P8614 [蓝桥杯 2014 省 A] 波动数列
题目描述
观察这个数列：
。
这个数列中后一项总是比前一项增加 或者减少 。
栋栋对这种数列很好奇，他想知道长度为 和为 而且后一项总是比前一项增加 或者减少 的整数数列可能有多少种呢？
输入格式
输入的第一行包含四个整数 ，含义如前面说述。
输出格式
输出一行，包含一个整数，表示满足条件的方案数。由于这个数很大，请输出方案数除以 的余数。
输入输出样例 #1
输入 #1
4 10 2 3
输出 #1
2
说明/提示
【样例说明】
这两个数列分别是 2 4 1 3 和 7 4 1 -2。
【数据规模与约定】
对于 的数据，，，；
对于 的数据，，，；
对于 的数据，，，；
对于 的数据，，，；
对于 的数据，，，。
时限 1 秒, 256M。蓝桥杯 2014 年第五届省赛
解析
这更像是一道数学题，我每次做到这种题就可头疼
要解决这个问题，直接去枚举序列肯定是不行的，必须从数学公式上寻找突破口。
1. 核心数学推导
假设数列的第一项是 。 由于后一项总是比前一项 或 ，我们可以把每一项都写成 的形式：
- 第 1 项：
- 第 2 项： （其中 是 或 ）
- 第 3 项：
- …
- 第 项：
题目要求序列的和为 ，即：
我们将上面的每一项展开相加：
合并同类项（数一下 和每个 出现了多少次）：
- 出现了 次。
- 出现了 次（从第2项到第n项）。
- 出现了 次（从第3项到第n项）。
- …
- 出现了 次。
于是得到关键公式：
其中 。
2. 转化为同余问题
题目要求 必须是整数。我们将公式变形：
这意味着：等式左边的值必须能被 整除。 换句话说，等式左边的值模 必须等于 0：
移项得到最终的判断条件：
简化理解： 系数 的集合其实就是 。虽然顺序和 对应，但因为我们要算的是“有多少种方案”，我们只需要知道： 我们需要在 到 的每一步 中，选择让 乘以 或者 乘以 ，使得所有项加起来的总和，除以 的余数等于 除以 的余数。
3. 动态规划 (DP) 设计
这是一个典型的背包问题变种。
状态定义：
dp[i][j] 表示：只考虑前 个系数（即 ），经过加加减减后，总和模 的余数为 的方案数。
状态转移方程： 对于第 个数（也就是系数 ），我们有两种选择：
- 选择 ：这一项变成了 。
如果当前余数是 ，那么上一个状态的余数应该是 。
即：
dp[i][j] += dp[i-1][(j - i * a) % n] - 选择 ：这一项变成了 。
如果当前余数是 ，那么上一个状态的余数应该是 。
即：
dp[i][j] += dp[i-1][(j + i * b) % n]
注意：
在 C++ 中，负数取模结果可能是负数（例如 -2 % 5 = -2），但在数学和数组下标中我们需要正数（即 3）。所以计算下标时要通用公式：((rem % n) + n) % n。
初始状态：
dp[0][0] = 1。
表示没有选取任何数时，余数为 0 的方案数是 1（什么都不做）。其他 dp[0][...] 均为 0。
最终答案：
dp[n-1][(s % n + n) % n]。
代码
//
// Created by 23264 on 2026/2/11.
//
#include<bits/stdc++.h>
using namespace std;
constexpr int MOD = 100000007;
int n,s,a,b;
vector<vector<int>> dp;
int GetMod(int x)
{
return (x % n + n) % n;
}
void solve()
{
dp[0][0] = 1;
for (int i = 1;i < n;i++)
{
for (int j = 0;j < n;j++)
{
dp[i][j] = (dp[i - 1][GetMod(j - a * i)] + dp[i - 1][GetMod(j + b * i)]) % MOD;
}
}
}
int main()
{
cin >> n >> s >> a >> b;
dp.resize(n,vector<int>(n));
solve();
cout << dp[n - 1][GetMod(s)];
}