TopCoder SRM 546 Div1 Hard FleaCircus

問題

長さnの順列（1〜nの数の並び替え）を、
4回適用した順列P^4が与えられる。

このとき、Pとしてありうる順列は何通りか、求めよ。

制約条件

n≦700くらい

方針

まずは順列をサイクルに分割する。

Pにおいて長さkのサイクルが、P^4ではどうなっているかを考察する。
すると、

• k = 4l のとき、lの長さのサイクル4つに分かれる
• k = 4l±1 のとき、4l±1のサイクルのまま
• k = 4l + 2 のとき、2l + 1の長さのサイクル2つに分かれる

ことがわかる。

したがって、サイクル長が奇数のときは、同じ長さが1個か2個か4個集まったサイクルから分解されて出来ていて、
サイクル長が偶数のときは、同じ長さのサイクル4つが集まったサイクルから分解されて出来ていることがわかる。

これがわかったら、サイクル長ごとに、
その個数のサイクルを作る場合の数をDPで求めればいい。
サイクルの長さがiで、個数がnum[i]個だとする。
サイクルk個を作る場合の数をdp[k]とすると、
iが奇数のとき、dp[k] = Σdp[k - {1, 2, 4}] * その合併の仕方
iが偶数のとき、dp[k] = dp[k - 4] * その合併の仕方

m個を合併するときの仕方は、まず1個の選び方は固定でよくて、
残りのm-1個の選び方がP(num[i]-1, m-1)通り。
次にエッジのつなぎ方がi ^ (m-1)通り。

ソースコード

const int mod = (int)1e9 + 9;
int n, to[1000], num[1000], dp[1000];
bool v[1000];

int dfs(int c){
	v[c] = 1;
	int res = 1;
	if(!v[to[c]]) res += dfs(to[c]);
	return res;
}

class FleaCircus {
	public:
	int countArrangements(vector <string> afterFourClicks) 
	{
		string s;
		each(i, afterFourClicks) s += *i;
		stringstream ss(s);
		int t;
		n = 0;
		while(ss >> t) to[n++] = t;
		
		memset(v, 0, sizeof(v));
		memset(num, 0, sizeof(num));
		rep(i, n) if(!v[i]) num[dfs(i)]++;
		
		ll ans = 1;
		rep(i, n + 1) if(num[i]){
			vi g;
			if(i % 2) g.pb(1), g.pb(2), g.pb(4);
			else g.pb(4);
			
			memset(dp, 0, sizeof(dp));
			dp[0] = 1;
			for(int j = 1; j <= num[i]; j++) rep(k, g.size()){
				if(g[k] > j) break;
				ll tmp = 1;
				rep(l, g[k] - 1) tmp = tmp * (j - 1 - l) % mod;
				rep(l, g[k] - 1) tmp = tmp * i % mod;
				dp[j] = (dp[j] + tmp * dp[j - g[k]]) % mod;
			}
			ans = (ans * dp[num[i]]) % mod;
		}
		
		return ans;
	}
};