UVALive 7040 / Gym 100548F – Color [容斥+数论]

Link

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5052

Mean

有N个格子，现有M种颜色，对这些格子涂色，相邻两个格子不能同色。问恰好用上K种颜色的涂色方法有多少种。

Analysis

14年西安网络赛的题。去年暑假组队赛也打过这道题，学姐推出来了，我写完TLE了，原因是当时不会逆元预处理。

今天用逆元推了一下，发现也不是很难嘛，知识点也学全了…就是一个容斥

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll maxn = 1024000, mod = 1000000007;
ll N, M, K;
ll C[maxn];
ll inv[maxn];

void initInv() {
    inv[1] = 1;
    for (int i = 2; i < maxn; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}

inline ll divMod(ll a, ll b) {
    return a * inv[b] % mod;
}

ll quickpow(ll m, ll y) {
    ll res = 1, base = m;
    while(y > 0) {
        if(y & 1)
            res = (res * base) % mod;
        base = (base * base) % mod;
        y >>= 1;
    }
    return res % mod;
}

void getC(ll n, ll ed) {
    C[0] = 1;
    for(ll i = 1; i <= ed; ++i)
        C[i] = divMod((C[i-1] * (n-i+1)) % mod, i);
}

ll solve() {
    ll sum = 0;
    ll flag = 1;
    for(ll i = 0; i <= K - 1; ++i) {
        ll cur = C[i] * (K - i) % mod;
        cur = cur * quickpow(K - i - 1, N - 1) % mod;
        sum = (sum + flag * cur + mod) % mod;
        flag = -flag;
    }
    return sum;
}


int main() {
    initInv();
    int T, kase = 0; cin >> T;
    while(T--) {
        cin >> N >> M >> K;
        getC(M, K); ll cmk = C[K];
        getC(K, K);
        int ans = (int) (cmk * solve() % mod);
        printf("Case #%d: %d\n", ++kase, ans);
    }
    return 0;
}