AOJ 0559 JOI Flag

問題

mxnマスのグリッドにJ, O, Iの文字を配置する。
'?'のマスには自由に文字を入れることができ、'J', 'O', 'I'がはじめから入っているマスにはその文字しか入れることができない。

全てのマスに文字を入れ終えたときに、

JO
I

という文字の並びがあるような、文字の入れ方は何通りあるか、
mod 10^5で求めよ。

制約条件

m, n≦20

方針

全ての場合の数から、条件を満たさない場合の数を引いてやればよい。

条件を満たさない場合の数は、一行分のビットを覚えるようなビットDPをすれば求まる。
dp[i][j][bit][prev]を、i行j列まで見たとき、直前の行にJOが出現しているマスのビットがbitで表され、一つ左隣のマスがJであるときの場合の数とする。
ここから、現在のマスを3通り更新するようなDPをすればいい。

ただしそのまま配列を確保するとMLEになるので、
直前の2マスだけ覚える。

毎回mod取ってたらTLEになって、剰余じゃなくて引き算でmod取るようにしたらACだった。

ソースコード

const int mod = (int)1e5;
int h, w, dp[2][1<<20][2];
string in[20];
const char *flag = "JOI";

int main()
{
	
	cin >> h >> w;
	rep(i, h) cin >> in[i];
	dp[0][0][0] = 1;
	int cur = 0, next = 1;
	rep(i, h){
		rep(j, w){
			memset(dp[next], 0, sizeof(dp[next]));
			rep(bit, 1 << w) rep(p, 2) if(dp[cur][bit][p]){
				rep(k, 3){
					if(in[i][j] != '?' && in[i][j] != flag[k]) continue;
					if((bit & 1 << j) && k == 2) continue;
					int nbit = bit & ~(1 << j), np = k == 0;
					if(p && k == 1) nbit |= 1 << j - 1;
					dp[next][nbit][np] += dp[cur][bit][p];
					if(dp[next][nbit][np] >= mod) dp[next][nbit][np] -= mod;
				}
			}
			swap(cur, next);
		}
		rep(bit, 1 << w){
			dp[cur][bit][0] += dp[cur][bit][1];
			if(dp[cur][bit][0] >= mod) dp[cur][bit][0] -= mod;
			dp[cur][bit][1] = 0;
		}
	}
	
	int ans = 1;
	rep(i, h) rep(j, w) if(in[i][j] == '?') ans = (ans * 3) % mod;
	rep(i, 1 << w) ans = (ans + mod - dp[cur][i][0]) % mod;
	cout << ans << endl;
	return 0;
}