AtCoder ABC #295 : Ex - E or m

TopCoderで出そうな印象。
https://atcoder.jp/contests/abc295/tasks/abc295_h

問題

01で構成されるH*Wのグリッドが与えられる。
ただし一部セルは未確定である。

未確定セルを0または1で埋めるとき、以下を満たす埋め方は何通りか。

• 初期状態全セル0の状態から、以下の手順により作れる。
  • 各行、左から何マスか1にする
  • 各列、上から何マスか1にする

解法

左上から、row-major orderで順に01を埋めて行く。
その際

• 各列、ここまで上から1にすることが可能か
• 現在の行で、ここまで左から1にすることが可能か

を状態として持ちながらDPしていけばよい。

int H,W;
const ll mo=998244353;
ll from[1<<18][2],to[1<<18][2];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	from[(1<<W)-1][1]=1;
	int mask;
	FOR(y,H) {
		cin>>s;
		FOR(x,W) {
			ZERO(to);
			FOR(mask,1<<W) {
				if(s[x]=='0'||s[x]=='?') {
					(to[mask&((1<<W)-1-(1<<x))][0]+=from[mask][0]+from[mask][1])%=mo;
				}
				if(s[x]=='1'||s[x]=='?') {
					if((mask&(1<<x))) {
						(to[mask][0]+=from[mask][0])%=mo;
						(to[mask][1]+=from[mask][1])%=mo;
					}
					else {
						(to[mask][1]+=from[mask][1])%=mo;
					}
				}
				
			}
			
			swap(from,to);
		}
		FOR(mask,1<<W) {
			(from[mask][1]+=from[mask][0])%=mo;
			from[mask][0]=0;
		}
	}
	
	ll ret=0;
	FOR(mask,1<<W) ret+=from[mask][1];
	cout<<ret%mo<<endl;
	
	
}

まとめ

TopCoderならH*Wの値に上限設けていそう。