题目描述
观察这个数列:
1 3 0 2 -1 1 -2 …
这个数列中后一项总是比前一项增加2或者减少3,且每一项都为整数。
栋栋对这种数列很好奇,他想知道长度为 n 和为 s 而且后一项总是比前一项增加 a 或者减少 b 的整数数列可能有多少种呢?
输入格式
共一行,包含四个整数 n,s,a,b,含义如前面所述。
输出格式
共一行,包含一个整数,表示满足条件的方案数。
由于这个数很大,请输出方案数除以 100000007 的余数。
数据范围
1≤n≤1000 ,
−109≤s≤109,
1≤a,b≤106
样例
输入样例:
4 10 2 3
输出样例:
2
样例解释
两个满足条件的数列分别是2 4 1 3和7 4 1 -2。
#include <iostream>
#include <cstdio>
using namespace std;
/*波动数列:二维dp,先对原题意进行化解
假设数列相邻两项之间的差为di属于集合{+a, -b}
则数列的每一项为 x x + d1 x + d1 + d2 x + d1 + d2 + d3, ..., x + d1 + d2 + ... + dn-1
求和, 得x = (s - ((n - 1) d1 + (n - 2)d2 + ... + dn-1) / n
由于x取值范围很广,因此只要s-()中, ()内的值模n与s模n的值相同即可
问题转化为, 如何选取di, 使得()内的值模n与s模n的值相同,类似背包问题
f[i][j]表示考虑括号内前i项, 当前总和模n余数为j的方案数
状态转移时,假设前i-1项总和模n余数为c,则计算状态转移中c的值
1、第i项选择+a, c + (n - 1) * a = j(mod n) c = j - (n - i) * a
2、第i项选择-b, c - (n - 1) * b = j(mod n) c = j + (n - 1) * b
由于j-(n - 1) * a 可能为负数,因此需要写一个求a%b的正余数的函数
状态转移就是f[i][j] = f[i - 1][c] + f[i - 1][c], c分别取以上两个值
*/
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;//考虑前0个数, 总和为0, 模n也为0, 方案数为1
for (int i = 1; i <= n - 1; i ++)//()内共有i - 1项
for (int j = 0; j < n; j ++)//余数为0-(n - 1)
f[i][j] = (f[i - 1][get_mod(j - (n - i) * a, n)] + f[i - 1][get_mod(j + (n - i) * b, n)]) % MOD;
cout << f[n - 1][get_mod(s, n)] << endl;//寻找与s%n同余的方案由多少种
return 0;
}