题目分析
首先先对题目做等价变形
$x = \frac{s - (d_{1}+2*d_{2}+…+(n-1)d_{n-1})}{n}$,分析可得每一组d的取法对应了一种序列。
换句话说,一种符合题意的$d_{i}$的取法,对应一种符合题意的序列。
因此,我们将问题等价为寻找一组$d_{i}$使得它与s同余n.
这是求组合的问题,因此采用背包模型
状态
f[i][j]表示只考虑前i项,且%n余数为j的方案数。
状态转移
考虑到第i项只有两种取法,+a,-b。记前$n - 1$项的和为C
当第i项取+a的时候,满足(C + ia) 模以n同余于j。
即C模以n 同余于j - ai.
同理对于第i项取-b时,令-b替换+a,
C模以n 同余于j + i*b.
推导出状态转移方程 f[i][j] = f[i - 1][j - ia] + f[i - 1][j + ib]
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, MOD = 100000007;
int f[N][N];
int get_mod(int a, int b) // 求a除以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 * (n - i), n)] + f[i - 1][get_mod(j + b * (n - i), n)]) % MOD;
cout << f[n - 1][get_mod(s, n)] << endl;
return 0;
}