[蓝桥杯][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代码：
#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;
} 
京公网安备 11010502036488号