题目大意：
用(1 2 3 … n) n个数填充 m个位置，问最少相同的数字出现的数量不少于I 的概率
思路分析：
逆向思考，求铺满最多的数量不够I 个的方案数。
每次用一个数字去铺，铺M个位置，，每个数字最多铺 不够I个。
dp[i][j]表示枚举到了第i个数字，前i个数字铺了j个位置的方案数。
考虑到组合计数
用Java
import java.util.*;import java.io.BufferedInputStream;import java.math.*;public class Main{static BigInteger [][] C = new BigInteger[110][110];static BigInteger [][] dp = new BigInteger[110][110];public static void main(String args[]){Scanner cin = new Scanner(new BufferedInputStream(System.in));for(int i=0;i<105;i++){C[i][0]=C[i][i]=BigInteger.ONE;for(int j=1;j<i;j++){C[i][j] = C[i-1][j-1].add(C[i-1][j]);}}int n,m,l;while(cin.hasNext()){m = cin.nextInt();n = cin.nextInt();l = cin.nextInt();BigInteger total = BigInteger.valueOf(n).pow(m);if(m<l){System.out.println("mukyu~");continue;}else if(l>m/2){BigInteger ans = BigInteger.ZERO;for(int i=l;i<=m;i++){ans = ans.add(C[m][i].multiply(BigInteger.valueOf(n-1).pow(m-i)));}ans = ans.multiply(BigInteger.valueOf(n));BigInteger gcd = ans.gcd(total);System.out.println(ans.divide(gcd)+"/"+total.divide(gcd));}else {for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)dp[i][j] = BigInteger.ZERO;}dp[0][0] = BigInteger.ONE;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=0;k<=j&&k<l;k++){dp[i][j] = dp[i][j].add(dp[i-1][j-k].multiply(C[m-(j-k)][k]));}}}BigInteger ans = BigInteger.ZERO;for(int i=1;i<=n;i++){ans = ans.add(dp[i][m]);}ans = total.subtract(ans);BigInteger gcd = ans.gcd(total);System.out.println(ans.divide(gcd)+"/"+total.divide(gcd));}}}}
有的旅行时为了寻找逝去的年华，重温青春的惆怅。
