挣扎了好几天终于把这一题过了。。比赛的时候RP低到爆忘记带费马小定理和快速幂的模板，好不容易YY出了一个组合数的求法，然后发现公式推错了，最后呵呵呵呵。><
一开始的想法是C(m,k)k(k-1)^(n-1)，但是这种case包括的是颜色数<=k的情形，所以还要减去颜色数<=(k-1)的情形。
C(m,k)[k(k-1)^(n-1)-(k-1)(k-2)^(n-1)]
下面考虑这种case，如果选取的k个颜色是1,2,3,4，那么会有一种染色方案是1,2,1,2...，如果选取的k-1个颜色是1,2,3，那么仍然会包含一种染色方案1,2,1,2...所以上面的公式减多了，还要再加上颜色数<=(k-2)的case，然后再减去颜色数<=(k-3)的case。
考虑有k种颜色时的染色方案：sum (-1)^i*C(k,i)*(k-i)*(k-i-1)^(n-1) for i=0,1,...,k
总共有m种颜色可以选择，所以再乘上C(m,k)即可。
因为涉及到组合数取模，所以需要求逆元，因为只有乘法才可以边乘边取模。由于1e9+7是质数，求逆元可以用用费马小定理，a^(p-1)=1%p
那么a^(p-1)/a =a^(p-2)= 1/a%p ，其中gcd(a,p)=1，p is a prime。最后用快速幂求解即可。
1,2,3....的逆元可以预处理。组合数可以递推求解。
一直WA on test 2 ，最后发现是相乘的过程中少%mod，估计是中途爆long long了。难怪小数据对拍都查不出来==
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<ctype.h>
#include<map>
#include<time.h>
#include<bitset>
using namespace std;
//Xi'an Reigonal F
int T;
long long n;
long long m;
long long k;
const long long mod=1000000007;
const int maxn=1000010;
long long comb[maxn];
long long inv[maxn];
long long ans;
long long pow_mod(long long a,long long b)
{
long long s=1;
long long t=1;
while(b)
{
if(b&t)
{
s=(s*a)%mod;
}
a=(a*a)%mod;
b=b>>1;
}
return s;
}
void cal_inv()
{
for(int i=1;i<maxn;i++)
{
inv[i]=pow_mod(i,mod-2)%mod;
}
}
void cal_comb(long long m0,long long k0)//C(m,0),C(m,1),C(m,2)....C(m,k)
{
comb[0]=1;
for(long long i=1;i<=k0;i++)
{
comb[i]=((comb[i-1]*(m0-i+1))%mod)*inv[i]%mod;
//cout<<i<<" " <<comb[i]<<endl;
}
}
void solve()
{
cal_comb(m,k);
ans=comb[k]%mod;
memset(comb,0,sizeof(comb));
long long ret=1;
cal_comb(k,k);
long long tmp=0;
// for(int i=k;i>0;i--) //equivalent to the following one, if we replace i with k-j
// {
// tmp+=ret*i*pow_mod(i-1,n-1)%mod*comb[i]%mod;
// tmp=(tmp+mod)%mod;
// ret=-ret;
// }
for(long long i=0;i<=(k-1);i++)
{
tmp+=ret*(k-i)*comb[i]%mod*pow_mod(k-i-1,n-1)%mod;//之前写成了tmp+=ret*comb[i]%mod*(k-i)*pow_mod(k-i-1,n-1);然后一直WA on test 2，估计是中间的相乘爆long long了。
//tmp+=ret*comb[i]%mod*(k-i)%mod*pow_mod(k-i-1,n-1)%mod; //it‘s also ok.
tmp=(tmp+mod)%mod;
ret=-ret;
}
ans=(ans*tmp)%mod;
}
int main()
{
//freopen("input.txt","r",stdin);
freopen("data.txt","r",stdin);
freopen("out1.txt","w",stdout);
scanf("%d",&T);
memset(inv,0,sizeof(inv));
cal_inv();
for(int ca=1;ca<=T;ca++)
{
memset(comb,0,sizeof(comb));
ans=1;
scanf("%I64d %I64d %I64d",&n,&m,&k);
if(n==1&&m==1)
{
ans=1;
}
else
{
solve();
}
printf("Case #%d: %I64d\n",ca,ans);
}
return 0;
}
顺便再附上暴力打表验证的的代码，其实数据大一点基本就跑不出来了==
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<stdlib.h>
#include<stdio.h>
#include<queue>
#include<cstring>
#include<time.h>
using namespace std;
//Xi'an Reigonal F BF
const int maxn=1000010;
int T;
int n;
int m;
int k;
long long ans;
int s[maxn];
int used[maxn];
void dfs(int dep)
{
if(dep==n)
{
memset(used,0,sizeof(used));
int cnt=0;
for(int i=1;i<=n;i++)
{
int t=s[i];
if(used[t]==0)
{
cnt++;
used[t]=1;
}
}
if(cnt==k)
{
ans++;
for(int i=1;i<=n;i++)
{
printf("%d ",s[i]);
}
puts("");
}
return;
}
for(int i=1;i<=m;i++)
{
if(s[dep]!=i)
{
s[dep+1]=i;
dfs(dep+1);
s[dep+1]=0;
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
freopen("data.txt","r",stdin);
freopen("out2.txt","w",stdout);
scanf("%d",&T);
for(int ca=1;ca<=T;ca++)
{
scanf("%d %d %d",&n,&m,&k);
ans=0;
memset(s,0,sizeof(s));
dfs(0);
printf("Case #%d: %I64d\n",ca,ans);
}
return 0;
}