分析
第一个数为x,则第二个为x+d1,第n个数为x+d1+....+dn-1
所以加起来$s=n*x+(n-1)*d_1+…+d_{n-1}$
$x=\frac{(s-((n-1)d_1+(n-1)d_2+…+d_{n-1}))}{n}$
$\frac{s}{n}$和$((n-1)d1+(n-1)d2+…+dn-1)\over n$同余时,x为一个合法整数
此时我们需要一次枚举$d_1,d_2,…d_{n-1}$
这时候就是组合问题
下面就可以用闫氏dp分析法了。
1.状态表示:f[i][j]表示要选i个a或者-b且余数为j的所有集合的数量。
2.状态计算:第i个可以选a或者-b。第i个选a:则表达式为 $[(n-1)*d_1+(n-2)*d_2+....+2*d_{n-2}+a] \% n=j$
所以 $[(n-1)*d_1+(n-2)*d_2+....+2*d_{n-2}] \% n=(j-a)\%n$正取模
随着i不断变大,f[i][j] = f[i - 1][j - i * a]
同理:f[i][j] = f[i - 1][j + i * b]
时间复杂度:O(n2)
状态数量 * 状态转移时操作数 = (n - 1) * (n - 1) * 2
#include<bits/stdc++.h>
using namespace std;
const int N=1010,MOD = 100000007;
int n,s,a,b;
int dp[N][N]; //dp[i][j]表示要选i个a或者-b且余数为j的所有集合的数量
//将i个加a或减b进行排列组合
int get_mod(int a, int b) // 求a除以b的正余数
{
return (a % b + b) % b;
}
int main(){
cin>>n>>s>>a>>b;
dp[0][0]=1;
for(int i=1;i<n;i++){
for(int j=0;j<n;j++){
dp[i][j]=(dp[i-1][get_mod(j-a*i,n)]+dp[i-1][get_mod(j+b*i,n)])% MOD;
// cout << dp[i][j]<<' ';
}
// cout<<"\n";
}
cout << dp[n - 1][get_mod(s, n)] << endl;
return 0;
}