
 /**//*
题意: 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
搜索
最新评论

|
|