AcWing 1214. 波动数列
原题链接
中等
作者:
我是java同学
,
2023-01-11 17:05:06
,
所有人可见
,
阅读 115
思路
- 由于x的变化可能太多,所以可以用变化小的变量把x表示出来
- 任何一个原序列,对应d1,d2…dn的一个取值,反过来任何一个d1,d2…dn的一组取值,都可以对应原来的序列
- 提问变成所有满足d1,d2…dn的取法的方案数
- 两个限制
- a,b的取法
- 满足是n的倍数,x就能求出合法值
- 集合:所有只考虑前i项,且当前的总和模以n的余数是j的方案集合
- 属性:count
- 状态计算:
- (前i - 1项的和 + i * a ) % i == j
#include <iostream>
using namespace std;
const int N = 1010, mod = 100000007;
int f[N][N];
int get_mod(int a, int b)
{
return (a % b + b) % b;
}
int main()
{
int n, s, a, b;
cin >> n >> s >> a >> b;
f[0][0] = 1;
for (int i = 1; i < n; i ++ )
for (int j = 0; j < n; j ++ )
f[i][j] = (f[i - 1][get_mod(j - a * i, n)] + f[i - 1][get_mod(j + b * i, n)]) % mod;
cout << f[n - 1][get_mod(s, n)] << endl;
return 0;
}