推公式
推成与余数相关的
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3003;
const int mod = 100000007;
ll f[N][N];
int cmod(int a, int p)
{
return (a % p + p) % p;
}
int main()
{
int n, s, a, b;
cin >> n >> s >> a >> b;
s = cmod(s, n);
f[0][0] = 1;
for(int i = 1; i <= n - 1; i ++ )
for(int j = 0; j < n; j ++ )
{
f[i][(j + i * a) % n] = (f[i][(j + i * a) % n] + f[i - 1][j]) % mod;
f[i][cmod(j - i * b, n)] = (f[i][cmod(j - i * b, n)] + f[i - 1][j]) % mod;
}
cout << f[n - 1][s];
}