蓝桥杯2014年第五届真题-波动数列 （C++代码）----------C语言-菜鸟级

解题思路:  用动态规划 ，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) 的贡献。

 剩下的就交个代码吧 

 详情查看原文   欢迎访问我的博客 一起交流

注意事项:

参考代码:

#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;
}