Mujin Programming Challenge 2018 : H - タイル張り

この考え方は覚えておこう…。
https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_h

問題

２次元グリッドの高さH,幅Wが与えられる。
グリッドの各セルを白黒で塗り分けるとき、２マスのサイズのドミノを互いに重ならないように白マス上に置ききれる塗り分け方は何通りか。

解法

「ドミノの置き方」なら良くある行列累乗テクの問題だが、今回はドミノの置き方ではなくマスの塗り分けを答えなければいけない。
同じマスの塗り分けでもドミノの置き方が複数ある場合があるので、この対処が大変である。

結論としては、やはり行列累乗に持ち込むのだが行列の持ち方が異なる。
塗り分け方は置いておいて、以下を考える。以下の値は「有無」なので真偽値である。
f(w,mask) := 高さH幅Wのグリッドのうち、条件を満たすようドミノを配置したとき、右端の列のうちmaskに示す行が１マス右にドミノがあふれるような置き方の有無

上記はドミノの配置だが、塗り分け方について以下の状態を考える。
g(w,mask') :=高さH幅Wのグリッドの塗り分け方のうち、f(w,mask)=Trueとなるようなmaskの集合が mask'となるものの組み合わせ数
mask'はmaskが2^H通りあるのでそのべき集合として2^(2^H)通りありそうだが、実際g(w,mask')→(g,w+1,mask'')の遷移を総当たりで辿ってみると、mask'に来る値は91通りである。

g(w,mask')→(g,w+1,mask'')の遷移は、追加する列の塗り分け方2^H通りに対し、mask'に含まれるmaskの遷移先のorを取ればよい。
よってg(w,mask')→(g,w+1,mask'')の遷移を91*91行列で表現し、行列累乗しよう。
最後解を求めるときは、w+1列目が全部黒である場合を考えると求めるべきmask'が１つになるのですっきり書ける。

int H,W;
ll mo=998244353;
ll step[32][32];
map<ll,int> S;
multiset<pair<ll,ll>> S2;

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

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;
}

ll nex(int mask,int avail) {
	ll ret=0;
	
	if((mask&avail)!=mask) return 0;
	avail ^= mask;
	for(int vert=0;vert<1<<H;vert++) {
		if(vert&(vert<<1)) continue;
		int tmask= vert | (vert<<1);
		if((avail&tmask)!=tmask) continue;
		ret |= 1LL<<(avail^tmask);
	}
	return ret;
}

void dfs(ll v) {
	if(S.count(v)) return;
	S[v]=0;
	int i;
	
	for(int mask=0;mask<1<<H;mask++) {
		ll ne=0;
		FOR(i,1<<H) if(v&(1LL<<i)) ne |= step[i][mask];
		S2.insert({v,ne});
		dfs(ne);
	}
	
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	int cand=0;
	FOR(i,1<<H) FOR(j,1<<H) step[i][j]=nex(i,j);
	dfs(1);
	
	Mat M;
	x=0;
	FORR(s,S) s.second=x++;
	FORR(s,S2) M.v[S[s.second]][S[s.first]]++;
	M=powmat(W,M,S.size());
	
	ll ret=0;
	FORR(s,S) {
		ll ne=0;
		FOR(i,1<<H) if(s.first&(1LL<<i)) ne |= step[i][0];
		if(ne==1) ret+=M.v[s.second][1];
	}
	cout<<ret%mo<<endl;
	
}

まとめ

bitmaskのさらにベキ集合を考えるというアイデアが出てこなかった。