zoj3380 Patchouli's Spell Cards

本文主要是介绍zoj3380 Patchouli's Spell Cards，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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~

当l>m明显无解，l>m/2,可直接用组合数求出，当l<=m/2,这里就不能用组合数求了，因为，这里会有重复，用dp[i][j]表示前i个数字，第j位，满足某个数字小于l的个数，那么我们可以得出dp[i][j]=dp[i][j-k]c[m-j+k][k],也就是第i个数字，可以放１－k个位置，这样就可以得出答案了！

import java.math.BigInteger;
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner a=new Scanner(System.in);int M=150;BigInteger dp[][]=new  BigInteger[150][150];BigInteger an[][]=new  BigInteger[150][150];BigInteger one ,zero;one=BigInteger.ONE;zero=BigInteger.ZERO;for(int i=0;i<120;i++){dp[i][i]=dp[i][0]=dp[0][i]=one;for(int j=1;j<i;j++){dp[i][j]=dp[i-1][j-1].add(dp[i-1][j]);}}while(a.hasNext()){int m,n,l;BigInteger ans,nn,mm,ll,all,gcd;m=a.nextInt();n=a.nextInt();l=a.nextInt();nn=BigInteger.valueOf(n);mm=BigInteger.valueOf(m);ll=BigInteger.valueOf(l);ans=nn.pow(m);if(l>m){System.out.print("mukyu~\n");continue;}if(l>m/2){all=zero;for(int i=l;i<=m;i++){all=all.add(dp[m][i].multiply(BigInteger.valueOf(n-1).pow(m-i)));}all=BigInteger.valueOf(n).multiply(all);gcd=ans.gcd(all);System.out.println(all.divide(gcd)+"/"+ans.divide(gcd));continue;}for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)an[i][j]=zero;an[0][0]=one;	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){for(int k=0;k<=j&&k<l;k++){an[i][j]=an[i][j].add(an[i-1][j-k].multiply(dp[m-j+k][k]));}}all=zero;for(int i=1;i<=n;i++){all=all.add(an[i][m]);}all=ans.subtract(all);gcd=ans.gcd(all);System.out.println(all.divide(gcd)+"/"+ans.divide(gcd));}}}

这篇关于zoj3380 Patchouli's Spell Cards的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---