/**//* 题意: m个位置,每个位置可以在n中选择(1到n) 问至少有l个数相等的情况 有O(nml)和O(mml)的做法 后者对于n无关,可以处理n很大时 先将问题转化为求没有l个数相等,即有1,2 l-1个相等
O(nml) dp[i,j] 表示用前i个数字在m个里放了j个位置,这些数字不一定都有用到 dp[i,j] = ∑ dp[i-1,j-k]*C[m-(j-k),k] 0≤k≤j , k<l 最后答案为dp[n,m] 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! 刚才用到的是乘法原理,是排列,要转化为组合数!
有些题,dp[i]是由dp[i-1]过来 而这道题是 通过选择放的位置来缩小规模 dp[j] <-- dp[j-k] 用k来控制相等的个数,小于l个即可!! 通过控制状态转移来满足条件!!
*/
import java.math.BigInteger; import java.util.Scanner;
class Main {
static BigInteger[][] C = new BigInteger[110][110]; static BigInteger[][] dp = new BigInteger[110][110];
static void init() { for(int i=0;i<110;i++) C[i][0] = C[i][i] = BigInteger.ONE; for(int i=2;i<101;i++) for(int j=1;j<i;j++) C[i][j] = C[i-1][j].add(C[i-1][j-1]); }
public static void main(String[] args) { init();
Scanner cin = new Scanner(System.in);
while(cin.hasNext()) { int m=cin.nextInt(); int n=cin.nextInt(); int l=cin.nextInt();
if(l>m) { System.out.println("mukyu~"); continue; }
BigInteger total = BigInteger.valueOf(n).pow(m);
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)); continue; }
// dp[i,j] = dp[i-1,j-k]*C[m-(j-k),k]
for(int i=0;i<=n;i++)//O(n*m*l) 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=0;j<=m;j++)//j start from 0 { for(int k=0;k<l&&k<=j;k++) dp[i][j] = dp[i][j].add( dp[i-1][j-k].multiply( C[m-(j-k)][k] ) ); }
/**//* for(int i=1;i<=m&&i<=n;i++)// O(m*m*l) for(int j=1;j<=m;j++) { for(int k=1;k<=j&&k<l;k++)//k start from 1 dp[i][j] = dp[i][j].add( dp[i-1][j-k].multiply(C[m-(j-k)][k]).multiply(BigInteger.valueOf(n-(i-1))) ); }
BigInteger ans = BigInteger.ZERO,f = BigInteger.ONE; for(int i=1;i<=m;i++) { ans = ans.add(dp[i][m].divide(f));// remember to divide : change permutation to combination!! f=f.multiply(BigInteger.valueOf(i+1)); } */
BigInteger ans = total.subtract(dp[n][m]); BigInteger gcd = ans.gcd(total);
System.out.println(ans.divide(gcd) + "/" + total.divide(gcd)); } } }
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|