AcWing_1214 波动数列(组合问题DP)

AcWing

1214. 波动数列

设数列的第一项为$x$，增量$d_i\in {+a, -b}$，那么有：

$x + (x+d_1) + (x+d_1+d_2) + \cdots + (x+d_1+d_2+\cdots +d_{n-1})=s$，

即：$nx + (n-1)d_1 + (n-2)d_2 + \cdots + 1d_{n-1} = s$.

暴力的做法是，枚举所有的取值$d_1, d_2, \cdots , d_{n-1}\in {+a, -b}$，对于某一组取值，如果解出$x \in N$，那么方案数加1. 但是这样做的时间复杂度是$O(2^n)$，一定会TLE.

不妨对上式化简，用变量$d_1, d_2, \cdots , d_{n-1}$和常量$s, n$来表示$x$，那么：

$x=\frac{s-((n-1)d_1 + (n-2)d_2 + \cdots + 1d_{n-1})}{n}$

当$x \in N$时，分子$s-((n-1)d_1 + (n-2)d_2 + \cdots + 1d_{n-1})$一定是分母$n$的整数倍，那么$s$与$((n-1)d_1 + (n-2)d_2 + \cdots + 1d_{n-1})$关于$n$是同余的，即：

$((n-1)d_1 + (n-2)d_2 + \cdots + 1d_{n-1}) \equiv s \mod n$

令数列$array_i = { (n-1)d_1, (n-1)d_1 + (n-2)d_2, \cdots, (n-1)d_1 + (n-2)d_2 + \cdots + 1d_{n-1}}, i\in [1, n-1]$.

令$f[i][j]$：数列$array$的第$i$项，余数为$j$的方案数，题目所求即为$f[i-1][s\%n]$.

设数列$array$的第$i$项对$n$求模为$c$，对应的方案数为$f[i-1][c]$，如果从$f[i-1][c]$转移到$f[i][j]$，那么有$c+(n-i)d_i \equiv j \mod n$，则$c \equiv j - (n-i)d_i \mod n$，$f[i-1][c]$可以表示为$f[i-1][j - (n-i)d_i]$，则状态转移方程为：

$f[i][j] = f[i - 1][j - (n-i)a] + f[i - 1][j + (n-i)b]$.

考虑边界条件，$f[0][0] = 1$，即不取任何一项时，$0 \equiv 0 \mod n$，是一种方案。

当$s < 0$时，$s \% n < 0$，而数组下标不能为负数，所以对$n$取余数，要取正余数。

int getmod(int a){
    return ((a % n) + n) % n;
}

代码：

#include <bits/stdc++.h>
using namespace std;
int n, s, a, b;
const int N = 1010, MOD = 100000007;
int f[N][N];
int getmod(int a){
    return ((a % n) + n) % n;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> s >> a >> b;
    f[0][0] = 1;
    for(int i = 1; i <= n - 1; i++)
        for(int j = 0; j <= n - 1; j++)
            f[i][j] = (f[i - 1][getmod(j - (n-i)*a)] + f[i - 1][getmod(j + (n-i)*b)]) % MOD;
    cout << f[n - 1][getmod(s)];
    return 0;
}