Patchouli's Spell Cards

---

Time Limit: 7 Seconds ???? Memory Limit: 65536 KB

---

Patchouli Knowledge, the unmoving great library, is a magician who has settled down in the Scarlet Devil Mansion (紅魔館). Her specialty is elemental magic employing the seven elements fire, water, wood, metal, earth, sun, and moon. So she can cast different spell cards like Water Sign "Princess Undine", Moon Sign "Silent Selene" and Sun Sign "Royal Flare". In addition, she can combine the elements as well. So she can also cast high-level spell cards like Metal & Water Sign "Mercury Poison" and Fire, Water, Wood, Metal & Earth Sign "Philosopher's Stones" .

Assume that there are m different elements in total, each element has n different phase. Patchouli can use many different elements in a single spell card, as long as these elements have the same phases. The level of a spell card is determined by the number of different elements used in it. When Patchouli is going to have a fight, she will choose m different elements, each of which will have a random phase with the same probability. What's the probability that she can cast a spell card of which the level is no less than l, namely a spell card using at least l different elements.

Input

There are multiple cases. Each case contains three integers 1 ≤ m, n, l ≤ 100. Process to the end of file.

Output

For each case, output the probability as irreducible fraction. If it is impossible, output "mukyu~" instead.

Sample Input

7 6 5 7 7 7 7 8 9

Sample Output

187/15552 1/117649 mukyu~

References

---

Author: WU, Zejun
Source: ACM × Touhou
Contest: ZOJ Monthly, August 2010

?

?

?

/*
?* ZOJ 3380
?* 題目意思：有m個位置，每個位置填入一個數(shù)，數(shù)的范圍是1~n,問至少有L個位置的數(shù)一樣的概率
?* 輸出要是最簡分?jǐn)?shù)的形式，所以用大數(shù)JAVA
?* 至少有L個位置一樣，就是L，L+1，L+2····m個位置一樣。
?* 我們從反面來考慮，總數(shù)是n^m，我們求沒有L個位置一樣的數(shù)的概率
?* 設(shè) dp[i][j]表示用前i個數(shù)，填充j個位置的方案數(shù)（要符合沒有L個位置是一樣的數(shù))
?* dp[i][j]=dp[i-1][j]+Sigm( dp[i-1][j-k]*C[m-(j-k)][k]? ) k<=j&&k<L
?* 其實就是看第i個數(shù)，可以不填，填一個位置，兩個位置······這樣累加過來。
?* 那么最后的答案就是 (n^m-dp[1~n][m])/(n^m)
?*/

?

主要是大數(shù)比較麻煩。所以就用JAVA寫了，當(dāng)是練習(xí)下JAVA吧！

?

/** ZOJ 3380* 題目意思：有m個位置，每個位置填入一個數(shù)，數(shù)的范圍是1~n,問至少有L個位置的數(shù)一樣的概率* 輸出要是最簡分?jǐn)?shù)的形式，所以用大數(shù)JAVA* 至少有L個位置一樣，就是L，L+1，L+2····m個位置一樣。* 我們從反面來考慮，總數(shù)是n^m，我們求沒有L個位置一樣的數(shù)的概率* 設(shè) dp[i][j]表示用前i個數(shù)，填充j個位置的方案數(shù)（要符合沒有L個位置是一樣的數(shù))* dp[i][j]=dp[i-1][j]+Sigm( dp[i-1][j-k]*C[m-(j-k)][k] ) k<=j&&k<L* 其實就是看第i個數(shù)，可以不填，填一個位置，兩個位置······這樣累加過來。* 那么最后的答案就是 (n^m-dp[1~n][m])/(n^m)*/ import java.util.*; import java.io.*; import java.math.*; public class Main {static BigInteger[][] dp=new BigInteger[110][110];static BigInteger[][] C=new BigInteger[110][110];//組合數(shù)public static void main(String arg[]){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 tol=BigInteger.valueOf(N).pow(M);if(L>M){System.out.println("mukyu~");continue;}if(L>M/2)//這個時候可以直接用組合數(shù)求出來 {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(tol);System.out.println(ans.divide(gcd)+"/"+tol.divide(gcd));continue;}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<L&&k<=j;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=tol.subtract(ans);BigInteger gcd=ans.gcd(tol);System.out.println(ans.divide(gcd)+"/"+tol.divide(gcd));}} }

?

總結(jié)

以上是生活随笔為你收集整理的ZOJ 3380 Patchouli's Spell Cards（概率DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。