2014-2015 ACM-ICPC, Asia Xian Regional Contest 【Color】

发表于 | 更新于 | 分类于 ，

$\large\mathcal{Description}$

题意 $:$ 从 $m$ 种颜色中取恰好 $k$ 种颜色给排成一排的 $n$ 朵花染色，使相邻花朵的颜色不同。求方案数。(两种方案不同，当且仅当至少有一朵花的颜色不同)

$\Large{☞}$ 提交通道 ($F$ 题)

$\large\mathcal{Solution}$

首先，从 $m$ 种颜色中选出 $k$ 种。很显然，有 $C_m^k$ 种方案。

然后考虑如何选恰好 $k$ 种。

$k \times (k - 1)^{n-1}$ 是至多选 $k$ 种的方案数，而不是恰好选 $k$ 种的方案数。

然后，一个很自然的想法 $:$ 至多选 $k$ 种的方案数减去至多选 $(k - 1)$ 种的方案数。

于是熟练地敲完代码，测一发样例，错了！！！

为什么这个想法是错的呢？

同一个 $(k - 2)$ 种的状态会被 $2$ 个 $(k - 1)$ 种的状态所包含。所以会多减。

因此，需要容斥。

$\large\mathcal{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
#include <iostream>
#include <cstdio>
#include <algorithm>

template <typename Tp>
inline void read(Tp &x) {
    x = 0;
    bool f = true; char ch = getchar();
    for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
    for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
    x = f ? x : -x;
}

const int N = 1e6 + 7, P = 1e9 + 7;

int Fac[N], iFac[N];

inline int Power(int a, int x) {
    int ret = 1;
    while (x) {
        if (x & 1) ret = 1LL * ret * a % P;
        a = 1LL * a * a % P;
        x >>= 1;
    }
    return ret;
}

inline int Inv(int x) {
    return Power(x, P - 2);
}

inline int C(int n, int m) {	
    if (n < 0 || m < 0 || m > n) return 0;
    return 1LL * Fac[n] * iFac[n - m] % P * iFac[m] % P;
}

inline int _C(int n, int m) {
    if (n < 0 || m < 0 || m > n) return 0;
    int s1 = 1, s2 = 1;	
    for (int i = n; i > n - m; --i) s1 = 1LL * s1 * i % P;
    for (int i = 1; i <= m; ++i) s2 = 1LL * s2 * i % P;
    return 1LL * s1 * Inv(s2) % P;
}

int main() {
    Fac[0] = 1;
    for (int i = 1; i < N; ++i) Fac[i] = 1LL * Fac[i - 1] * i % P;
    iFac[N - 1] = Inv(Fac[N - 1]);
    for (int i = N - 2; i >= 0; --i) iFac[i] = 1LL * iFac[i + 1] * (i + 1) % P;
    int T;
    read(T);
    for (int Case = 1; Case <= T; ++Case) {
        int n, m, k;
        read(n), read(m), read(k);
        int Ans = 0;
        for (int i = 0; i < k; ++i) Ans = ((Ans + 1LL * (i & 1 ? -1 : 1) * C(k, i) % P * (k - i) % P * Power(k - i - 1, n - 1) % P) % P + P) % P;
        printf("Case #%d: %d\n", Case, (int)(1LL * Ans * _C(m, k) % P));
    }
    return 0;
}