题目大意：
对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=1000000007; const long long ny=500000004; long long n,m,k; long long cm[1000010]; long long cn[1000010]; long long ck[1000010]; long long inv[1000010]; long long mo(long long x) { while(x<0) x+=mod; return x%mod; } long long exgcd(long long a,long long b,long long &x,long long &y) { if(a==0&&b==0) return -1; if(b==0){x=1;y=0;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==1) return (x%n+n)%n; else return -1; } long long quickmod(long long a,long long b,long long m) //a^b%m { long long res=1; while(b) { if(b&1) res=res*a%mod; b>>=1; a=a*a%mod; } return res; } void ini() { cn[0]=cm[0]=1; memset(cm,0,sizeof(cm)); cm[0]=1; int tmp=min(m/2,k); for(int i=1;i<=tmp;i++) { cm[i]=(cm[i-1]*(m+1-i)%mod*inv[i])%mod; } if(cm[k]==0) cm[k]=cm[m-k]; ck[0]=ck[k]=1; for(int i=1;i<=k/2;i++) { ck[i]=(ck[i-1]*(k+1-i)%mod*inv[i])%mod; ck[k-i]=ck[i]; } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); inv[1]=1; for(int i=2;i<=1000000;i++) { inv[i]=Inv(i,mod); } int t; scanf("%d",&t); int cas=0; while(t--) { cas++; scanf("%I64d%I64d %I64d",&n,&m,&k); ini(); long long ans=0; long long p=1; for(int i=k;i>=1;i--) { ans=(ans+p*((ck[k-i])*i%mod*quickmod(i-1,n-1,mod)%mod)+mod)%mod; p=-p; } ans=(ans*cm[k])%mod; printf("Case #%d:%c%I64d ",cas,' ',ans); } return 0; }