思路: 闫氏dp法
關于前一項的表示
代碼:
# include<iostream>
# include<cstring>
# include<cstdio>
# 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 - i * a,n)] + f[i - 1][get_mod(j + i * b,n)]) % MOD;
}
}
//序列的長度是n,若目前數是x,需要組合n - 1個數,才變成S,是以相當于求從前n - 1個項中選,餘數是s % n的方案數
cout << f[n - 1][get_mod(s,n)] << endl;
return 0;
}