ZOJ 3380 Patchouli's Spell Cards（概率DP）

ZOJ 3380 Patchouli's Spell Cards（概率DP）

传送门

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~

题目大意：

题目的原意是比较难理解的，将题目抽象一下：有 m $m$ 个格子，每个格子可以用 n$n$ 种颜色进行涂色，求在这 m $m$ 个格子中颜色相同的格子数目 ≥ L$ge L$ 的概率。

解题思路：
考虑 DP $DP$，设 dp[i][j]：用前 i 种颜色涂 j 个格子的概率 $dp[i][j]：用前 i 种颜色涂 j 个格子的概率$（是在 m $m$ 个格子中涂 j$j$ 个，并不是前 j $j$ 个），那么有：
dp[i][j]=∑k=0k≤jk<ldp[i−1][j−k]∗C[m−(j−k)][k] $$dp[i][j]=sum_{k=0}^{kle j klt l}dp[i-1][j-k]*C[m-(j-k)][k]$$
解释：因为第 i $i$ 种颜色可以不涂，可以涂一个格子，可以涂两个格子，以此类推。
初始化： dp[0][0]=1$dp[0][0]=1$
因为结果太大，所以考虑 java 大数

import java.math.BigInteger;
import java.util.Scanner;public class Main {static BigInteger C[][] = new BigInteger[105][105];public static void Init(){for(int i=0; i<105; i++) for(int j=0; j<105; j++) C[i][j] = BigInteger.ZERO;for(int i=0; i<105; i++) C[i][0] = BigInteger.ONE;for(int i=1; i<105; i++) for(int j=1; j<105; j++) C[i][j]=C[i][j].add(C[i-1][j].add(C[i-1][j-1]));}public static void main(String[] args) {Init();Scanner in = new Scanner(System.in);    while(in.hasNext()){int m, n, l;m = in.nextInt(); n = in.nextInt(); l = in.nextInt();if(l > m){System.out.println("mukyu~");continue;}BigInteger dp[][] = new BigInteger[105][105];for(int i=0; i<105; i++) for(int j=0; j<105; 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.valueOf(n).pow(m);BigInteger tmp = BigInteger.ZERO;for(int i=1; i<=n; i++) tmp = tmp.add(dp[i][m]);tmp = ans.subtract(tmp);BigInteger gcd = d(ans);System.out.println(tmp.divide(gcd)+"/"+ans.divide(gcd));}}
}