Codeforces #181 Div2. D. Painting Square

さてD。
http://codeforces.com/contest/300/problem/D

問題

数値N,KからなるクエリがQ個与えられるので、それぞれに答えよ。

数値Nに対し、N*Nの白マスで構成されたグリッドが与えられる。
これらのN*Nマスは黒マスで囲まれている。

ここで、黒マスで囲まれて正方形を白マス群を１つ選び、その中を幅１の黒線を横方向の中心および縦方向の中心に１本ずつ引き、４つの同じサイズの正方形に分割する。
この分割処理をK回行う場合、得られる図形の組み合わせ数を答えよ。

解法

Q<=10^5なので、１クエリを30usで回答しないといけない。
実際には、前処理を一旦行えば各クエリは高速で答えられる。

分割処理が行えるのはサイズSが奇数の時で、その際サイズが(S-1)/2の正方形が４つできる。
その(S-1)/2が奇数ならまた各正方形を分割できる。
よって、Sに対し分割できる最大の深さDを求めることができる。

次に、深さDに対してK回分割する組み合わせ数をDPで求めていく。
この回数をとすると、は明らかである。
K>1に対しては、１度４つに分割した深さ(D-1)の正方形に対し合計(K-1)回の分割ができるので、と言える。

しかし、ここでK<1000なので４重ループを行うことはできない。
そこで、蟻本にあるAntsを参考に、４つの項のうち２つの項の和ごとにDPをしていけばよい。

ll memo[34][1001];
ll memo2[34][1001];
ll mo=7340033;

int numsp(int N) {
	int num=0;
	while(N>1 && N%2==1) {
		num++;
		N>>=1;
	}
	return num;
}

void solve() {
	int f,r,i,j,k,l, x,y,ma,num,nt;
	int Q,N,K;
	
	memo[0][0]=1;
	for(i=1;i<34;i++) {
		memo[i][0]=1;
		
		for(j=0;j<=1000;j++) FOR(k,j+1) memo2[i-1][j]=(memo2[i-1][j]+memo[i-1][k]*memo[i-1][j-k]) % mo;
		for(j=1;j<=1000;j++) FOR(k,j) memo[i][j]=(memo[i][j]+memo2[i-1][k]*memo2[i-1][j-1-k]) % mo;
	}
	
	cin>>Q;
	FOR(i,Q) {
		cin>>N>>K;
		cout << memo[numsp(N)][K] << endl;
	}
	
	return;
}

まとめ

幸いすんなり解法が思いついた。
４重ループの解法が思いつかないと計算があふれるね。