HDU/HDOJ 4043 BUPT 235 FXTZ II 2011ACM北京网络赛 D题

FXTZ II

Accept:15	Submit:28
Time Limit:1000MS	Memory Limit:65536KB

Description

Cirno is playing a fighting game called “FXTZ” with Sanae.

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 naïve. 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?

Input

The first line an integer C (C<=30), the number of test cases.

For each case, the only line contains one integer N(0<N<=500), indicating the number of iceballs.

Output

For each case output a fraction, the possibility of Cirno's victory. The fraction must be reduced.

Sample Input

2

1

4

Sample Output

1/2

35/128

分母很好算：

n!*2^n

意思是全排列乘以2^n个状态

然后分子的公式很难推。我是用DFS打表看出来的规律

规律为：1*3*5*7*...*(2*n-1)

于是可以直接用java水过：

我的代码：

import java.util.*;
import java.math.*;

public class Main {
	public static void main(String args[])
	{
		Scanner cin=new Scanner(System.in);
		int t,i,T,n;
		BigInteger[] ans1=new BigInteger[505];
		BigInteger[] ans2=new BigInteger[505];
		BigInteger x;
		ans1[1]=BigInteger.ONE;
		ans2[1]=BigInteger.valueOf(2);
		for(i=2;i<=500;i++)
		{
			ans1[i]=ans1[i-1].multiply(BigInteger.valueOf((2*i-1)));
			ans2[i]=ans2[i-1].multiply(BigInteger.valueOf(2)).multiply(BigInteger.valueOf(i));
		}
		T=cin.nextInt();
		for(t=1;t<=T;t++)
		{
			n=cin.nextInt();
			x=ans1[n].gcd(ans2[n]);
			System.out.print(ans1[n].divide(x));
			System.out.print('/');
			System.out.println(ans2[n].divide(x));
		}
	}
}