[LOJ2731] 「JOISC 2016 Day 1」棋盤遊戲（DP計數）

題意

• 給你一個 3 × n \rm 3 \times n 3×n的棋盤，棋盤上有一些棋子，問有多少種不同填棋子的順序可以填滿棋盤，一個位置可以被填棋子當且僅當它的左右已經填了棋子或者它的上下都填了棋子。（ n ≤ 2000 \rm n \le2000 n≤2000）

首先判掉無解的情況，如果第一行或者第三行有連續兩個空棋子，或者四個邊角沒有填棋子，就不存在填滿棋盤的方案。

把這個棋盤當做一個四聯通圖，我們可以發現每個空格組成的聯通塊是互不影響的，我們可以分聯通塊DP，再組合一下各個聯通塊的方案就好了。

對于某個聯通塊，我們觀察到每一列的填法隻與上一列的棋子是通過哪種規則填的和填的時間有關，我們記 f ( 0 / 1 , i , j ) \rm f(0/1,i,j) f(0/1,i,j)表示第 2 \rm2 2行第 i \rm i i列的格子是在上下格子填完之後還是左右格子填完之後，是在目前聯通塊操作序列中第 j \rm j j個操作的方案數，那麼分類讨論上一列的格子通過哪種規則填來轉移。

記 S i z e \rm Size Size為目前聯通塊的大小， s u m \rm sum sum為目前列上下的空格子數：

• 如果上一個格子是通過填好上下格子再填的話，這個格子也通過填好上下格子再填，那麼這兩列是互不影響的。

  f ( 0 , i , j ) = ∑ k = 1 S i z e f ( 0 , i − 1 , k ) × A ( j − 1 , s u m ) \rm f(0,i,j)=\sum_{k = 1}^{Size}f(0,i-1,k)\times A(j-1,sum) f(0,i,j)=k=1∑Size​f(0,i−1,k)×A(j−1,sum)

• 如果上一個格子是通過填好左右格子再填的話，這個格子必須通過填好上下格子再填，那麼目前格子必須先填。

  f ( 0 , i , j ) = ∑ k = j − s u m − 1 S i z e f ( 1 , i − 1 , k ) × A ( j − 1 , s u m ) \rm f(0,i,j)=\sum_{k=j-sum-1}^{Size}f(1,i-1,k) \times A(j-1,sum) f(0,i,j)=k=j−sum−1∑Size​f(1,i−1,k)×A(j−1,sum)

• 如果這一個格子是通過填好左右格子再填的話，首先它必須不可以通過填上下格子再填，否則會算重，是以上下格子至少有一個在它之後填，而上一個格子必須通過填上下格子再填。我們枚舉上下格子有 k − 1 \rm k - 1 k−1個在目前格子之前填。

  f ( 1 , i + k , j ) = s u m ! × ( S i z e − j − k s u m − ( k − 1 ) ) × ( j + k − 1 k − 1 ) × ∑ t = 1 j f ( 0 , i − 1 , t ) \rm f(1,i+k,j)=sum!\times\binom{Size-j-k}{sum-(k-1)}\times\binom{j+k-1}{k-1}\times\sum_{t = 1}^{j}f(0,i-1,t) f(1,i+k,j)=sum!×(sum−(k−1)Size−j−k​)×(k−1j+k−1​)×t=1∑j​f(0,i−1,t)

複雜度 O ( n 2 ) O(\rm n^2) O(n2)，注意增加新聯通塊的時候的一些細節，還有最後一個聯通塊要特殊考慮。

#include <bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define mp make_pair
#define inf (0x3f3f3f3f)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(), x.end()
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define debug(x) cout << #x << " = " << x << endl
#define Rep(i, a) for (int i = 0, i##end = (a); i < i##end; ++ i)
#define For(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++ i)
#define Forr(i, a, b) for (int i = (a), i##end = (b); i >= i##end; -- i)
#define Travel(i, u) for (int i = head[u], v = to[i]; i; v = to[i = nxt[i]])

namespace IO { 

	const int N = 1e6;

	static char s[N], *S = s, *T = s, t[N], *E = t;

	inline void flush() { fwrite(t, 1, E - t, stdout), E = t; }

	inline char getc() {
		if (S == T) T = (S = s) + fread(s, 1, N, stdin);
		return S == T ? 0 : *S ++;
	}

	inline void putc(char c) {
		if (E == t + N - 1) flush();
		*E ++ = c;
	}
}

using IO::getc;
using IO::putc;
using IO::flush;
using namespace std;
using ll = long long;
using PII = pair <int, int>;

template <class T>
inline T read() {
	T ___ = 1, __ = getc(), _ = 0;
	for (; !isdigit(__); __ = getc())
		if (__ == '-') ___ = -1;
	for (; isdigit(__); __ = getc())
		_ = _ * 10 + __ - 48;
	return _ * ___;
}

