AcWing 1214. 波动数列
原题链接
中等
作者:
wjie
,
2020-08-06 14:54:04
,
所有人可见
,
阅读 489
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e3 + 5;
const int MOD = 100000007;
int n, s, a, b;
int dp[N][N];
int func(int x)
{
return (x % n + n) % n;
}
int main()
{
scanf("%d %d %d %d", &n, &s, &a, &b);
dp[1][func((n-1) * a)] = 1;
dp[1][func((n-1) * (-b))] = 1;
for (int i = 2; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
dp[i][j] = (dp[i-1][func(j-(n-i)*a)] + dp[i-1][func(j+(n-i)*b)]) % MOD;
}
}
printf("%d", dp[n-1][func(s)]);
return 0;
}