传送门
题意简述：对n个排成一排的物品涂色，有m种颜色可选。
要求相邻的物品颜色不相同，且总共恰好有K种颜色，问所有可行的方案数。（n,m≤1e9,k≤1e6n,m\le1e9,k\le1e6n,m≤1e9,k≤1e6）
思路：
容斥原理套路：
先不考虑是否选全kkk种颜色，方案数为Cmk∗k∗(k−1)n−1C_m^k*k*(k-1)^{n-1}Cmk∗k∗(k−1)n−1。
然后枚举剩下的至少有几种颜色没选来容斥掉非法情况：
于是Ans=Cmk∑i=k1(−1)k−iCkii(i−1)n−1Ans=C_m^k\sum_{i=k}^1(-1)^{k-i}C_k^ii(i-1)^{n-1}Ans=Cmk∑i=k1(−1)k−iCkii(i−1)n−1
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=1e6+5,mod=1e9+7;
typedef long long ll;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}
int n,m,k,C[N],inv[N],mult;
inline void init(){
inv[1]=1;
for(ri i=2;i<=1000000;++i)inv[i]=mul(inv[mod-mod/i*i],mod-mod/i);
}
inline void Init(){
C[0]=1,mult=1;
for(ri i=1;i<=k;++i)C[i]=mul(mul(C[i-1],k-i+1),inv[i]);
for(ri i=1;i<=k;++i)mult=mul(mult,mul(m-i+1,inv[i]));
}
int main(){
init();
for(ri ans,tt=1,up=read();tt<=up;++tt){
n=read(),m=read(),k=read(),ans=0;
Init();
for(ri i=k,tmp;i;--i){
tmp=mul(C[i],mul(i,ksm(i-1,n-1)));
ans=(k-i)&1?dec(ans,tmp):add(ans,tmp);
}
cout<<"Case #"<<tt<<": "<<mul(mult,ans)<<'\n';
}
return 0;
}