11月11日, 2016 4,939 views次
Link
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; }