1214. 波动数列

https://www.acwing.com/problem/content/1216/

定义f[i][j]为考虑前i个d,余数为j的count数
需要注意的是,根据理解推得的公式,有多种等效形式
我这里为n*x+1*d1+2*d2+3*d3+........+(n-1)*dn-1;
对于每一个d,都有+a,-b两种形式,从所有组合形式的集合来分析
利用集合状态分析,前一次组合选择,即f[i-1],有+a与-b两种形式
且余数要减去最后一项再膜n
表示出来就是f[i-1][ (j-i*a) % n ]
同理有f[i-1][ ( j+i*b) % n ] 

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1005, MOD = 100000007;
int f[N][N];
int a, b, n, s;

int get_mod(int a, int b) //求正余数
{
	return (a % b + b) % b;
}
int main()
{
	f[0][0] = 1;//初始条件
	scanf("%d%d%d%d", &n, &s, &a, &b);
	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;
		}
	cout << f[n - 1][get_mod(s, n)] << endl;
	return 0;
}