[数据结构与算法]AcWing 1214 波动数列

观察这个数列：

1 3 0 2 -1 1 -2 …

这个数列中后一项总是比前一项增加2或者减少3，且每一项都为整数。

栋栋对这种数列很好奇，他想知道长度为?nn?和为?ss?而且后一项总是比前一项增加?aa?或者减少?bb?的整数数列可能有多少种呢？

输入格式

共一行，包含四个整数?n,s,a,bn,s,a,b，含义如前面所述。

输出格式

共一行，包含一个整数，表示满足条件的方案数。

由于这个数很大，请输出方案数除以?100000007100000007?的余数。

数据范围

1≤n≤10001≤n≤1000,
?109≤s≤109?109≤s≤109,
1≤a,b≤1061≤a,b≤106

输入样例：

4 10 2 3

输出样例：

2

样例解释

两个满足条件的数列分别是2 4 1 3和7 4 1 -2。

假设第一个数是x，第二个数是x+d1,第三个数是x+d1+d2，第n个数是x+d1+……d(n-1)
di属于（+a，-b）
将这些数累加起来得到
nx+（n-1）d1+(n-2)d2+……+d(n-1)=s
整理得，x=s-((n-1)d1+(n-2)d2+……+d(n-1))/n
也就是说((n-1)d1+(n-2)d2+……+d(n-1))与s模n是同余的

d1 d2 …………di=+a;
d1' d2'…………di'=+a;
f[i][j]第i个数模n为j
设d（i-1）前面的和是C，C+ia与j模n同余
C与j-ia模n同余
f[i-1][(j-ia)%n]+f[i-1][(j+bi)%n]
所以是由上一层的i转移过来，而且无法像背包一样降维度，因为背包那个是有单调性的
dp[0][0]=1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[1005][1005];
const int mod=1e8+7;
int getmod(int a,int b)
{
    return (a%b+b)%b;
}
int n,s,a,b;
int main()
{
    cin>>n>>s>>a>>b;
    dp[0][0]=1;
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            dp[i][j]=(dp[i-1][getmod(j-a*i,n)]+dp[i-1][getmod(j+b*i,n)])%mod;
        }
    }
    cout<<dp[n-1][getmod(s,n)];

    return 0;
}