动态规划 计数

【Codeforces 1681E】Non-Intersecting Subpermutations

Posted by WHZ0325 on 2023-09-05, Viewed times

题目描述

给定 $n, k$，求由 $[1,k]$ 组成所有长度为 $n$ 的序列的贡献之和，一个序列的贡献为能够在其中找到的最多互不交叉的段数使得每一段长度为 $k$ 且恰好包含 $[1,k]$ 中每个数，输出答案对 $998244353$ 取模的值。

$2\le n,k\le 4000$。

算法分析

设 $f[i][j]$ 表示前 $i$ 个数中末尾连续互不相同的数有 $j$ 个时的方案数，考虑转移：

  1. 由前 $i - 1$ 个数补充一个不在其已有互不相同的数集中的数得到，这样的数由 $k - (j - 1)$ 个，即 $(k-(j - 1))\times f[i - 1][j - 1]$，对于 $j = 0$ 的情况则从 $f[i - 1][k - 1]$ 转移。
  2. 由前 $i - 1$ 个数补充一个在其已有互不相同的数集中的数得到，枚举新数在原数集中的位置，则应由所有 $t\ge j$ 的 $f[i-1][t]$ 转移而来。例如，对于 $f[i-1][j-1]$ 而言，添加一个在 $j - 1$ 个数中出现过的数可以转移到 $f[i][1\dots j-1]$（去掉一段数再加上一个数）。

累计答案时考虑每一个刚刚完成的段对答案的贡献，即 $\sum k^{n-i}f[i][0]$。

时间复杂度为 $O(nk)$。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#define N 4005
typedef long long int ll;

const int mod = 998244353;
inline void inc(int &x, int y) { x += y; if(x >= mod) x -= mod; }
inline int mul(int x, int y) { return (ll)x * y % mod; }
inline int qpow(int n, int k) {
    int ans = 1;
    while(k > 0) {
        if(k & 1) ans = mul(ans, n);
        n = mul(n, n); k >>= 1;
    }
    return ans;
}

int f[N][N];
int main() {
    int n, k; scanf("%d %d", &n, &k);

    int ans = 0; f[0][0] = 1;
    for(int i = 1; i <= n; ++i) {

        f[i][0] = f[i - 1][k - 1];
        for(int j = 1; j < k; ++j) {
            f[i][j] = mul(f[i - 1][j - 1], k - (j - 1));
        }

        int cur = 0;
        for(int j = k - 1; j >= 1; --j) {
            inc(cur, f[i - 1][j]);
            inc(f[i][j], cur);
        }

        inc(ans, mul(f[i][0], qpow(k, n - i)));
    }
    printf("%d\n", ans);

    return 0;
}