Codeforces #175 Div2. D. Permutation Sum

今度こそここからが本番。
http://codeforces.com/contest/285/problem/D

問題

整数値Nが与えられる。
要素がA[1],A[2],...,A[N]となるPermutationと、B[1],B[2],...,B[N]となるPermutationのうち、C[i]=((A[i]-1+B[i]-1)%N)+1で計算できる数列もPermutationとなる組み合わせを答える。

解法

まず、C[i]=iとしてCを固定してしまう。
Cの並び順はN!通りなので、Cを固定したときの答えにN!すればよい。

Cを固定したうえで、AをN!通りDFSで全部列挙すればよい。
CとAを固定すればBが確定するので、AおよびBがPermutationかチェックできる。

なお、この問題はメモ化再帰を使ってもN>=14だとTLEする。
なのでN=15の答えは１分ほどコードを動かして答えを埋め込んだ。
また、どうもNが偶数だと答えが0になるので、結局調べるのはN<=13だけで良い。

まぁ全部埋め込んでもいんだけどね。

int N;
ll mo=1000000007;
map<int,ll> memo[1<<17];

ll dfs(int id,int MA,int MB) {
	if(id>=N) return 1;
	if(memo[MA].find(MB)!=memo[MA].end()) return memo[MA][MB];
	
	ll res=0;
	int a,b;
	FOR(a,N) {
		if(MA & (1<<a)) continue;
		b=(id-a+N)%N;
		if(MB & (1<<b)) continue;
		res = (res + dfs(id+1,MA|(1<<a),MB|(1<<b))) % mo;
	}
	return memo[MA][MB]=res;
}

void solve() {
	int f,r,i,j,k,l,x,y,cur,tar;
	
	N=GETi();
	if(N==15) _P("150347555\n");
	else if(N==16 || N==14) _P("0\n");
	else {
		ll res = 1;
		FOR(i,N) res=(res*(i+1))%mo;
		FOR(i,1<<N) memo[i].clear();
		
		res=(res*dfs(0,0,0)) % mo;
		cout << res << endl;
	}
	return;
}

まとめ

最初N=13で600msちょい、N=14でTLEしてどうしようか迷ったけど、事前計算結果を埋め込めばいいことに気づいてげんなり。
綺麗にN=16を解くことができるのかな？