本文主要是介绍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 个格子,每个格子可以用
解题思路:
考虑 DP ,设 dp[i][j]:用前 i 种颜色涂 j 个格子的概率 (是在 m 个格子中涂
解释:因为第 i 种颜色可以不涂,可以涂一个格子,可以涂两个格子,以此类推。
初始化:
因为结果太大,所以考虑 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 = tmp.gcd(ans);System.out.println(tmp.divide(gcd)+"/"+ans.divide(gcd));}}
}
这篇关于ZOJ 3380 Patchouli's Spell Cards(概率DP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!