LOJ #2731. 「JOISC 2016 Day 1」棋盘游戏（dp）

棋盘游戏（dp）"/>

LOJ #2731. 「JOISC 2016 Day 1」棋盘游戏（dp）

题意

JOI 君有一个棋盘，棋盘上有 \(N\) 行 \(3\) 列 的格子。JOI 君有若干棋子，并想用它们来玩一个游戏。初始状态棋盘上至少有一个棋子，也至少有一个空位。

游戏的目标是：在还没有放棋子的格子上依次放棋子，并填满整个棋盘。在某个格子上放置棋子必须满足以下条件之一：

1. 这个格子的上下一格都放有棋子；
2. 这个格子的左右一格都放有棋子。

JOI 君想知道有多少种从初始状态开始，并达到游戏目标的方案，这个答案可能会非常大。请你帮 JOI 君算出这个答案，并对 \(10^9+7\) 取模。

数据范围

对于所有数据，满足 \(1 \le N \le 2000\)。

题解

思维能力为 \(0\) 的 sb 帮你把 doe 的讲解搬过来啦。

显然对于每个 \(x\) 的联通块是可以单独考虑的。

首先把无解的情况全部判掉，例如有两个 \(x\) 连在一起就不行，或者 \(x\) 在四个角落也是不行的。

那么我们的联通块的形状就形如：

 x x x x
xxxxxxxxxx  x x

不难发现中间一行是一定连贯的，两边会不定时的出现 \(0/1/2\) 个空。

那么我们可以对于每个中间位进行考虑，因为上下位都是可以随时填进来的。

那么满足这个节点能填的方案只有，要么上下填了，要么左右填了，要么两个都填了。

这样的话我们可以设一个 \(f[i][j][0/1]\) 表示对于第 \(i\) 列中间空，它是在整个联通块第 \(j\) 个被填进去的，在它之前满足了 上下/左右 已经填好的方案数。

注意对于上下左右都填好的时候我们为了不算重，算到上下那里去。

然后对于转移，我们第 \(i\) 列如果选上下，那么 \(i + 1\) 列上下填是不会限制的，但是对于左右填要强制 \(i\) 列中间出现在 \(i + 1\) 列之前。

\(i\) 如果选左右，那么 \(i + 1\) 列不能选左右，只能选上下，并且要强制 \(i + 1\) 列出现在 \(i\) 列之前。

然后在联通块结束的时候用组合数算算方案就行了。

然后直接转移是 \(\mathcal O(n^3)\) 的，由于只有相对的大小关系才有意义，可以前缀和优化到 \(\mathcal O(n^2)\) 。

总结

对于填的方案计数，如果相关元素不多，我们通常可以考虑 \(i\) 填在全局第 \(j\) 个的方案数，然后转移的时候乘上一个排列/组合数就好了。

代码

具体转移的细节在代码中，可以参考。

#include <bits/stdc++.h>#define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endlusing namespace std;template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }inline int read() {int x(0), sgn(1); char ch(getchar());for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);return x * sgn;
}void File() {
#ifdef zjp_shadowfreopen ("2731.in", "r", stdin);freopen ("2731.out", "w", stdout);
#endif
}const int N = 4e3 + 1e2, Mod = 1e9 + 7;namespace Computation {inline int fpm(int x, int power) {int res = 1;for (; power; power >>= 1, x = 1ll * x * x % Mod)if (power & 1) res = 1ll * res * x % Mod;return res;}inline void add(int &x, int y) { if ((x += y) >= Mod) x -= Mod; }#define plus Plusinline int plus(int x, int y) { return (x += y) >= Mod ? x - Mod : x; }inline void sub(int &x, int y) { if ((x -= y) < 0) x += Mod; }inline int dec(int x, int y) { return (x -= y) < 0 ? x + Mod : x; }inline int mul(int x, int y) { return 1ll * x * y % Mod; }}using namespace Computation;int fac[N], ifac[N];void Math_Init(int maxn) {fac[0] = ifac[0] = 1;For (i, 1, maxn) fac[i] = mul(fac[i - 1], i);ifac[maxn] = fpm(fac[maxn], Mod - 2);Fordown (i, maxn - 1, 1) ifac[i] = mul(ifac[i + 1], i + 1);
}inline int comb(int n, int m) {if (n < 0 || m < 0 || n < m) return 0;return mul(mul(fac[n], ifac[n - m]), ifac[m]);
}inline int perm(int n, int m) {if (n < 0 || m < 0 || n < m) return 0;return mul(fac[n], ifac[n - m]);
}char S[3][N];int n, f[N][N][2];void get_pre(int x) {For (i, 1, n * 2) Rep (j, 2)add(f[x][i][j], f[x][i - 1][j]);//前缀和优化一维复杂度
}int main () {File();n = read();Rep (i, 3) scanf ("%s", S[i] + 1);Math_Init(n * 2 + 10);for (int i = 0; i <= 2; i += 2) For (j, 1, n) if (S[i][j] == 'x' && (S[i][j - 1] != 'o' || S[i][j + 1] != 'o'))return puts("0"), 0;int ans = 1, num = 0, tot = 0;if (S[1][1] == 'x')get_pre(f[1][1][0] = num = 1);For (i, 2, n) {int cur = (S[0][i] == 'x') + (S[2][i] == 'x');if (S[1][i] == 'x') {if (S[1][i - 1] == 'o') {f[i][cur + 1][0] = fac[cur];//横竖都可转移的时候，强制转移竖的if (cur >= 1) f[i][1][1] = fac[cur];if (cur >= 2) f[i][2][1] = 2;get_pre(i); num = cur + 1; continue;}num += cur + 1;For (j, 1, num) {add(f[i][j][0], mul(f[i - 1][num][0], perm(j - 1, cur)));//两个都是竖的，两个位置无先后要求，考虑当前上下插到中间前面的方案add(f[i][j][0], mul(dec(f[i - 1][num][1], f[i - 1][max(0, j - (cur + 1))][1]), perm(j - 1, cur)));//这个竖，上个横，那么这个中间位要比上一列中间位先填For (k, 1, cur) if (j + k <= num)add(f[i][j + k][1],mul(mul(fac[cur], comb(j + k - 1, k - 1)),//上下在中间位之前出现的方案数 与 上下互换的方案mul(comb(max(0, num - j - k), cur + 1 - k), f[i - 1][j][0])));//上下在中间位之后出现的方案数 以及//强制横的先出现，竖的出现在 0 那里统计}get_pre(i);} else {if (S[1][i - 1] == 'x')ans = mul(mul(ans, plus(f[i - 1][num][0], f[i - 1][num][1])), comb(tot += num, num));//把当前联通块塞到前面的方案数ans = mul(ans, perm(tot += cur, cur));//注意对于联通块首的上下位的方案数要单独计算}}if (S[1][n] == 'x')ans = mul(ans, mul(f[n][num][0], comb(tot += num, num)));//最后一个联通块可能没有统计，要统计上printf ("%d\n", ans);return 0;}

转载于:.html