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~

題意:

抽象的來說，就是給你M個(gè)不同的球，N種顏色，現(xiàn)在給球染色，問至少有L個(gè)球同一種顏色的概率。

解法：

總方案數(shù)很好算，為N^M，剩下的就是求至少L個(gè)球同色的方案數(shù)，其可以轉(zhuǎn)換為 （總方案數(shù)-每種顏色至多L-1個(gè)球的方案數(shù)）。

然后就是很明顯的DP了，DP[I][J]表示已放完I種顏色，剩下J個(gè)球的方案數(shù)，那么轉(zhuǎn)移方程為

DP[I+1][J-K]+=DP[I][J]*C（J,K） 其中C()為組合數(shù)，K為當(dāng)前顏色裝的球數(shù)。

tip:

GCD（總方案數(shù)-每種顏色至多L-1個(gè)球的方案數(shù),總方案數(shù)）==GCD（每種顏色至多L-1個(gè)球的方案數(shù),總方案數(shù)）

import java.math.BigInteger; import java.util.Scanner;public class Main {static BigInteger[][] dp = new BigInteger[105][105];static BigInteger[][] c = new BigInteger[105][105];static void init(){c[0][0] = BigInteger.valueOf(1);for(int i = 1; i <= 100; i++){c[i][0] = c[i][i]= BigInteger.valueOf(1);for(int j = 1; j < i; j++)c[i][j] = c[i-1][j-1].add(c[i-1][j]);}}static int min(int x, int y){return x < y ? x : y;}static void solve(int m, int n, int l){BigInteger fm = BigInteger.valueOf(n).pow(m);for(int i = 0; i <= n+1; i++)for(int j = 0; j <= m; j++)dp[i][j] = BigInteger.ZERO;dp[0][m] = BigInteger.ONE;for(int i = 1; i <= n; i++)for(int j = 0; j <= m; j++)for(int k = 0; k <= min(j,min(m,l-1)); k++)dp[i][j-k] = dp[i][j-k].add(dp[i-1][j].multiply(c[j][k]));BigInteger fz = dp[n][0];BigInteger gcd = fm.gcd(fz);fz = fm.subtract(fz).divide(gcd);fm = fm.divide(gcd);System.out.println(fz + "/" + fm);}public static void main(String[] args) {init();Scanner cin = new Scanner(System.in);int m, n, l;while(cin.hasNext()){m = cin.nextInt();n = cin.nextInt();l = cin.nextInt();if(l > m)System.out.println("mukyu~");elsesolve(m, n, l);}cin.close();} }

總結(jié)

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

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