블로거의 비비 시간.

자신이 통제할 수 없는 방향으로 나아가고 있음을 느끼다.

Solution

DP\mathtt{DP} DP를 'O' 와 상관없이 수행하는 방법을 먼저 고려하십시오.
세로로 놓인 D o m i n o\mathtt {Domino} Domino는 비교적 쉽고 관건은 가로로 놓인 것을 해결하는 것이다.
f[i] [j] f[i] [j] f[i] [j]를 ii열로 지정하기 전에 Do m i n o\mathtt {Domino} Domino는 이미 모두 합법화되었으며, 본 열은 i+ 1 i+1i+1열을 필요로 하여 빈 위치의 상태가 jj(예를 들어 j=(101) 2 j=(101)2j=(101)2는 i+1 i+1 i+1 열의 첫 번째이며, 세 자리는 가로로 놓인 D o m i n o\mathtt {Domino} Domino가 비어 있어야 한다.sto[i]sto[i]sto[i]는 ii열의'X'를 표시하는 상태를 미리 처리해야 한다.
그리고 매거 i, j, ki, j, j, k(i, ji, ji, ji, j의 정의와 같이 kk는 매거 i-3-1i-3열의 상태이다).
우리는 언제 kkk가 jjj로 옮길 수 있을지 고려했다.
4

kkk상태는 뒷열로 보충해야 하는 위치 jj상태는 장애가 없다

4

jj 상태의'X'위치와 보충된 위치를 제외하고 나머지 ii열의 위치는 놓지 않거나 세로로 놓거나 한다

다음에 우리는 'O' 를 고려할 것이다.'O'를'X'로 바꿀 수 있다는 것을 발견했다.'O'는 합법적이기 때문에 최소한 하나의 Do m i n o\mathtt {Domino} Domino를 마주하면'O'옆의 위아래 좌우를 열거할 수 있다. Do m i n o\mathtt {Domino} Domino를 이렇게 마주하는 경우(444종)는 무겁다. 이 정도는 무겁다고 할 수 있으니 용서하면 된다.

Code

#include 
#include 

#define rep(i, _l, _r) for(register signed i = (_l), _end = (_r); i <= _end; ++ i)
#define fep(i, _l, _r) for(register signed i = (_l), _end = (_r); i >= _end; -- i)
#define erep(i, u) for(signed i = head[u], v = to[i]; i; i = nxt[i], v = to[i])
#define print(x, y) write(x), putchar(y)

template <class T> inline T read(const T sample) {
	T x = 0; int f = 1; char s;
	while((s = getchar()) > '9' || s < '0') if(s == '-') f = -1;
	while(s >= '0' && s <= '9') x = (x << 1) + (x << 3) + (s ^ 48), s = getchar();
	return x * f;
}
template <class T> inline void write(const T x) {
	if(x < 0) return (void) (putchar('-'), write(-x));
	if(x > 9) write(x / 10);
	putchar(x % 10 ^ 48);
}
template <class T> inline T Max(const T x, const T y) {return x > y ? x : y;}
template <class T> inline T Min(const T x, const T y) {return x < y ? x : y;}
template <class T> inline T fab(const T x) {return x > 0 ? x : -x;}
template <class T> inline T Gcd(const T x, const T y) {return y ? Gcd(y, x % y) : x;}

const int N = 1e4 + 5, mod = 1e9 + 7;

char g[3][N];
int n, X, Y, dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}, sto[N], f[N][10], l[10], r[10], ans;

bool ok(const int x, const int y) {
	if(x < 0 || x >= 3 || y < 0 || y >= n || g[x][y] == 'X') return 0;
	return 1;
}

int DP() {
	memset(sto, 0, sizeof sto);
	memset(f, 0, sizeof f);
	rep(i, 0, 2) rep(j, 0, n - 1)
		if(g[i][j] == 'X') sto[j] |= (1 << i);
	rep(i, 0, n - 1) {
		rep(j, 0, 7) {
			if(sto[i] & j) continue;
			rep(k, 0, 7) {
				int t = (j | k | sto[i]), tmp;
				if(i == 0) tmp = (k == 0);
				else tmp = f[i - 1][k];
				if((k & (sto[i] | j)) == 0 && (t == 1 || t == 4 || t == 7))
					f[i][j] = (f[i][j] + tmp) % mod;
			}
		}
	}
	return f[n - 1][0];
}

int main() {
	int cnt;
	n = read(9);
	rep(i, 0, 2) scanf("%s", g[i]);
	rep(i, 0, 2) rep(j, 0, n - 1)
		if(g[i][j] == 'O') {X = i, Y = j; g[i][j] = 'X'; break;}
	rep(i, 1, 15) {
		int tmp = i; cnt = 0;
		bool flag = 0;
		rep(j, 0, 3) {
			if(tmp & 1) {
				l[++ cnt] = dir[j][0], r[cnt] = dir[j][1];
				l[++ cnt] = (dir[j][0] << 1), r[cnt] = (dir[j][1] << 1);
			}
			tmp >>= 1;
		}
		rep(j, 1, cnt) if(! ok(X + l[j], Y + r[j])) {flag = 1; break;}
		if(flag) continue;
		rep(j, 1, cnt) g[X + l[j]][Y + r[j]] = 'X';
		if((cnt >> 1) & 1) ans = (ans + DP()) % mod;
		else ans = (ans - DP() + mod) % mod;
		rep(j, 1, cnt) g[X + l[j]][Y + r[j]] = '.';
	}
	print(ans, '
');
	return 0;
}