AOJ0504 Card Game II - nanikakaのAOJ航海日誌

解法

公式解説を読んで解きましたが、所々理解が追いついてない状態です。
Mで場合分けして解くようです。
M=0のとき、nk枚目に引くカード(最後に引くカード)が1である場合が、ゲームをクリアする必要十分条件というらしいのです。そして、最後が1であれば、直前のkn-1枚のカードはどんな順列でも途中でカードの山が尽きてゲームオーバーになることがない、らしいです。これは自力では気づける自信がないなー・・・。結局、(最後が1であるような場合の数)/(全順列数)が答えの確率になります。実はこの確率は1/nになります(!)。
M=1のとき。1度もゲームオーバーになることなくクリアできる確率は上述の通り1/nになります。そして、（自分は数学力がからっぽなので）驚くべきことに、2回目の試行でクリアできる確率を求めるにはk=1の場合だけ考えれば十分らしいのです。M=0のときは、式の結果にkが入ってこないからkが答えに影響しないことが分かるのですが、M=1の場合でいきなりそんなこと言われても分からない・・・。まぁこれを信じることにすると、1が書かれたカードをi番目(1 <= i < n)に引く確率はそれぞれ1/n。残ったn-i枚で、M=0のときと同じ議論をすると、クリアする確率は1/(n-i)。よって、2回目でクリアする確率は(1/n){(1/1)+(1/2)+...+(1/(n-1))}。これに1回目で成功する確率を加えた1/nを足したものが答えになります。

数学力が足りなさすぎる！！！

ソース

import java.util.Scanner;

//Card Game II
public class AOJ0504 {

	int[] res, t;
	
	void add(int D){
		t[0] = 1/D;
		int R = 1%D, id = 1;
		while(id<t.length){
			R*=10;
			t[id++] = R/D;
			R%=D;
		}
		for(int i=t.length-1;i>0;i--){
			res[i]+=t[i];
			res[i-1]+=res[i]/10;
			res[i]%=10;
		}
		res[0]+=t[0];
	}
	
	void div(int n){
		t[0] = res[0]/n;
		int R = res[0]%n, id = 1;
		while(id<t.length){
			R = R*10 + res[id];
			t[id++] = R/n;
			R%=n;
		}
		for(int i=0;i<t.length;i++)res[i] = t[i];
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt(), k = sc.nextInt(), m = sc.nextInt(), r = sc.nextInt();
			if((n|k|m|r)==0)break;
			res = new int[r+10];
			t = new int[r+10];
			if(m==0){
				add(n);
			}
			else{
				for(int i=1;i<n;i++)add(i);
				div(n);
				add(n);
			}
			System.out.print(res[0]+".");
			for(int i=1;i<=r;i++)System.out.print(res[i]+(i==r?"\n":""));
		}
	}
	
	public static void main(String[] args) {
		new AOJ0504().run();
	}
}