[蓝桥杯][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) 的贡献。

1	2	3	4
x	x a	x a ?	x a ?

剩下的就交个代码吧

AC代码：

代码语言：javascript复制

#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

0 人点赞