2014 ICPC 西安区域赛 F - color 容斥原理

传送门：http://codeforces.com/gym/100548/attachments

题意

给n朵花，m种颜色，让你在m种颜色种选择k种在n多花种涂色，k种的每一种都要用到，而且相邻的花不能涂相同的颜色。问有多少种涂色方法？

思路

首先可知，m种选k种有$C_m^k$，然后每个人都可以想到这样的公式：$C_m^k*k*(k-1)^{n-1}$。 这个式子是说明n朵花中有涂大于1种并且小于等于k种颜色，也就是2，3…k-1，k种颜色的方案都有，而我们只要整好k种，那该怎么半呢？答案就是容斥。

怎么个容斥法呢？

例如有4种颜色1，2，3，4，在里面找3种颜色涂，可以找（1，2，3）和（1，2，4）。 根据$k*(k-1)^{n-1}$： 在（1，2，3）中，你会选择（1，2）这个方案，因为是小于等于k种，而在（1，2，4）中你也会选择（1，2）这个方案，所以我们重复选择了，需要把这种减掉。

学过容斥的都知道，容斥就是干这个事情的，那该怎么减去重复呢？

那就是k种的减去k-1种的，然后在加上k-2种的，就这样一加一减，减是因为要减掉重复的，加是因为把需要的也给减掉了，所以需要加上，容斥都是这个道理，总式子如下所示：

$$C_m^k\left ( \sum_{i=1}^k(-1)^{k-i+1}C_k^i*i*(i-1)^{n-1} \right ) $$

O(n)预处理阶乘和阶乘逆元，方便组合数O(1)求出，$C_m^k$由于m太大，数组存不下，但是k只有1e6，所以直接暴力算就可以了，$C_m^k=\frac{m!}{k!(m-k)!}=invF[k]*\prod_{i=m-k+1}^mi$，次幂直接快速幂即可。复杂度为$O(n)+O(Tn\log n)$

Code（1996ms）

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
const ll mod = 1e9 + 7;
// const double eps = 1e-6;
// const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;

const int N = 1e6 + 10;
ll f[N], invF[N];

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

void Init() {
    f[0] = f[1] = invF[0] = invF[1] = 1;
    for(int i = 2;i < N; i++){
        f[i] = f[i - 1] * i % mod;
    }
    invF[N - 1] = quick_pow(f[N - 1], mod - 2);
    for(int i = N - 2;i >= 0; i--) {
        invF[i] = (invF[i + 1] * (i + 1)) % mod;
    }

}

ll C(ll m, ll n) {
    if(m < 0  n < 0  n > m)
        return 0;
    ll ans = f[m];
    ans = ans * invF[n] % mod;
    ans = ans * invF[m - n] % mod;
    return ans;
}

ll rongchi(ll n, ll k) {
    int opt = 1;
    ll ans = 0;
    for(ll i = k;i >= 1; i--) {
        ll res = 1ll * opt * i * quick_pow(i - 1, n - 1) % mod * C(k, i) % mod;
        ans = (ans + res + mod) % mod;
        opt *= -1;
    }
    return (ans % mod + mod) % mod;
}

void solve() {
    Init();
    int _;
    scanf("%d",&_);
    int Case = 1;
    while(_--) {
        ll n, m, k;
        scanf("%lld%lld%lld",&n,&m,&k);
        ll ans = rongchi(n, k);
        for(ll i = m - k + 1;i <= m; i++) ans = ans * i % mod;
        ans = ans * invF[k] % mod;
        printf("Case ##%d: %lld\n",Case++,ans);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    signed test_index_for_debug = 1;
    char acm_local_for_debug = 0;
    do {
        if (acm_local_for_debug == '$') exit(0);
        if (test_index_for_debug > 20)
            throw runtime_error("Check the stdin!!!");
        auto start_clock_for_debug = clock();
        solve();
        auto end_clock_for_debug = clock();
        cout << "Test " << test_index_for_debug << " successful" << endl;
        cerr << "Test " << test_index_for_debug++ << " Run Time: "
             << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
    solve();
##endif
    return 0;
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/11/15/2014-icpc-西安区域赛-f-color-容斥原理/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！