首页 > 代码库 > HDU 4043 FXTZ II （组合数学-排列组合）
HDU 4043 FXTZ II （组合数学-排列组合）
FXTZ II
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 498 Accepted Submission(s): 266
Sanae is a ChuShou(master) of the game while Cirno is a ShaBao(noob). Since Cirno is a ShaBao, she just presses a random key on the keyboard for every 0.5 second, expecting to make a BiShaJi.
The battle begins. Having tried exactly 9 times, she finally makes a BiShaJi! She find herself summoned N iceballs!!! Then Sanae‘s HP decreases to 0 immediately....It should have been like that. But Cirno is too simple, always navie. She doesn‘t know how to handle the iceballs, so she starts to press the keyboard at random, again.
Let‘s see how the iceball damages. Each iceball has a fixed energy: the first ball‘s energy is 2^0, the second ball‘s energy is 2^1,..., and the N-th ball‘s energy is 2^(N-1). The damage caused by an iceball is equal to its energy. Cirno will shoot N times. Since Cirno is pressing the keyboard at random, each time Cirno will choose exactly one iceball with equal possibility to shoot out. Once shot out, the iceball can‘t be chosen again. And even worse, the target may be either her opponent or herself, with equal possibility(50%). What a big ShaBao she is. =_=
During shooting, once Cirno‘s HP is less than Sanae‘s, she will lose the game. Otherwise, she wins.
You may assume Sanae did nothing while Cirno‘s shooting(all damages are caused by Cirno‘s iceball), and their original HP are both 2^N (No one will die in the middle of the battle unless Cirno‘s HP is less than Sanae‘s).
Here comes the question: Can you calculate the possibility of Cirno‘s victory?
For each case, the only line contains one integer N(0<N<=500), indicating the number of iceballs.
2 1 4
1/2 35/128
题目大意：
解题思路：有n个能量球，能量分别为 2^0,2^1,2^2,........2^n-1
这个人每次随机选择一个能量球概率相同，选择后的可以看作消失了不能再被选，打中自己和敌人的概率都是50%，
过程中，一旦自己的血量小于对方就算输了，问自己赢的概率。
解题代码：这题是分析概率题
首先，拿到题目，看到的输出样式是分子除以分母，这样的格式的话，不能只求概率，要用方法数来算
（1）可以确定的是为化简的分母，也就是总方法数，应该是 n 个雪球全排列后，然后再决定每个雪球打在谁身上。
也就是 n! * 2^n
（2）现在来分析分子，也就是赢的方法数
现在n个雪球排列好了在一排，
可以肯定的是第n个雪球是打在对方身上 ，否则我必输
因为第n个雪球的能量是2^(n-1) 大于剩下的 n-1 个球的能量总和
所以根据第n个球的位置讨论赢的方法数，假设这个球记为x,则其它球记为*
1.第n个雪球在1号位
x*****************
n-1 个雪球只需要随机排列(n-1)!，并且可以随便打谁2^(n-1) ，所以方法数为：c[n-1][0]*(n-1)!*2^(n-1)
2.第n个雪球在2号位
*x****************
只需要选择1个雪球在左边，n-2个雪球可以随便，所以方法数为：c[n-1][1]*(n-2)!*2^(n-2)
3.第n个雪球在3号位
**x***************
只需要选择2个雪球在左边，并且满足要求也就是dp[2]，n-3个雪球可以随便，dp[2]*c[n-1][2]*(n-3)!*2^(n-3)
备注：dp[n]记录的是n个雪球时满足要求的方法数
4.第n个雪球在i号位
*******x**********
只需要选择i-1个雪球在左边，并且满足要求也就是dp[i-1]，剩下的n-i个球随便放(n-i)!*2^(n-i)方法，所以方法数dp[i-1]*c[n-1][i-1]*(n-i)!*2^(n-i)
因此，总的赢的方法数dp[n] = sum { dp[i-1]*c[n-1][i-1]*(n-i)!*2^(n-i) } 1<=i<=n
化简：dp[n] = sum { dp[i-1] * (n-1)! * 2^(n-i) / (i-1)! } 1<=i<=n
即 dp[n] = (n-1)! * ( dp[0]*2^(n-1)/0! + dp[1]*2^(n-2)/1! + dp[2]*2^(n-3)/2! + ..... + dp[n-2]*2^1/(n-2)! + dp[n-1]*2^0/(n-1)! )
而dp[n-1] = (n-2)! * ( dp[0]*2^(n-2)/0! + dp[1]*2^(n-3)/1! + dp[2]*2^(n-4)/2! + ..... + dp[n-2]*2^0/(n-2)! ）
所以看出： dp[n]=(n-1)*2*dp[n-1]+dp[n-1]
所以 dp[n]=(2*n-1)*dp[n-1] ，dp[0]=1，
所以赢的方法数为:1*3*5*7*...*(2*n-1)
综合（1），（2）得到答案为1*3*5*7*...*(2*n-1) / (n! * 2^n)
import java.util.*;
import java.math.*;
public class Main{
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
int T=scan.nextInt();
while(T-- >0){
int n=scan.nextInt();
BigInteger sum=new BigInteger("1"),x=new BigInteger("1");
for(int i=1;i<=n;i++){
sum=sum.multiply(BigInteger.valueOf(2*i));
x=x.multiply(BigInteger.valueOf(2*i-1));
}
BigInteger gcd0=x.gcd(sum);
System.out.println(x.divide(gcd0)+"/"+sum.divide(gcd0));
}
scan.close();
}
}HDU 4043 FXTZ II （组合数学-排列组合）