
 /**//*
題意: 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
搜索
最新評論

|
|