キーエンス プログラミング コンテスト 2020 : F - Monochromization

難しいはずの前半の考察はできたんだけどなぁ。
https://atcoder.jp/contests/keyence2020/tasks/keyence2020_f

問題

H*Wのグリッドがあり、各セル白黒で塗られている。
このグリッドに対し、1列または1行を白または黒で上塗りする、ということを任意回数繰り返す。
最終的に得られるグリッドの塗り分け方は何通りか。

解法

まず重複しない数え方を考えよう。
列および行のうち、上塗りする位置を(2^H)*(2^W)通り総当たりしよう。
残された列・行のうち、追加で列・行の塗りつぶしをしてもよい、すなわち列または行全体が同色の箇所がある場合、その列または行も塗りつぶした状態から同じ状態に持ち込めるので、そのケースは無視する。
そうでない場合、その色の状態を実現できるのは、上塗りしない列・行の組み合わせが今総当たり中のその組み合わせだけであるので、あとはその場合上塗りの仕方を数えて総和を取ろう。

ここまでが前半パート。
上塗りするのがR行C列とするとき、その塗り方を考える。

全体を上塗り、すなわちR=H、C=Wの場合

行や列を入れ替えると、グリッド上で左下角から右上角まで上または右への移動を繰り返して移動し、その経路の左上側を白、右下側を黒と塗るような形に持ち込める。
そこで、そのような塗り方を、列や行の入れ替えも踏まえてDPで数え上げよう。
なお、この塗り方をf(R,C)としておく。

一部を上塗り、すなわちR＜H、C＜Wの場合

この場合、行または列で上塗りするパターンのみしか上塗りされないマスが存在する。
よって、行と列の上塗りパターン(2^R)*(2^C)の分だけそれらのマスの塗り方がある。
そのような塗り方を総当たりするわけだが、その際、行はa行白で(R-a)行黒、列はb行白で(C-b)行黒で塗ることとする。
行も列も同じ色で塗るマスは塗る順はどうでもよいが、片方が白で片方が黒の場合、塗る順が問題となる。
ただ、これは上述のパターンが利用できる。
行と列で色が異なる場所の分、すなわちf(a,C-b)*f(R-a,b)通りの塗り分け順がある。

int H,W;
string A[10];
const ll mo=998244353;

ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	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;
}

int R[10];
int C[10];
ll memo_all[12][12];
ll memo[12][12];

ll hoge_all(int H,int W) {
	if(memo_all[H][W]>=0) return memo_all[H][W];
	if(H==0 || W==0) return 1;
	
	ll dp[11][11][2]={};
	int y,x;
	for(y=1;y<=H;y++) dp[y][0][0]=comb(H,y);
	for(x=1;x<=W;x++) dp[0][x][1]=comb(W,x);
	
	FOR(y,H) FOR(x,W) {
		int y2,x2;
		for(y2=y+1;y2<=H;y2++) dp[y2][x][0]+=dp[y][x][1]*comb(H-y,y2-y)%mo;
		for(x2=x+1;x2<=W;x2++) dp[y][x2][1]+=dp[y][x][0]*comb(W-x,x2-x)%mo;
	}
	
	ll ret=0;
	FOR(x,W) ret+=dp[H][x][0];
	FOR(y,H) ret+=dp[y][W][1];
	return memo_all[H][W]=ret%mo;
	
}

ll hoge(int H,int W) {
	if(memo[H][W]>=0) return memo[H][W];
	ll ret=0;
	int x,y;
	FOR(y,H+1) FOR(x,W+1) ret+=comb(H,y)*comb(W,x)%mo*hoge_all(y,x)%mo*hoge_all(H-y,W-x)%mo;
	return memo[H][W]=ret%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>A[y];
		FOR(x,W) if(A[y][x]=='#') {
			R[y] |= 1<<x;
			C[x] |= 1<<y;
		}
	}
	MINUS(memo);
	MINUS(memo_all);
	
	int rm,cm;
	ll ret=hoge_all(H,W);
	FOR(rm,1<<H) FOR(cm,1<<W) if(rm&&cm) {
		int did=0;
		FOR(y,H) if((rm&(1<<y)) && (((R[y]&cm)==0)||(~R[y]&cm)==0)) did = 1;
		FOR(x,W) if((cm&(1<<x)) && (((C[x]&rm)==0)||(~C[x]&rm)==0)) did = 1;
		if(did==0) ret+=hoge(H-__builtin_popcount(rm),W-__builtin_popcount(cm));
	}
	cout<<ret%mo<<endl;
}

まとめ

解説動画では前半パートのほうが難しいと言ってたけど、自分は本番前半は到達できたし後半のほうがつらかった。