CODE FESTIVAL 2014 決勝 : G - 魔方陣

オンサイトとオープン合わせてFA取れた。
http://code-festival-2014-final.contest.atcoder.jp/tasks/code_festival_final_g

問題

通常3*3の魔方陣は列や行の数値の和を一致させるが、ここでは積を一致させるような魔方陣を考える。
中心のセルの値Nが与えられた場合、条件を満たす魔方陣が何通りあるか答えよ。
ただし、回転・反転で同じ形に出来る魔方陣群は１つとみなす。

解法

列や行においてセル同士の積が一致するということは、各素因数の指数について和が一致するということで、結局普通の魔方陣と同様に考えることができる。

まず、Nを素因数分解し、N=(p1^q1)*(p2^q2)… と出来たとする。

その場合、各指数qnにおいて、中央値がqnの和の魔方陣を列挙する。
ただし、通常の魔方陣と異なり、同じ数が複数あっても良く、０も利用できるが、負の数は不可。
魔方陣の列挙は、真ん中の数値がqで決まっているとして、実はあと左上と上の２か所を0～2*qの範囲で総当たりすればよい。
(自分は冗長に右上も総当たりしてしまったが、これでも間に合う。)

後は各qnの魔方陣を掛け合わせ、全要素が異なっているような魔方陣を作ればよい。
反転と回転を考慮すると、同じとカウントされる魔方陣は８つずつできるので最後に全体を８で割る。

以下２点注意。

• 魔方陣を掛け合わせる際、複数の魔方陣の数値を直接掛け合わせない方が良い。途中最大N^2の数値が登場し、64bit値に収まらないため。以下のコードでは、各素因数の指数をvectorで保持している。
• 全部のパターンを生成するとTLEする。掛け合わせの途中、９要素が異なる数値になったら、後はどう掛け合わせても全要素異なる数値になるので、以降の掛け合わせは省略できる。

struct mag { ll A[3][3];};
vector<int> NN;
vector<mag> V[51];
vector<int> T[9];

map<ll,int> enumdiv(ll n) {
	map<ll,int> V;
	if(n==1) V[1]=1;
	else {
		for(ll i=2;i*i<=n;i++) while(n%i==0) V[i]++,n/=i;
		if(n>1) V[n]++;
	}
	return V;
}

void enummag(int g) {
	mag m;
	if(V[g].size()) return;
	
	V[g].clear();
	m.A[1][1]=g;
	FOR(m.A[0][0],g*2+1) FOR(m.A[0][1],g*2+1) FOR(m.A[0][2],g*2+1) {
		int x=m.A[0][0]+m.A[0][1]+m.A[0][2];
		m.A[2][2]=x-m.A[0][0]-m.A[1][1];
		m.A[2][1]=x-m.A[0][1]-m.A[1][1];
		m.A[2][0]=x-m.A[0][2]-m.A[1][1];
		m.A[1][0]=x-m.A[0][0]-m.A[2][0];
		m.A[1][2]=x-m.A[0][2]-m.A[2][2];
		if(m.A[2][2]<0) continue;
		if(m.A[2][1]<0) continue;
		if(m.A[2][0]<0) continue;
		if(m.A[1][0]<0) continue;
		if(m.A[1][2]<0) continue;
		if(m.A[1][0]+m.A[1][1]+m.A[1][2]!=x) continue;
		V[g].push_back(m);
	}
	
}

ll ret;

void dfs(int cur) {
	int i,j;
	int same=0;
	
	FOR(i,9) for(j=i+1;!same&&j<9;j++) if(T[i]==T[j]) same=1;
	if(!same) {
		ll r=1;
		for(i=cur;i<NN.size();i++) r*=V[NN[i]].size();
		ret+=r;
		return;
	}
	
	if(cur==NN.size()) return;
	
	FOR(i,V[NN[cur]].size()) {
		FOR(j,9) T[j].push_back(V[NN[cur]][i].A[j/3][j%3]);
		dfs(cur+1);
		FOR(j,9) T[j].pop_back();
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	ll N;
	cin>>N;
	map<ll,int> M=enumdiv(N);
	
	ITR(it,M) NN.push_back(it->second), enummag(it->second);
	dfs(0);
	cout<<ret/8<<endl;
}

まとめ

魔方陣の各行の和が中央値の３倍になるの、忘れてた…。