首页 题解

# Descirption

Luogu传送门

# Solution

题目要求我们求出符合某种条件的方案数，不难想到使用容斥或者二项式反演。

考虑二项式反演的套路，设至少 blablabla 的方案数 g(i,j,k)g(i, j, k)，恰好 blablabla 的方案数 f(i,j,k)f(i, j, k)，然后通过一定方法来计算。

回到这道题目上，我们设：

  • 至少有 ii 行 jj 列没有染色，且有 kk 种颜色没有使用的方案数为 g(i,j,k)g(i, j, k)。
  • 恰好有 ii 行 jj 列没有染色，且有 kk 种颜色没有使用的方案数为 f(i,j,k)f(i, j, k)

那么答案就是 f(0,0,0)f(0, 0, 0)。

注意到 g(i,j,k)g(i, j, k) 是可以直接计算的，即：

g(i,j,k)=(ni)(mj)(ck)(c−k+1)(n−i)×(m−j)g(i, j, k) = \dbinom{n}{i}\dbinom{m}{j}\dbinom{c}{k}(c - k + 1)^{(n - i) \times (m - j)}

即从 nn 行里选 ii 列不合法，mm 列里选 jj 列不合法，cc 种颜色中选 kk 种不使用，使用的 c−k+1c - k + 1 种颜色各有 (n−i)×(m−j)(n - i) \times (m - j) 种放法。

然后二项式反演一下：

f(x,y,z)=∑i=xn∑j=ym∑k=zc(−1)i+j+k−x−y−z(ix)(jy)(kz)g(i,j,k)f(x, y, z) = \sum_{i = x}^n\sum_{j = y}^m\sum_{k = z}^c(-1)^{i + j + k - x - y - z}\dbinom{i}{x}\dbinom{j}{y}\dbinom{k}{z}g(i, j, k)

则：

f(0,0,0)=∑i=0n∑j=0m∑k=0c(−1)i+j+k(i0)(j0)(k0)g(i,j,k)=∑i=xn∑j=ym∑k=zc(−1)i+j+k(ni)(mj)(ck)(c−k+1)(n−i)×(m−j)\begin{aligned} f(0, 0, 0) &= \sum_{i = 0}^n\sum_{j = 0}^m\sum_{k = 0}^c(-1)^{i + j + k}\dbinom{i}{0}\dbinom{j}{0}\dbinom{k}{0}g(i, j, k) \\ &= \sum_{i = x}^n\sum_{j = y}^m\sum_{k = z}^c(-1)^{i + j + k}\dbinom{n}{i}\dbinom{m}{j}\dbinom{c}{k}(c - k + 1)^{(n - i) \times (m - j)} \end{aligned}

# Code

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
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 410;
const int mod = 1e9 + 7;
int n, m, c;
int fac[N], ifac[N];
int px[N * N];

inline int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return res;
}

inline int C(int n, int m){
    return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

inline void init(int n){
    fac[0] = 1;
    for(int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[n] = qpow(fac[n], mod - 2);
    for(int i = n - 1; i >= 0; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
}

signed main(){
    n = read(), m = read(), c = read();
    init(max(max(n, m), c));
    int ans = 0;
    for(int k = 0; k <= c; ++k){
        px[0] = 1;
        for(int i = 1; i <= n * m; ++i) px[i] = 1ll * px[i - 1] * (c - k + 1) % mod;
        for(int i = 0; i <= n; ++i)
            for(int j = 0; j <= m; ++j)
                ans = (ans + ((i + j + k) & 1 ? -1ll : 1ll) * C(n, i) % mod * C(m, j) % mod * C(c, k) % mod * px[(n - i) * (m - j)] % mod + mod) % mod;
    }
    write(ans), puts("");
    return 0;
}
// X.K.