AtCoder ABC #204 : F - Hanjo 2

Eで手間取ってしまった。Fは典型。
https://atcoder.jp/contests/abc204/tasks/abc204_f

問題

H*Wのグリッドがある。
1*1と1*2のブロックでこのグリッドを埋めるとき、何通りの埋め方があるか。

解法

Hが小さいので行列累乗で解く。
f(n,mask) := 左からn列目までを決めたとき、1*2のブロックを横に置くことでmaskに対応する列がn+1列目にはみ出ているような置き方の組み合わせ

とすると、f(n,*)→f(n+1,*)の状態遷移を考えると(2^H)次の行列累乗に持ち込めるのでf(W,0)を求めよう。

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

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 H;
ll W;
Mat A;

void dfs(int mask,int cur,int sm) {
	if(cur==H) {
		A.v[sm][mask]++;
		return;
	}
	
	if(mask&(1<<cur)) {
		dfs(mask,cur+1,sm);
	}
	else {
		// 1*1
		dfs(mask,cur+1,sm);
		// yoko
		dfs(mask,cur+1,sm|(1<<cur));
		// tate
		if(cur<H-1&&(mask&(1<<(cur+1)))==0) {
			dfs(mask,cur+2,sm);
		}
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	int mask;
	FOR(mask,1<<H) dfs(mask,0,0);
	A=powmat(W,A);
	cout<<A.v[0][0]<<endl;
}

まとめ

yukicoderでこれ系何度も見た気がするしね。