题意

一个 $n\times n$ 的方阵中，有些点可以放洒水器，有些点不能放。洒水器有两个种类：一个种类可以让它和它的左下角变成 $\texttt{C}$ ，一个种类可以让它和它的右上角变成 $\texttt{A}$ ，现在问放洒水器的方案数使得每个格子有且仅有一个字符。

$n\leq2000$ 。

题解

好题！

这个方阵一定会被一条轮廓线分成两部分，那么 DP 维护这个轮廓线方案数。设 $f_{i,j,0/1}$ 表示以 $(i,j)$ 的右下角为轮廓线的最后点，最后的线时向右或向下的方案数。

代码

const int N = 2010, mod = 1e9 + 7;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	char a[N][N];
	ll qpow (ll a, ll b) {
		ll ans = 1;
		for (; b; b >>= 1, a = a * a % mod)
			if (b & 1) ans = ans * a % mod;
		return ans;
	}
	ll f[N][N][2], cnt, inv2 = 5e8 + 4;
	int main () {
		n = Read();
		for (int i = 1; i <= n; i++) {
			scanf ("%s", a[i] + 1);
			for (int j = 1; j <= n; j++) cnt += a[i][j] == '.';
		}
		f[0][0][0] = f[0][0][1] = qpow(2, cnt);
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= n; j++) {
				if (i) {
					(f[i][j][0] += f[i - 1][j][0]) %= mod;
					if (a[i][j] == '.') (f[i][j][0] += f[i - 1][j][1] * inv2 % mod) %= mod;
				}
				if (j) {
					(f[i][j][1] += f[i][j - 1][1]) %= mod;
					if (a[i][j] == '.') (f[i][j][1] += f[i][j - 1][0] * inv2 % mod) %= mod;
				}
			}
		}
		printf ("%lld\n", (f[n][n][0] + f[n][n][1]) % mod);
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}