CSAcademy Round #69 : E. The Wall

ちょっと説明文の解釈に時間がかかった。
https://csacademy.com/contest/round-69/task/the-wall/

問題

高さ1、幅2のブロックを縦に積んでいく。
奇数段目は3個のブロックが並ぶようにし、偶数段目は２個のブロックが並ぶようにする。
２個のブロックの中心は、下の段の３個のブロックの境目に来るようにし、その上の３個のブロックは、中心がブロックの境目または端に来るようにする。

何もない状態からN段ブロックを積みたい。
ブロックを積む際は、直下に来るブロックがすべて積み終わった状態でなければ積むことができない。
N段ブロックを積む際の積み方の順番は何通りか。

解法

行列累乗で解いていく。
下から3,2,3個のブロックが並ぶ計３段を考えよう。
最上段の上にさらに４段目を積むには、最上位のブロックを２個以上並べる必要があり、そのためには２段目のブロックが揃わないと行けない。
よって、偶数段目を積み始めるには２段下のブロックが積み終わらなければならない。

そこで、この３段におけるブロックの状態2^8で256通り(実際は下にブロックがなくあり得ない状態もあるが)の状態を考える。
初期状態として、最下段３段の状態2^3=8通りを考え、初めて下２段計5ブロックが埋まった段階で、3段目が2^8通りどうなっているかを考えると、２段積む場合の状態遷移が求められる。
この状態遷移は最下段8通りに対し256通り状態に関する遷移を求めるだけなので計算量は余裕である。

最下段の状態8通りに対し、２段埋まった状態における３段目の状態8通りへの遷移の仕方を考えうると8*8の正方行列が求められるので、あとは行列累乗テクでN/2乗を求めよう。
Nが奇数の場合は、残り最上段の埋め方を何通りか試すだけ。

const int MAT=8;
struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);};};

ll mo=1000000007;

Mat mulmat(Mat& a,Mat& b,int n=MAT) {
	ll mo2=4*mo*mo;
	int x,y,z; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(x,n) FOR(z,n) FOR(y,n) {
		r.v[x][y] += a.v[x][z]*b.v[z][y];
		if(r.v[x][y]>mo2) r.v[x][y] -= mo2;
	}
	FOR(x,n) FOR(y,n) r.v[x][y]%=mo;
	return r;
}

Mat powmat(ll p,Mat a,int n=MAT) {
	int i,x,y; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(i,n) r.v[i][i]=1;
	while(p) {
		if(p%2) r=mulmat(r,a,n);
		a=mulmat(a,a,n);
		p>>=1;
	}
	return r;
}

int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	Mat A;
	FOR(i,8) {
		ll tp[1<<8]={};
		tp[i]=1;
		for(int mask=0;mask<256;mask++) {
			if((mask&31)==31) continue;
			FOR(x,8) if((mask&(1<<x))==0) {
				if(x==3 && ((mask&3)!=3)) continue;
				if(x==4 && ((mask&6)!=6)) continue;
				if(x==5 && ((mask&8)!=8)) continue;
				if(x==6 && ((mask&24)!=24)) continue;
				if(x==7 && ((mask&16)!=16)) continue;
				tp[mask^(1<<x)]+=tp[mask];
			}
		}
		FOR(x,8) A.v[i][x]=tp[(x<<5)|31];
	}
	
	
	cin>>N;
	
	A=powmat(N/2,A);
	if(N%2==0) {
		cout<<A.v[0][0]<<endl;
	}
	else {
		ll ret=0;
		ret+=A.v[0][0]*6;
		ret+=A.v[0][1]*2;
		ret+=A.v[0][2]*2;
		ret+=A.v[0][3]*1;
		ret+=A.v[0][4]*2;
		ret+=A.v[0][5]*1;
		ret+=A.v[0][6]*1;
		cout<<ret%mo<<endl;
		
	}
	
	
}

まとめ

今回Cが最難でした…。