P8614 [蓝桥杯 2014 省 A] 波动数列 的题解

卷王 · 2023-03-31 21:19:46 · 题解

题目大意

求满足和为 s 且 t_i=t_{i-1}+a 或 t_i=t_{i-1}-b 的长度为 n 的数列 t 的方案数。

思路

首先，得确定大概方向：

一提到方案数，你会想到什么？

• 搜索（当然可以，只是会 T 到飞起）

• 记忆化搜索（emmm，我暂时还没研究过，或许可以吧）

• 大炮——dp！（此题正解）

其次，冷静分析数据范围：

看到题目里面的 n \leq 1000，再看看空间范围就可以大概猜测：用 O(n^2) 的时空复杂度。这就是本题最清晰的解法。

然后，设计状态：

我们发现只有 n 这一个变量可以二重循环，因此，我们尝试进行每重循环的次数都和 n 有关。但是即使这样，空间也有可能不够啊！后面的都是 10^6 级以上的！怎么办？我们会想到取模。于是设 dp_{i, j} 表示前 i 项的和模 n 等于 j 时的方案数。

最后，最重要的转移方程：

关于取模的转移方程，我不细讲了，就看 RoMantic_Queue 大佬的吧。觉得他讲的详细些。

在一些数学推导（其实这题也是个数学题）后，得到转移方程 dp[i][j]=(dp[i-1][c(j-a×i)] + dp[i-1][c(j+b×i)])，其中 c(x) 表示 x 对 n 取模的结果，注意负数。

坑点：

• 注意模数是 10^8 + 7。

• 注意转移方程里面的加减，别搞混了。

代码奉上：

//time：2023-04-01
#include <bits/stdc++.h>
using namespace std;
#define mod 100000007
typedef long long ll;
int n, s, a, b;
int dp[1007][1007];
inline int c(int x) {
    return (x % n + n) % n;
}
int main() {
    cin >> n >> s >> a >> b;
    dp[0][0] = 1;
    for(int i = 1; i < n; i++)
        for(int j = 0; j < n; j++)
            dp[i][j] = (dp[i - 1][c(j - a * i)] + dp[i - 1][c(j + b * i)]) % mod;
    cout << dp[n - 1][c(s)];
    return 0;
}