题目

CF2145G。

思路

对于这种数方案的题目，我们应当先考察方案的合法性。

由于题面要求用最小的操作次数达到一个方案，所以一行或一列涂色次数至多为 11。

随后考虑特殊的性质，因为颜色的值随着操作是单调递增的，因此颜色为 kk 的值最后一定整行整列出现。

去掉这些行和列，我们发现这个问题变成了 k−1k-1 种颜色的子问题，而这个子问题到原先的问题需要额外的操作次数是去掉的行数 + 去掉的列数。

如此一直重复到 k=1k=1，设此时的行列分别是 x,yx,y，那么需要的操作次数就会是 min⁡(x,y)\min(x,y)。

于是，为了涂到给定的一个方案，就会需要 n+m−max⁡(x,y)n+m-\max(x,y) 的操作次数。这是因为 min⁡(x,y)=x+y−max⁡(x,y)\min(x,y)=x+y-\max(x,y)，而 ∑xi+∑yi=n+m\sum x_i+\sum y_i=n+m。

我们可以枚举 x,yx,y，后面的答案需要乘上 (nx)(my)\binom{n}{x}\binom{m}{y}。

现在的问题就变成了，有 n+m−x−yn+m-x-y 个操作次数，需要涂上 k−1k-1 种颜色。

注意，由于 11 这一块颜色的存在，我们在剩下的行或列中，无论如何也无法用新的颜色完全覆盖之前的某个颜色。

因此，只要这些操作次数能用完这 k−1k-1 种颜色，它就是合法的。

设 dpi,jdp_{i,j} 是 ii 个操作次数，jj 种颜色的方案，递推式：

dpi,j=jdpi−1,j+[k−1−(j−1)]dpi−1,j−1dp_{i,j}=jdp_{i-1,j}+[k-1-(j-1)]dp_{i-1,j-1}

当然，还有一个别的 dp 方式，你可以认为 jj 种颜色只能是 1∼j1\sim j，那么递推式是：

dpi,j′=jdpi−1,j′+dpi−1,j−1′dp'_{i,j}=jdp'_{i-1,j}+dp'_{i-1,j-1}

这是因为前 i−1i-1 只用了颜色 1∼j−11\sim j-1 时，第 ii 次操作只能用 jj 这个颜色。

然而，这样的话 dp 的含义就变了，这意味着第 jj 个颜色出现时它只能是 jj，但是它实际上可以是 1∼k−11\sim k-1 的任意一种没出现过的颜色，因此统计答案时需要乘一个全排列 (k−1)!(k-1)!。

写这个只是因为我在一开始思考的是第二种 dp 方式，不过确实第一种从常数上看会更优。

实现

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
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 4010, P = 998244353;
int dp[N][N], ans[N];
int fact[N], infact[N];

int qpow(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * a % P;
        a = a * a % P;
        k >>= 1;
    }
    return res;
}

int C(int a, int b) {
    return fact[a] * infact[b] % P * infact[a-b] % P;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    dp[0][0] = 1;
    for (int i = 1; i <= n+m; i++) {
        for (int j = 1; j <= k-1; j++) {
            dp[i][j] = (dp[i-1][j] * j + dp[i-1][j-1] * (k-j)) % P;
        }
    }

    fact[0] = 1;
    for (int i = 1; i < N; i++) fact[i] = fact[i-1] * i % P;
    infact[N-1] = qpow(fact[N-1], P-2);
    for (int i = N-2; i >= 0; i--) infact[i] = infact[i+1] * (i+1) % P;

    for (int x = 1; x <= n; x++) {
        for (int y = 1; y <= m; y++) {
            ans[n+m-max(x,y)] = (ans[n+m-max(x,y)] + C(n, x) * C(m, y) % P * dp[n+m-x-y][k-1]) % P;
        }
    }

    for (int i = min(n, m); i <= n+m-1; i++) cout << ans[i] << " \n"[i == n+m-1];

    return 0;
}