题意

我们有一个 $N \times 3$ 的棋盘，初始有一些棋子（o）和空位（x）。要按特定规则放置棋子直到填满整个棋盘。

放置规则：在空格放棋子必须满足以下条件之一：

1. 上下相邻格都有棋子
2. 左右相邻格都有棋子

目标：计算从初始状态到填满棋盘的所有合法放置序列的数量，对 $10^9+7$ 取模。

---

关键观察

1. 放置条件的组合意义

规则实际上要求：新放的棋子必须被"支撑"住：

• 垂直支撑：上下都有棋子
• 水平支撑：左右都有棋子

这意味着棋子只能放在已有棋子形成的"框架"上。

2. 状态压缩表示

由于只有 $3$ 行，我们可以用状态压缩表示每一列的棋子情况：

• 用 $3$ 位二进制数表示一列，第 $i$ 位为 $1$ 表示该行有棋子
• 共 $2^3 = 8$ 种状态：$000, 001, 010, 011, 100, 101, 110, 111$

3. 放置的局部性

放置一个棋子只影响局部区域，主要考虑：

• 当前列的状态变化
• 与相邻列的相互作用

---

算法思路：动态规划

状态设计

设 $dp[i][mask]$ 表示：

• 已经处理了前 $i$ 列
• 第 $i$ 列的状态为 $mask$（$0 \leq mask \leq 7$）
• 且前 $i$ 列的所有格子都已放置棋子

的方案数。

状态转移

从 $dp[i][mask]$ 转移到 $dp[i+1][newMask]$，需要：

1. 第 $i+1$ 列的初始状态由输入确定
2. 按照规则依次放置第 $i+1$ 列的空格
3. 放置过程中每一步都必须合法

放置顺序的处理

关键难点：在同一列内，放置顺序影响合法性。

解决方案：预处理所有可能的放置序列。

对于一列从状态 $start$ 到状态 $target$ 的所有合法放置序列：

• 枚举所有可能的放置顺序
• 检查每一步是否满足放置条件
• 统计合法序列数量

---

详细算法步骤

步骤1：预处理单列转移

对于每一对状态 $(start, target)$，其中 $start \subseteq target$（只能增加棋子），计算从 $start$ 到 $target$ 的所有合法放置序列数 $trans[start][target]$。

步骤2：检查放置条件

步骤3：DP转移

处理水平支撑

水平支撑是本题最复杂的部分。棋子 $(r, c)$ 的水平支撑要求：

• $(r, c-1)$ 和 $(r, c+1)$ 都有棋子

这意味着放置 $(r, c)$ 时：

• 如果 $c-1$ 列的第 $r$ 行有棋子
• 且 $c+1$ 列的第 $r$ 行最终会有棋子（但不一定是现在）

解决方案：在状态中额外记录"承诺"信息。

改进的状态设计

设 $dp[i][mask][promise]$，其中：

• $mask$：第 $i$ 列的状态
• $promise$：对第 $i+1$ 列的承诺（哪些位置最终会有棋子）

这样就能正确计算水平支撑。

---

复杂度分析

• 状态数：$O(N \times 8 \times 8) = O(64N)$
• 转移数：每状态最多 $8$ 种选择
• 总复杂度：$O(512N)$，对于 $N=2000$ 可行

---

样例验证

样例1

输入：
3
oxo
xxo  
oxo

初始状态：
第0列: 101 (oxo) -> 5
第1列: 001 (xxo) -> 1  
第2列: 101 (oxo) -> 5

通过DP计算得到14种方案

样例3

初始状态不连通或无法满足放置条件
DP结果为0

---

总结

这道题的关键在于：

1. 状态压缩：利用棋盘只有3行的特性
2. 放置条件分析：正确处理垂直和水平支撑
3. 承诺机制：处理跨列的水平支撑条件
4. 序列枚举：预处理所有合法的放置顺序