AcWing 1214. 波动数列
原题链接
中等
作者:
Bear_King
,
2021-01-14 08:58:50
,
所有人可见
,
阅读 364
波动数列
组合DP的变种类型题:
状态定义:所有只考虑前 i 项,且当前的总和除以 n 的余数是 j 的方案的集合 , 定义其属性为:Count
所以只用考虑最后一项是+ia还是+ib
状态转移方程:f[i][j] = f[i-1][(j-ia)%n] + f[i-1][(j+ib)%n];
本题难点在于细节处理和假设数列公式的推导:x = S - ((n - 1)d(1) + (n - 2)d(2)+… + d(n-1)) / n
#include<iostream>
#define N 1010
#define MOD 100000007
using namespace std;
int f[N][N];
int get_mod(int a,int b)//处理负余数的问题
{
return (a % b + b) % b;
}
int main()
{
int n,s,a,b;
cin >> n >> s >> a >> b;
f[0][0] = 1;//一个数也不取,只有这种方案,其他都为0
for(int i = 1;i <= n;i ++)
for(int j = 0;j < n;j ++)
f[i][j] = (f[i - 1][get_mod(j - a * i,n)] + f[i - 1][get_mod(j + b * i,n)]) % MOD;
cout << f[n - 1][get_mod(s, n)] << endl;//当s为负数时会报0
return 0;
}