[蓝桥杯][2014年第五届真题]波动数列（DP 简洁）

                             [蓝桥杯][2014年第五届真题]波动数列 时间限制: 1Sec 内存限制: 128MB 提交: 64 解决: 16 题目描述 观察这个数列：  1  3  0  2  -1  1  -2  ...  这个数列中后一项总是比前一项增加2或者减少3。  栋栋对这种数列很好奇，他想知道长度为  n  和为  s  而且后一项总是比前一项增加a或者减少b的整数数列可能有多少种呢？  样例说明  这两个数列分别是2  4  1  3和7  4  1  -2。  数据规模和约定  对于100%的数据，1< =n< =1000，-1,000,000,000< =s< =1,000,000,000，1< =a,  b< =1,000,000。  输入 输入的第一行包含四个整数  n  s  a  b，含义如前面说述。  输出 输出一行，包含一个整数，表示满足条件的方案数。由于这个数很大，请输出方案数除以100000007的余数。  样例输入 4 10 2 3 样例输出 2

思路： 用动态规划 ，01背包，的思想  

 1.按照题目要求，最终得到的序列的长度为n，和为s，并且后一项是前一项加a或减b，我们不妨将这个操作封装在一起，记作P 操作，即P=(a,-b)。

 2.设首项为x，可以得到一个等式x+(x+P)+(x+2P)+...+(x+(n-1)P)=s，将这个式子整理一下，就是nx+P+2P+...+(n-1)P=s，

  即(s-(P+2P+...+(n-1)P))/n=x    s%n-(P+2P+...+(n-1)P)%n=0;

 3. 于是就等价于求这个式子有多少个可能    s%n-(P+2P+...+(n-1)P)%n=0;    令 s%n=K1 ，P%n=K2, 2P%n=K3,...(n-1)P%n=Kn     那么 K1+K2+K3...+Kn=0; 让他们的和为0 则满足条件

4.再来看看一张表

  令 首项为 x 假设 第2项为加 a 那么 它后面的项 都会存在第2项的贡献 

 所以 第2项加上a  对于整个序列来说 给整个序列带来了 a*(4-2+1) 即 a*(n-i+1) 的贡献。

 剩下的就交个代码吧

AC代码：

#include<iostream>
#define LL long long
#define MOD 100000007
using namespace std;
int main()
{
    LL n, s, a, b,sum_a,sum_b;
	LL dp[1010][1010] ;//dp[i][j] 代表序列前Ki的和取模n后的值为 j的方案数 
    cin>>n>>s>>a>>b;
    dp[1][(s%n+n)%n] = 1;//相当于式子的s%n，即 K1 ( (s%n+n) 是处理负数） 
    for (int i = 2; i<=n; i++){// 式子的前Ki项 
        sum_a = a*(n-i+1)%n;//假定 第i项为加上 a 那么 a 的贡献为 a*(n-i+1)%n 
        sum_b = b*(n-i+1)%n;//假定 第i项为减上 b 那么 b 的贡献为 b*(n-i+1)%n
        for (int j = 0; j < n; j++)//遍历所有前K(i-1)对n取模可能取到的值的方案数 
        {
            dp[i][(j-sum_a+n)%n] = (dp[i][(j-sum_a+n)%n] + dp[i-1][j]) % MOD;
        //前Ki项为j-sum_a对n取模的方案数 等于
		// 其它对n取模也得 j-sum_a值 加上 前K(i-1)项取模n的值j  (j-sum_a+n)防止负数 
            dp[i][(j+sum_b)%n] = (dp[i][(j+sum_b)%n] + dp[i-1][j]) % MOD;
        //前Ki项为j+sum_b对n取模的方案数 等于
		// 其它对n取模也得 j+sum_b值 加上 前K(i-1)项取模n的值j  
        }
    }
    cout<<dp[n][0]<<endl;//输出前Kn项对n取模后为0的方案数 即是答案。 
    return 0;
}

题目链接：http://www.dotcpp.com/oj/problem1449.html