牛客 NC13884 组合数学-容斥

传送门: https://ac.nowcoder.com/acm/problem/13884

大体的题意是给你n, m, k(1 <= n,m <= 1e9 , 1 <= k <= 1e6 , k <= n,m)
n是一排 n 个box, m是有 m 种不同的颜色, k是每次使用 k 种不同颜色(k种都用到, 并且相邻箱子颜色不能一样), 给 n 个box染色, 询问方案数.

题意比较简单, 我们首先想到, C(m, k) : 从m种颜色种挑k种的方案数, 然后问题就转化为 : k 种颜色给 n 个盒子染色的方案数, 相邻盒子颜色还不能相同.

想了好久, 没能成功选择出来, 最后一次尝试了一下插空法(高中学过的), 本以为凑出来了, 结果刚开始敲, 突然发现还是有重复计数, 果断放弃, 看官方牛的题解去了.

定义用不超过 k 种颜色涂完 n 个盒子的方案数为
$$ x_k = k(k-1)^{n-1} $$
这个公式好解释, 第一个k种选择, 之后都是(k - 1)种选择.
然后, 根据容斥原理, 正好 k 种颜色涂完 n 个盒子的方案数:
$$ tmp = x_k - C_{k}^{k-1}x_{k-1} + C_{k}^{k-2}x_{k-2} + … + (-1)^{k}x_1 $$

所以, 答案就是 $C_m^k$ * tmp.

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
62
63
64
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll mod = 1e9 + 7;
const int maxn = 1e6;

int T;
ll p[maxn + 10], invp[maxn + 10], inv[maxn + 10];

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

void init() {
    p[0] = 1;
    for (int i = 1; i <= maxn; i++) {
        p[i] = p[i - 1] * i % mod;
    }   
    invp[maxn] = qp(p[maxn], mod - 2);
    for (int i = maxn - 1; i >= 0; i--) {
        invp[i] = invp[i + 1] * (i + 1) % mod;
    }
    inv[1] = 1;
    for (int i = 2; i <= maxn; i++) {
        inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
    }
}

int C(ll n, ll m) {
    return p[n] * invp[m] % mod * invp[n - m] % mod;
}

int main() {
    init();
    scanf("%d", &T);
    while (T--) {
        ll n, m, k;
        scanf("%lld %lld %lld", &n, &m, &k);
        ll Cmk = 1;
        for (int i = 1; i <= k; i++) {
            Cmk = Cmk * (m - k + i) % mod * inv[i] % mod;
        }
        ll tmp = 0;
        for (int i = 0; i < k; i++) {
            if (i % 2 == 0) {
                tmp = (tmp + C(k, k - i) * (k - i) % mod * qp(k - i - 1, n - 1) % mod + mod) % mod;
            }
            else {
                tmp = (tmp - C(k, k - i) * (k - i) % mod * qp(k - i - 1, n - 1) % mod + mod) % mod;
            }
        }
        ll ans = Cmk * tmp % mod;
        printf("%lld\n", ans);
    }
    return 0;
}