http://acm.hdu.edu.cn/showproblem.php?pid=6143
题意：
用m个字母去取名字，名字分为前后两部分，各由n个字符组成，前后两部分不能出现相同字符，问合法的组成有多少种。
思路：
$C(m,i)$表示前面用i种字母组成，那么后面的情况就是可以随便用剩下的m-i种字母，总的方法数也很简单，就是$(m-i)^{n}$。
现在问题是怎么计算用i种字母组成n长度的字符串个数？
容斥原理。$i^n-inom{i}{1}(i-1)^n+inom{i}{2}(i-2)^n-inom{i}{3}(i-3)^n+...$
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int,ll> pll; 15 const int INF = 0x3f3f3f3f; 16 const int maxn=2000+5; 17 const int mod=1e9+7; 18 19 int n, m; 20 ll c[maxn][maxn]; 21 ll mul[maxn][maxn]; 22 23 void init() 24 { 25 memset(c,0,sizeof(c)); 26 for(int i=0;i<=2000;i++) 27 { 28 c[i][0]=1; 29 for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod; 30 } 31 } 32 33 ll qpow(ll x, ll n) 34 { 35 if(mul[x][n]) return mul[x][n]; 36 ll ans=1,aa=x,bb=n; 37 while(n) 38 { 39 if(n&1) ans=ans*x%mod; 40 x=x*x%mod; 41 n>>=1; 42 } 43 mul[aa][bb]=ans; 44 return ans; 45 } 46 47 ll calc(ll x) 48 { 49 ll tmp=0; 50 for(int i=0;i<=x;i++) 51 { 52 if(i&1) tmp=(tmp-c[x][i]*qpow(x-i,n)%mod+mod)%mod; 53 else tmp=(tmp+c[x][i]*qpow(x-i,n)%mod)%mod; 54 } 55 return tmp; 56 } 57 58 int main() 59 { 60 //freopen("in.txt","r",stdin); 61 init(); 62 int T; 63 scanf("%d",&T); 64 while(T--) 65 { 66 ll ans=0; 67 scanf("%d%d",&n,&m); 68 for(int i=1;i<m && i<=n ;i++) 69 { 70 ans=(ans+(c[m][i]*calc(i)%mod)*qpow(m-i,n)%mod)%mod; 71 } 72 printf("%lld ",ans); 73 } 74 return 0; 75 }