[蓝桥杯][2014年第五届真题]波动数列

设第一项为(x_1)，则(2 sim n)项依次为(x_1+dif_1、x_1+dif_1+dif_2、cdots、x_1+dif_1+dif_2+cdots+dif_{n-1})。其中(dif_i in {+a,-b})，即第(i)项为：(x_1+(i-1)*dif_i)。

则总和为：(sum = n*x_1+(n-1)*dif_1+(n-2)*dif_2+ cdots dif_{n-1})。

要求(sum = s)的方案数，由(sum=s)得(x_1 = frac{s- (n-1)*dif_1+(n-2)*dif_2+ cdots dif_{n-1}}{n})，要求(x_1)为整数，(sum = s)的方案数等价于求(x_1)为整数的方案数。

由(x_1)为整数，得(s equiv sum_{i=1}^{n-1}(n-i)*dif_i mod n)，即满足(sum_{i=1}^{n-1}(n-i)*dif_i)和(s)模(n)同余的方案数。

令(v_i= (n-i)*dif_i)，其中(v_0=0)。
状态表示：(f(i,j))：前(i)项模(n)为(j)的方案数。
状态转移：

[f(i,j)=f(i-1,j+(n-i)*a)+f(i-1,j-(n-i)*b) ]

边界：

[f(0,0)=0 ]

const int N=1010;
int f[N][N];
int n,s,a,b;

int get(int x,int n)
{
    return (x%n+n)%n;
}

int main()
{
    cin>>n>>s>>a>>b;

    f[0][0]=1;
    for(int i=1;i<n;i++)
        for(int j=0;j<n;j++)
            f[i][j]=(f[i-1][get(j-a*i,n)]+f[i-1][get(j+b*i,n)])%mod;
    cout<<f[n-1][get(s,n)]<<endl;
    //system("pause");
    return 0;
}