题目大意：
对n个排成一排的物品涂色，有m种颜色可选。
要求相邻的物品颜色不相同，且总共恰好有K种颜色，问所有可行的方案数
分析：
从m种颜色中选出k种，有c(m,k)种方法，那么我们只用考虑 k种颜色的涂法即可
显然第一个物品有k种涂法，后面的因为不能跟前面的相同都只有k-1种涂法
因此容易想到一个公式：k*(k-1)^(n-1)
但是这个公式算的是 不超过k种颜色的涂法，题目要求必须k种，怎么办呢？
先考虑一个简化版的问题：
用而且用完5种颜色涂不相关的五个物品的方案数
用阶乘的方法可以算出 ans=120，换一种思路呢想一想这个问题，容易想到
ans（取五种颜色）=5^5（取不大于5种颜色）-c(5,4)*4^5（取不大于4种颜色）
可是一算发现ans竟然小于0了，这是怎么回事呢？容易发现其实取小于四种颜色的方案被减重复了
于是想到需要容斥
ans=c(5,5)*5^5-c(5,4)*4^5+c(5,3)*3^5-c(5,2)*2^5+c(5,1)*1^5 =120
这个问题解决了。原问题也就差不多了。。
代码：
#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
using namespace std;
const long long mod=;
const long long ny=;
long long n,m,k;
long long cm[];
long long cn[];
long long ck[];
long long inv[];
long long mo(long long x)
{
while(x<)
x+=mod;
return x%mod;
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
if(a==&&b==) return -;
if(b==){x=;y=;return a;}
long long d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
long long Inv(long long a,long long n)
{
long long x,y;
long long d=exgcd(a,n,x,y);
if(d==) return (x%n+n)%n;
else return -;
}
long long quickmod(long long a,long long b,long long m) //a^b%m
{
long long res=;
while(b)
{
if(b&)
res=res*a%mod;
b>>=;
a=a*a%mod;
}
return res;
}
void ini()
{
cn[]=cm[]=;
memset(cm,,sizeof(cm));
cm[]=;
int tmp=min(m/,k);
for(int i=;i<=tmp;i++)
{
cm[i]=(cm[i-]*(m+-i)%mod*inv[i])%mod;
}
if(cm[k]==)
cm[k]=cm[m-k];
ck[]=ck[k]=;
for(int i=;i<=k/;i++)
{
ck[i]=(ck[i-]*(k+-i)%mod*inv[i])%mod;
ck[k-i]=ck[i];
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
inv[]=;
for(int i=;i<=;i++)
{
inv[i]=Inv(i,mod);
}
int t;
scanf("%d",&t);
int cas=;
while(t--)
{
cas++;
scanf("%I64d%I64d %I64d",&n,&m,&k);
ini();
long long ans=;
long long p=;
for(int i=k;i>=;i--)
{
ans=(ans+p*((ck[k-i])*i%mod*quickmod(i-,n-,mod)%mod)+mod)%mod;
p=-p;
}
ans=(ans*cm[k])%mod;
printf("Case #%d:%c%I64d\n",cas,' ',ans);
}
return ;
}