题意:有N朵花,在M种颜色中选择恰好k种不同的颜色,将这N朵花染色,要求相邻的两朵花颜色不相同.
分析:若限制改为选择不超过k种颜色将N朵花朵染色,则方案数\(f(N,k) = k*(k-1)^{N-1}\),第一朵可以在k个颜色中任意选择,第二朵可以有k-1个选择,第三朵也有k-1....
但是f(N,k)种方案中包含了使用了少于k个颜色的方案数,要减去这些方案数.设没有使用的颜色数为i,当i=1时,减去只使用1种颜色的方案数\(C(k,1)*f(N,k-1)\);当i=2时,方案数已经被i=1时重复减去了一遍,所以要加回... 根据容斥原理,需要减去的方案数为
\[ tmp = -\sum_{i=1}^{k-2}(-1)^{i}*C(k,i)*f(N,k-i)\]
\(f(N,k) - tmp\)得到用k种颜色染色的方案.
因为k种颜色是在M种颜色中任选,所以最后的答案是
\[ans = C(M,k)*(f(N,k)-tmp))\]
因为该题M和N很大,所以最后一步的组合数需要用卢卡斯取模.
中间过程的\(C(k,i),k\)恒定,因为\(k\leq 1e6\),可以预处理出阶乘的逆元,对每组数据,\(O(k)\)处理出所有k为底的组合数.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e6+5;
LL mod = 1e9+7;
LL fac[MAXN], inv[MAXN];
LL Comb[MAXN];
LL qpow(LL x, LL n, LL p)
{
LL res=1;
while(n){
if(n&1) res= res *x % p;
x= x*x %p;
n>>=1;
}
return res;
}
void pre()
{
fac[0] = fac[1] = 1;
for(int i = 2;i<MAXN; ++i){
fac[i] = i*fac[i-1] %mod;
}
inv[MAXN-1] = qpow( fac[MAXN-1], mod-2 ,mod);
for(int i= MAXN-2; i>=0; --i){
inv[i] = (i+1) * inv[i+1] % mod;
}
}
void pre_Ck(LL k)
{
LL pt = 1;
for(int i=1 ;i<=k ;++i) pt = pt * i % mod;
for(int i=0 ;i<=k ;++i){
Comb[i] = pt * inv[i] %mod * inv[k-i] %mod;
}
}
LL C (LL a, LL b, LL p) {
if (a < b) return 0;
if (b > a - b) b = a - b;
LL up = 1, down = 1;
for (LL i = 0; i < b; i++) {
up = up * (a-i) % p;
down = down * (i+1) % p;
}
return up * qpow(down, p-2, p) % p; // 逆元
}
LL lucas (LL a, LL b, LL p) { //卢卡斯组合数取模
if (b == 0)
return 1;
return C(a%p, b%p, p) * lucas(a/p, b/p, p) % p;
}
LL f(LL n , LL k)
{
return k * qpow(k-1,n-1,mod) %mod;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
LL N,M,k;
pre();
int T,cas=1; scanf("%d", &T);
while(T--){
scanf("%lld %lld %lld",&N, &M ,&k);
pre_Ck(k);
LL res = f(N,k);
LL tmp =0;
for(int i= 1;i<=k-2;++i){
if(i&1 ) tmp = (tmp + Comb[i] * f(N,k-i) %mod) %mod;
else tmp = (tmp + mod - Comb[i]* f(N,k-i) %mod) %mod;
}
res = (res + mod - tmp) % mod * lucas(M, k, mod) %mod;
printf("Case #%d: %lld\n",cas++,res);
}
return 0;
}