来源： 第五届蓝桥杯省赛C++A组

算法标签：动态规划，DP

题目描述

观察这个数列：

1 3 0 2 -1 1 -2 …

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

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

输入格式

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

输出格式

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

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

数据范围

1≤n≤1000,
−109≤s≤109,
1≤a,b≤106

输入样例：

4 10 2 3

输出样例：

2

样例解释

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

思路

1.这个数列中的后一项总是比前一项增加a或者减少b 

2.则s=x+d1 + x+d1+d2 + x+d1+d2+d3 +... x+d1+d2+...dn-1;
    s=n*x + n-1*d1 + n-2*d2 + ... 1*dn-1;

(s-(n-1*d1 + x-2*d2 + n-3*d3 +... 1*dn-1))/n == x;

3.由于数列为整数，则(s-(n-1*d1 + x-2*d2 + n-3*d3 +... 1*dn-1)) 是n的倍数

4.则i-1个数之和的情况下，c为前项之和，第i项为i*a
i-1,c+(i*a) = j(mod n)
    c=j-(a*i)(mod n)
则有f(i-1,j-(a*i)(mod n)   

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int MOD =  100000007;
int f[1010][1010];//前i个数的集合余数为j的数量

int get_mod(int a,int b)//求a%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*(n-i),n)] + f[i-1][get_mod(j+b*(n-i),n)])%MOD;


    cout<<f[n-1][get_mod(s,n)];
    return 0;
}