3734 Blocks

問題概要

n個のタイルを赤、緑、青、黄の4色に塗る。
そのような塗り方のうち、赤と緑のタイルの枚数が偶数になるような塗り方は何通りか。
mod 10007で求めよ。

n≦10^9とする。

解法

4色の偶奇をそれぞれ1ビットで表わす。
i枚のタイルを偶奇jの状態で塗る塗り方をdp[i][j]とすると、
dp[i+1][j]=Σ{dp[i][k]|jとkが、一枚だけ偶奇が異なる}

という漸化式が立つのでDPができるが、nが大きいのでそのままやるとTLEする。

線形2項間漸化式は行列の掛け算に変換できるので、n乗を繰り返し二乗法で求めれば間に合う。

ソースコード

const int mod=10007;
struct M{
	int a[16][16];
	M operator*(const M &r){
		M ret;
		rep(i,16)rep(j,16){
			ret.a[i][j]=0;
			rep(k,16)ret.a[i][j]+=a[i][k]*r.a[k][j];
			ret.a[i][j]%=mod;
		}
		return ret;
	}
};
int bit(int b){
	int r=0;
	for(;b;b&=b-1)r++;
	return r;
}
int main()
{
	int n,T; scanf("%d",&T);
	rep(U,T){
		scanf("%d",&n);
		M x,r;
		rep(i,16)rep(j,16)x.a[i][j]=i==j,r.a[i][j]=bit(i^j)==1;
		for(int i=n;i;i/=2){
			if(i&1)x=x*r;
			r=r*r;
		}
		int ans=0; rep(i,4)ans+=x.a[0][i];
		printf("%d\n",ans%mod);
	}
	return 0;
}