[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;
}