20241014总结

bryce蒟蒻的小窝 / 2024-10-19 / 原文

true

40pts

设 $dp_{i, j, k}$ 表示第 $i$ 个左端点为 $j$，右端点为 $k$ 的方案数，转移很好想，暴力枚举合法的 $l, r$ 转移，由于空间开不下，选择用滚动数组优化一维，时间复杂度 $O(nm^4)$。

70pts

考虑在什么条件下才能够转移，很明显转移的 $l\le k$，$r\ge \max(l, j)$，由于在 $r\lt l$ 时的 $dp$ 为 $0$，所以 $dp_{i, j, k} = \sum\limits_{1\le l\le k, j\le r\le m}dp_{i - 1, l，r}$，这一坨可以用前缀和优化，时间复杂度 $O(nm^2)$。

100pts

发现这样枚举左右端点是无法继续优化下去了，于是考虑将左右端点拆开进行动态规划，设 $f_{i, j}$ 为第 $i$ 个右端点为 $j$ 的方案数，$g_{i, j}$ 为第 $i$ 个左端点为 $j$ 的方案数。

思考转移方程，需要用到容斥，$f_{i, j} = j\times \sum\limits_{k = 1}^{j} g(i - 1, k) - \sum\limits_{r = 1}^{j}\sum\limits_{k = 1}^{r - 1} f(i - 1, k)$，意思为所有左端点在 $j$ 左侧的区间的方案数减去这些满足上一条件的右端点小于当前区间左端点的区间的方案数，$g_{i, j}$ 同理。集中注意力，发现所有的求和都可以用前缀和优化，顺便还可以直接去掉第一维，减少空间，于是时间复杂度为 $O(nm)$。

#include<iostream>
#define int long long

using namespace std;

inline int read(){
    register int x = 0, f = 1;
    register char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}

const int N = 5e3 + 10, mod = 998244353;
int n, m, ans;
int f[N], g[N], sf[N], sumf[N], sg[N], sumg[N];

signed main(){
    freopen("true.in", "r", stdin);
    freopen("true.out", "w", stdout);
    n = read(), m = read();
    for (int i = 1; i <= m; i++) f[i] = i, g[i] = m - i + 1;
    for (int i = 2; i <= n; i++){
        for (int j = 1; j <= m; j++) sf[j] = (sf[j - 1] + f[j]) % mod, sumf[j] = (sumf[j - 1] + sf[j]) % mod;
        for (int j = 1; j <= m; j++) sg[j] = (sg[j - 1] + g[j]) % mod;
        for (int j = m; j >= 1; j--) sumg[j] = (sumg[j + 1] + (sg[m] - sg[j - 1] + mod) % mod) % mod;
        for (int j = 1; j <= m; j++) f[j] = (j * sg[j] % mod - sumf[j - 1] + mod) % mod;
        for (int j = 1; j <= m; j++) g[j] = ((m - j + 1) * ((sf[m] - sf[j - 1] + mod) % mod) % mod - sumg[j + 1] + mod) % mod;
    }
    for (int i = 1; i <= m; i++) ans = (ans + f[i]) % mod;
    cout << ans;
    return 0;
}