読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #181 Div2. D. Painting Square

Codeforces

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

問題

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

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

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

解法

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


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

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

しかし、ここでK<1000なので4重ループを行うことはできない。
そこで、蟻本にあるAntsを参考に、4つの項のうち2つの項の和ごとに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;
}

まとめ

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

広告を非表示にする