SRM 391 500pt: KeysInBoxes

問題概要

1~N(<20)の箱がある。それぞれの箱を開ける鍵が1個ずつある。鍵を箱の中に1個ずつ適当に入れて全ての箱の鍵を占める。あなたはM(

考えたこと

• 何で有理数？面倒くさい…。
• とりあえず20!を計算すると64ビットに収まる。
• ということは確率は見せかけで場合の数を求める問題か。
• どうも置換の問題っぽい？数学のことばに直すと、M個以下の巡回置換で表せる置換の数？
• Mは大した量ではないのでkを固定してk個の巡回置換で表せる置換の数を足しあげよう。
• 重複が出ないように考えないといかん。
• ある特定の1個に注目して、その数字を含む巡回置換のサイズをまた固定して残りは再帰的に探索したらいけそう。
• 書く。サンプル通らない。
• 再帰呼び出しの引数に間違い発見。修正して無事通った。

practiceで通ったコード

計算量O(N^3)くらい？

#include <string>
#include <sstream>
#include <algorithm>
using namespace std;

typedef long long int64;
const int MAX_N = 20;

int64 fact[MAX_N+1];
int64 comb[MAX_N+1][MAX_N+1];
int64 memo[MAX_N+1][MAX_N+1];
bool visited[MAX_N+1][MAX_N+1];

struct KeysInBoxes {

	string getAllKeys(int N, int M) {

		//階乗の計算
		fact[0] = 1;
		for(int i=1; i<=MAX_N; i++){
			fact[i] = i * fact[i-1];
		}

		//二項係数の計算
		for(int n=0; n<=N; n++){
			for(int k=0; k<=n; k++){
				comb[n][k] = fact[n] / (fact[k] * fact[n-k]);
			}
		}

		int64 cnt = 0, total = fact[N];
		//k個の巡回置換に分解する方法
		for(int k=1; k<=M; k++){
			cnt += func(N, k);
		}

		//約分
		int64 d = __gcd(cnt, total);
		cnt /= d; total /= d;

		//文字列へ変換
		stringstream ss;
		ss << cnt << '/' << total;
		return ss.str();
	}

	int64 func(int N, int k){

		//メモ化処理
		if(visited[N][k]){
			return memo[N][k];
		}
		visited[N][k] = true;

		int64& ret = memo[N][k];

		//基底
		if(k == 1){
			return ret = fact[N-1];
		}

		//ある特定の一個がサイズいくつの巡回置換に含まれるか
		for(int sz=1; sz<=N; sz++)if(N - sz >= k - 1){
			ret += comb[N-1][sz-1] * fact[sz-1] * func(N-sz, k-1);
		}

		return ret;
	}

};