読者です 読者をやめる 読者になる 読者になる

AOJ0559 JOI Flag

bitDP初めてなのにこれをやったせいで苦戦しました.
JOIの解説を読まないと解けませんでした...

これだと解けるけどAOJではMLEします

#include <cstdio>
#include <cstring>
using namespace std;

const int mod = 100000;
int n, m, count;
char flag[21][21];
int fact[401];
int dp[20][20][10947][2];

int rec(int v, int isJ, int S){
	int x, y;
	x = v / m; y = v % m;
	if (v == n * m){
		return 1;
	}
	if(dp[x][y][S][isJ] >= 0){
		return dp[x][y][S][isJ];
	}
	int tmp = 0;
	if (flag[x][y] == '?' || flag[x][y] == 'J'){
		int bit = S;
		bit = bit << 1 & ((1 << (m - 1)) - 1);
		tmp = (rec(v + 1, 1, bit) + tmp) % mod;
	}
	if (flag[x][y] == '?' || flag[x][y] == 'O'){
		int bit = S;
		if(isJ == 1){
		    bit = (bit << 1 & ((1 << (m - 1)) - 1)) | 1;
		}else{
		    bit = bit << 1 & ((1 << (m - 1)) - 1);
		}
		tmp = (rec(v + 1, 0, bit) + tmp) % mod;
	}        
	if (flag[x][y] == '?' || flag[x][y] == 'I'){
		if (((1 << (m - 2)) & S) == 0 || y == m - 1){ 
			int bit = S;
			bit = bit << 1 & ((1 << (m - 1)) - 1);
			tmp = (rec(v + 1, 0, bit) + tmp) % mod;
		}
	}
	return dp[x][y][S][isJ] = tmp;
}

int main(){
	fact[0] = 1;
	for(int i = 1; i <= 400; i++){
		fact[i] = (fact[i - 1] * 3) % mod;
	}
	scanf("%d %d", &n, &m);
	getchar();
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			scanf("%c", &flag[i][j]);
			if (flag[i][j] == '?'){
				count++;
			}
		}
		getchar();
	}    
	memset(dp, -1, sizeof(dp));
	printf("%d\n", (fact[count] - rec(0,0,0)) % mod);
	return 0;
}

さらにisJとSの情報をまとめてひとつの要素にするかforループで配列を使い回すと通ります