Codeforces #429 Div1 C. On the Bench

直前にTDPCを解いておいたのが生きた。
http://codeforces.com/contest/840/problem/C

問題

N要素の数列Aがある。
このAを並べ替えたものうち、隣接要素の積が平方数にならないものを求めよ。

なお、並べ替え方が異なる場合は、値の並びそのものが同じでも別の数列とみなす。

解法

Aの各要素が平方数の倍数の場合、それらの平方数で順次割っていこう。
こうして得られたAを考える。

こうなると平方数云々の条件は関係なく、単に同じ要素を隣接させてはいけないという条件になる。
するとこの問題は以下の問題と同じとみなせるようになる。
O: 文字列 - Typical DP Contest | AtCoder

このブログでこの問題は解決していないのでここで簡単に紹介。
f(x,y) := 全部で(x+y-1)個の数値が並んだ数列がある。次に数字を挿入する箇所は(x+y)通りだが、うちy箇所は同じ数字が隣接している箇所の間で、それ以外がx箇所あるような場合の組み合わせ
f(1,0)=1から初めてAのうち値が同じもの同士を一気に配置していき、最終的にf(N+1,0)を求めればよい。

int N;
ll mo=1000000007;

ll ret=1;
ll from[303][303];
ll to[303][303];

ll combi(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}
ll hcomb(int P_,int Q_) { return (P_==0&&Q_==0)?1:combi(P_+Q_-1,Q_);}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	map<int,int> M;
	cin>>N;
	FOR(i,N) {
		cin>>x;
		for(j=2;j*j<=x;j++) while(x%(j*j)==0) x/=j*j;
		M[x]++;
	}
	
	from[1][0]=1;
	FORR(r,M) {
		int cnt=r.second;
		
		for(j=1;j<=cnt;j++) ret=ret*j%mo;
		ZERO(to);
		
		FOR(x,N+2) FOR(y,N+2) if(from[x][y]) {
			for(j=1;j<=min(x+y,cnt);j++) {
				ll a=hcomb(j,cnt-j);
				int add=cnt-j;
				
				for(int z=0;z<=min(j,x);z++) {
					int w=j-z;
					if(w>y) continue;
					ll b=combi(x,z);
					ll c=combi(y,w);
					(to[x+z+2*w][y-w+add]+=a*b%mo*c%mo*from[x][y])%=mo;
				}
			}
		}
		swap(from,to);
	}
	
	cout<<ret*from[N+1][0]%mo<<endl;
	
}

まとめ

ちょうどTDPC Oを最近解いたところだったのでよかった。