FXTZ II

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 498    Accepted Submission(s): 266

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();

	}

}