题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3380
题意：有m种不同的元素，每种元素都有n种不同的相位，现在假设有每种元素各一个，其相位是等概率随机的。如果几个元素的相位相同，那么帕琪就可以把它们组合发动一个符卡(Spell Card)。现在问帕琪能够发动等级不低于l，即包含l个相同相位的不同元素的附卡的概率。
首先所有的总数是n^m，然后只要求满足情况的数目了，对于 l >m/2我们可以直接用组合数来求的，即n*Σ( C(m,i)*(n-1)^(m-i) )，如果 l <= m/2就麻烦一些了，因为这里存在重复的情况，组合数求比较麻烦，于是我们可以用DP，f[i][j]表示前 i 个数放在 j 个位置并且相同的元素个数小于 l 的数目，f[i][j]=sum{dp[i-1][j-k]*choose[m-(j-k)][k] | k≤j && k<l}。然后这题大数，直接用Java了。。。
上面是O(nml)的复杂度，还有一个O(mml)的：
dp[i,j] 表示用i个数字在m个里放了j个位置，i表示有i个，不一定是[1,i]
dp[i,j] = ∑ dp[i-1,j-k]*C[m-(j-k),k]*(n-(i-1)) 1≤k≤j , k<l
最后答案为 ∑ dp[i,m]/i! 刚才用到的是乘法原理，是排列，要转化为组合数！
//STATUS:Java_AC_1240MS_20194KB
import java.util.*;
import java.math.*;
import java.io.*;
import java.text.*; public class Main {
static final int N=101;
static BigInteger[][] f=new BigInteger[N][N];
static BigInteger[][] C=new BigInteger[N][N];
public static void main(String args[]){
Scanner cin = new Scanner (new BufferedInputStream(System.in));
int i,j,k;
for(i=0;i<N;i++)C[i][0]=C[i][i]=BigInteger.valueOf(1);
for(i=2;i<N;i++){
for(j=1;j<i;j++)
C[i][j]=C[i-1][j-1].add(C[i-1][j]);
}
int n,m,l;
BigInteger tot,cnt;
while(cin.hasNext())
{
m=cin.nextInt();
n=cin.nextInt();
l=cin.nextInt();
if(l>m){
System.out.println("mukyu~");
continue;
}
tot=BigInteger.valueOf(n);
tot=tot.pow(m);
cnt=BigInteger.ZERO;
if(l>m/2){
for(i=l;i<=m;i++){
cnt=cnt.add(C[m][i].multiply( BigInteger.valueOf(n-1).pow(m-i) ));
}
cnt=cnt.multiply(BigInteger.valueOf(n));
}
else {
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)f[i][j]=BigInteger.ZERO;
f[0][0]=BigInteger.ONE;
for(i=1;i<=n;i++){
for(j=0;j<=m;j++){
for(k=0;k<=j && k<l;k++){
f[i][j]=f[i][j].add(f[i-1][j-k].multiply(C[m-j+k][k]));
}
}
}
cnt=tot;
cnt=cnt.subtract(f[n][m]);
}
BigInteger t=cnt.gcd(tot);
cnt=cnt.divide(t);
tot=tot.divide(t); System.out.println(cnt+"/"+tot);
}
}
}