Codeforces 300(#181 Div2 only) D. Painting Square

問題

nxnの小正方形が並んだ正方形がある。大きな正方形の外側は黒い。
この正方形に対して以下の操作をk回行う。

• 一辺の長さが3以上の奇数の正方形であって、内部が全部白で、外側は黒いものを選ぶ
• 辺の長さをLとしたとき、内部の小正方形で(L + 1) / 2行目および(L + 1) / 2列目にある小正方形を全て黒に塗る

この操作を行った後の正方形の状態は何通りありうるか求めよ。

制約条件

n≦10^9
k≦1000

方針

正方形を"どのくらいの深さまで操作できるか"をdとする。
（dは、nが3以上の奇数である間n = (n + 1) / 2とできる回数）

すると、求める場合の数は深さがdの4分木であって、
各頂点は黒または白、ある頂点が黒のとき、その親の頂点も黒
であるような木のうち、黒の頂点の数がk個であるようなものの個数。

dp[depth][k]を、深さdepthで、黒い頂点がk通りあるときの個数とすると、
dp[i + 1][j + k + l + m + 1] = Σdp[i][j] * dp[i][k] * dp[i][l] * dp[i][m]
の漸化式が成り立つので、計算すればよい。

このままだとO(k^4)かかってしまうが、
dp[i][j] * dp[i][k]の部分をまとめてd[j + k]と計算しておけば、
dp[i + 1][j + k + 1] = Σd[j] * d[k]として求められる。

この計算は畳み込みなので、剰余環上のFFTを使うのが想定解だったらしいのだけど、
このO(k^2 logn)の解法で300msくらいで通ってしまうのでぜんぜんいみない…
k=50000くらいだったらFFT必須になりそうなのに。

ソースコード

const int mod = 7340033;
ll dp[33][1024], d[1024];

int main(){
	dp[0][0] = 1;
	rep(i, 31){
		memset(d, 0, sizeof(d));
		dp[i + 1][0] = 1;
		rep(j, 1001) rep(k, 1001 - j) d[j + k] += dp[i][j] * dp[i][k];
		rep(j, 1001) d[j] %= mod;
		rep(j, 1001) rep(k, 1000 - j) dp[i + 1][j + k + 1] += (ll)d[j] * d[k];
		rep(j, 1001) dp[i + 1][j] %= mod;
	}
	int q;
	scanf("%d", &q);
	while(q--){
		int n, k;
		scanf("%d%d", &n, &k);
		int j = 0;
		while(n > 1 && n % 2) j++, n /= 2;
		printf("%d\n", dp[j][k]);
	}
	return 0;
}