yukicoder : No.2837 Flip Triomino

これはすんなり。
https://yukicoder.me/problems/no/2837

問題

H*Wのグリッドがあり、各セルは白または黒色の状態であるとする、
また、初期状態として各セル白・黒・不定のいずれかが与えられる。

ここに対し、4種類のトリオミノ型の形状の3マスに対し白黒反転させる操作を任意回数行える時、全マスを白にできるような初期状態は何通りか。

解法

各セル(r,c)を、r+cで分類すると、どのトリオミノを選択しても、(r+c)が連続する3つのセルを1つずつ白黒反転させることに相当する。
また、複数の形状のトリオミノを使うことで、r+cが一致する2つのマスを同時に白黒反転させることができる。

よって、r+cが一致するマスの集合に対し、黒マスの数の偶奇と、そのマスに対する処理回数の偶奇が一致していればよい。
処理aを、r+c=aとなるマス、r+c=a+1となるマス、r+c=a+2となるマスを選んで処理することと置く。
dp(n,a,b) := r+c=nとなるマスまでを白にそろえたとき、処理(n-1)の回数の偶奇がaで、処理(n)の回数の偶奇がbであるような組み合わせ

としてDPのテーブルを埋めて行けばよい。

int H,W;
string S[505];
const ll mo=998244353;

ll comb(ll N_, ll C_) {
	const int NUM_=2400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll from[2][2];
ll to[2][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	int C[1010][2]={};
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) {
			if(S[y][x]=='B') C[(y+x)][0]^=1;
			if(S[y][x]=='?') C[(y+x)][1]++;
		}
	}
	
	from[0][0]=1;
	FOR(i,H+W) {
		ZERO(to);
		for(j=0;j<=C[i][1];j++) {
			FOR(x,2) FOR(y,2) {
				(to[y][C[i][0]^(j%2)^x^y]+=from[x][y]*comb(C[i][1],j))%=mo;
			}
		}
		swap(from,to);
	}
	
	cout<<from[0][0]<<endl;
}

まとめ

テトリミノで埋める問題もあったような。あれAtCoderだったかな…。