template <class T>
inline void write(T _, char __ = '\n') {
	if (!_) putc(48);
	if (_ < 0) putc('-'), _ = -_;
	static int sta[111], tp;
	for (sta[tp = 0] = __; _; _ /= 10)
		sta[++ tp] = _ % 10 + 48;
	while (~tp) putc(sta[tp --]);
}

template <class T>
inline bool chkmax(T &_, T __) {
	return _ < __ ? _ = __, 1 : 0;
}

template <class T>
inline bool chkmin(T &_, T __) {
	return _ > __ ? _ = __, 1 : 0;
}

inline void proStatus() {
	ifstream t("/proc/self/status");
	cerr << string(istreambuf_iterator <char> (t), istreambuf_iterator <char> ());
}

const int N = 2000;
const int M = 6000;
const int mod = 1e9 + 7;

int fac[M + 5], ifac[M + 5];

int qpow(int a, int x) { 
	int ret = 1; 
	while (x) { 
		if (x & 1) ret = ret * (ll)a % mod;
		x >>= 1, a = a * (ll)a % mod;
	}
	return ret; 
}

void Math_Init(int n) { 
	fac[0] = ifac[0] = 1; 
	For(i, 1, n) fac[i] = fac[i - 1] * (ll)i % mod;
	ifac[n] = qpow(fac[n], mod - 2);
	Forr(i, n, 1) ifac[i - 1] = ifac[i] * (ll)i % mod;
}

ll A(int n, int m) { return n < m ? 0 : fac[n] * (ll)ifac[n - m] % mod; } 
ll C(int n, int m) { return n < m ? 0 : fac[n] * (ll)ifac[m] % mod * ifac[n - m] % mod; }

char S[3][N + 5];

int dp[2][N + 5][M + 5];
int n, sum, m, blk, ans = 1;

void Get_Sum(int x) { 
	Rep(i, 2) For(j, 1, n * 3)
		(dp[i][x][j] += dp[i][x][j - 1]) %= mod;
}

signed main() {

	Math_Init(M), scanf("%d", &n);
	Rep(i, 3) {
		scanf("%s", S[i] + 1);
		For(j, 1, n) {
			if ((i + 1) & 1 && S[i][j] == S[i][j - 1] && S[i][j] == 'x')
				return puts("0"), 0;
		}
		if ((i + 1) & 1 && (S[i][1] == 'x' || S[i][n] == 'x')) 
			return puts("0"), 0;
	}

	if (S[1][1] == 'x') 
		Get_Sum(blk = dp[0][1][1] = 1);

	For(i, 2, n) { 

		// dp[0 / 1][i][j]（從上下轉移還是左右）， 放完前i列 （2，i）是第j個放的。 
		// 有一個字首和 是以第三維代表（2，i）放置時間小于等于 j。
		
		sum = (S[0][i] == 'x') + (S[2][i] == 'x');
		if (S[1][i] == 'x') { 
			if (S[1][i - 1] == 'x') { 
				blk += sum + 1; 
				For(j, 1, blk) {
					(dp[0][i][j] += dp[0][i - 1][blk] * A(j - 1, sum) % mod) %= mod;
					// 兩個都是從上下轉移過來。
					(dp[0][i][j] += (dp[1][i - 1][blk] - dp[1][i - 1][max(0, j - 1 - sum)] + mod) * A(j - 1, sum) % mod) %= mod;
					// 上一個從左右轉移 目前從上下轉移
					// 放完目前棋子成了第j個，之前插入了sum個，那麼上一個格子就至少要是第 j - sum個
					For(k, 1, sum) (dp[1][i][j + k] += dp[0][i - 1][j] * C(j + k - 1, k - 1) % mod
							* fac[sum] % mod * C(blk - j - k, sum - k + 1) % mod) %= mod;
					// 枚舉自己上下有 k - 1 個在自己前 
					// 先從前面選k - 1個位置放上下
					// 上下内部是可以随便選的
					// 最後有sum - (k - 1)個上下放在後面 把後面留一些位置出來。
				}
			} else { 
				blk = sum + 1; 
				dp[0][i][sum + 1] = fac[sum]; // 從上下轉移
				if (sum >= 1) dp[1][i][1] = fac[sum]; //從左右轉移 那上下至少有一個在它後面
				if (sum >= 2) dp[1][i][2] = fac[sum]; //同上
			}
			Get_Sum(i);
		} else {
			if (S[1][i - 1] == 'x') 
				ans = ans * C(m += blk, blk) % mod * (dp[0][i - 1][blk] + dp[1][i - 1][blk]) % mod;
			ans = ans * A(m += sum, sum) % mod % mod;
		}
	}

	// 最後一個聯通塊可能沒算。
	if (S[1][n] == 'x') 
		ans = ans * C(m + blk, blk) % mod * dp[0][n][blk] % mod;

	write(ans);

	return flush(), 0;
}