动态规划/DP/组合数学

时间复杂度：$O(N^2)$

设序列为 $x \in \mathcal{Z}$、$x + d_1$、$x + d_1 + d_2$、…、$x + d_1 + d_2 + … + d_{n-1}$，总共有 $n$ 项，将 $n$ 项累加整理得：

$$nx + (n - 1)d_1 + (n - 2)d_2 + … + d_{n -1}$$

令上述序列之和等于 $s$，解得 $x = \frac{s - (n - 1)d_1 + (n - 2)d_2 + … + d_{n -1}}{n}$，若上述的 $x$ 为整数，则该序列为波动数列，若 $x$ 为整数，则分子必定为 $n$ 的倍数，即 $(n - 1)d_1 + (n - 2)d_2 + … + d_{n -1}$ 与 $s$ 模 $n$ 的余数相同，而 $d_1、d_2、d_3、…、d_{n - 1}$ 只能 $+a、-b$，此时就变成了一个组合问题。

动态规划：

$f[i][j]$ 表示 $(n - 1)d_1 + (n - 2)d_2 + … + d_{n -1}$ 序列的前 $i$ 项之和对 $n$ 取模余数为 $j$ 的方案数。

$C$ 表示序列的前 $i - 1$ 项之和对 $n$ 的余数，由 $(C + (n - i) \times a) \\% n = j$、$(C - (n - i) \times b) \\% n = j$，可解 $C = (j - (n - i) \times a) \\% n$、$C = (j + (n - i) \times b) \\% n$。

可推状态转移方程：

$f[i][j] = f[i - 1][(j - (n - i) \times a) \\% n] + f[i - 1][(j + (n - i) \times b) \\% n]$

C++ 代码

#include <iostream>
using namespace std;

const int N = 1010, MOD = 100000007;
int f[N][N]; // f[i][j] 表示前 i 项，所求总和模 n 的余数为 j 的所有方案

int get_mod(int a, int b)
{
    return (a % b + b) % b;
}

int main() // 组合问题
{
    int n, s, a, b;
    cin >> n >> s >> a >> b;
    f[0][0] = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < n; ++j) { 
            // C = j - i * a 或者 C = j + i * b
            f[i][j] = (f[i - 1][get_mod(j - (n - i) * a, n)] + f[i - 1][get_mod(j + (n - i) * b, n)]) % MOD;
        }
    }
    cout << f[n - 1][get_mod(s, n)] << endl; // s 可能为负
    return 0;
}