【蓝桥杯省赛】2014年A组波动数列题解：动态规划解法与代码解析（C++实现）
一、题目解读
“波动数列”是2014年蓝桥杯省赛A组的一道经典题目。题目要求生成一个数列，其前n项的和模n等于给定值s，且每项只能通过加减固定值a、b波动。问题本质是求解满足特定模运算条件的数列组合方案数，涉及数学递推与组合计数，需转化为算法模型求解。
二、解题思路
采用动态规划（Dynamic Programming）解决该问题。核心思想是定义状态转移方程，通过递推计算前i项的和模n的方案数。关键点如下：
1. 状态定义：dp[i][j]表示前i项的和模n等于j的方案数。
2. 边界条件：初始状态dp[0][0] = 1（0项和为0的唯一方案）。
3. 状态转移：当前项可加减a、b，因此第i项的和由前i-1项推导：dp[i][j] = dp[i-1][j-ai] + dp[i-1][j+bi]，需通过取模处理负数与溢出。
4. 优化细节：自定义mod函数处理负数取模，避免直接运算的边界问题；使用MOD常数防止结果溢出。
三、解题步骤
1. 输入参数：读取n（项数）、s（目标模值）、a、b（波动值）。
2. 初始化DP数组：创建n×n的dp矩阵，初始状态dp[0][0]设为1。
3. 循环递推：
外层循环i从1到n-1，逐层扩展项数。
内层循环j遍历模n的所有可能值（0到n-1）。
状态转移时，通过mod函数处理加减a、b后的模值，累加前状态的方案数。
4. 输出结果：最终方案数为dp[n-1][s mod n]，即n项满足条件的组合数。
四、代码与注释
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 100000007; // 溢出保护常数
// 自定义取模函数处理负数（关键优化）
inline int mod(int x, int n) {
return (x % n + n) % n; // 将负数转正后再取模
}
int main() {
int n, s, a, b; // 输入参数
cin >> n >> s >> a >> b;
// dp[i][j]：前i项的和模n等于j的方案数
vector<vector<int>> dp(n, vector<int>(n, 0));
dp[0][0] = 1; // 初始状态：0项和为0有1种方案
for (int i = 1; i < n; i++) { // 递推项数
for (int j = 0; j < n; j++) { // 遍历模值
// 状态转移：当前项可+a或-b（需处理负数模运算）
dp[i][j] = (dp[i-1][mod(j - a*i, n)] + dp[i-1][mod(j + b*i, n)]) % MOD;
}
}
// 输出结果：n项满足s mod n的方案数
cout << dp[n-1][mod(s, n)] << endl;
return 0;
}五、总结
该解法巧妙将数学问题转化为动态规划模型，通过状态压缩与优化取模运算，高效求解组合计数问题。代码亮点在于负数处理细节与MOD常数的防溢出设计，体现了算法竞赛中“边界条件优化”的重要性。动态规划思路适用于类似递推求和问题，值得算法学习者深入理解与实践。
原创内容 转载请注明出处
