[hdu-2048]神、神、そして神様

神様、神様、神様
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 20794    Accepted Submission(s): 8780
Problem Description
HDU 2006'10 ACM contestの授賞式が盛大に始まりました!
雰囲気を盛り上げるために、組織者は個別に生麺を開き、賞品が豊富な抽選活動を行いました.この活動の詳細な要求はこうです.
まず、パーティーに参加した全員が自分の名前が書かれたメモを抽選箱に入れた.
そして、すべてのメモが追加されて完成し、一人一人が箱からメモを取ります.
最後に、取得したメモに自分の名前が書かれていると仮定すると、「おめでとう、当選しました!」
当時の盛り上がりを想像してみてください.当選者の賞品はみんなが夢見ていたTwinsサイン写真ですね.ただ、すべてのデザインを試みたコメディが悲劇的に終わることが多いように、今回の抽選活動は結局誰も当選しなかった.
私の神、神と神様、どうしてこんなことになったのですか.
ただ、興奮しないでください.今問題が来ました.このような状況が発生する確率を計算してもらえますか.
計算できないの?あなたも悲劇で終わりたいの?!
 
Input
入力データの最初の行は整数Cであり、試験例の個数を表し、次いでC行データであり、各行には整数n(1 
Output
各テストインスタンスについて、このような状況が発生した割合を出力してください.各インスタンスの出力は1行を占め、結果は2桁の小数(四捨五入)を保持します.詳細なフォーマットはsample outputを参照してください.
 
Sample Input

   
     

      
    1
2
   
     

 
Sample Output

   
     

      
    50.00%
   
     

 
分析:これは繰返し問題です.
1、n人でn枚の切符があれば、n!種の配列状況.私たちがしなければならないのはここからn!この場合,n人全員の誤配列を見出す.
2、もしn人がいれば、間違いの数はf(n)で、彼らを1人とn-1人の2つの部分に分けます.例えば、以下の3、4の2つのケースがあります.
3、もし1人が自分の切符を持っていて、n-1が持っているのはすべて自分の切符ではありませんならば、この1人はこのn-1人の中でどんな人と切符を交換しなければならなくて、n人の間違いを満たすことができます.従って(n−1)*f(n−1)がある.
4、n-1人のうち1人が自分の切符を持っている場合、1人が自分の切符を持っているかどうかにかかわらず、n-1人のうち1人が自分の切符を持っている人と交換するだけで、n人の列を間違えることができます.そして、n-1人のうち自分の切符を持っている人を除いて、n-2人は間違いを満たしているに違いない.だからまた(n-1)*f(n-2)があります.
以上より、f(n)=(n−1)*[f(n−1)+f(n−2)]
コードを叩くとき,1つの2次元配列cases[21][2]を利用できる. ,配列0列目はn人のすべての配列を格納するn!,配列1列目はn人の誤配列を格納する f ( n ) = ( n - 1) * [ f ( n - 1 ) + f ( n - 2 ) ]

import java.util.Scanner;

public class Main {

	static long[][] cases = new long[21][2];

	static {
		cases[1][0] = 1;
		cases[1][1] = 0;
		cases[2][0] = 2;
		cases[2][1] = 1;

		for (int i = 3; i < 21; i++) {
			cases[i][0] = i * cases[i - 1][0];
			cases[i][1] = (i - 1) * (cases[i - 1][1] + cases[i - 2][1]);
		}
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();

		while (n-- != 0) {
			int count = scanner.nextInt();

			System.out.printf("%.2f", 100.0 * cases[count][1] / cases[count][0]);
			System.out.println("%");
		}
	}
}