A6166. 「USACO 2021 US Open Platinum」Balanced Subsets
编程题
省选/NOI-
知识点
题目描述
**题目来自 [USACO 2021 US Open Contest, Platinum](http://usaco.org/index.php?page=open21results) Problem 3. [Balanced Subsets](http://usaco.org/index.php?page=viewproblem2&cpid=1142&lang=zh)**
Farmer John 的草地可以被看作是由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘），对于每一个 $1\le i\le N$、$1\le j\le N$，方格可以用有序对 $(i,j)$ 表示（$1\le N\le 150$）。某些方格中含有草。
方格的一个非空子集被称为是「平衡的」，如果以下条件成立：
1. 所有子集中的方格均含有草。
2. 子集是四连通的。换句话说，从子集中的任一方格到另一方格均存在一条路径使得路径中的相邻方格均水平或竖直方向上相邻。
3. 如果方格 $(x_1,y)$ 和 $(x_2,y)$（$x_1\le x_2$）存在于子集中，那么所有满足 $x_1\le x\le x_2$ 的方格 $(x,y)$ 也存在于子集中。
4. 如果方格 $(x,y_1)$ 和 $(x,y_2)$（$y_1\le y_2$）存在于子集中，那么所有满足 $y_1\le y\le y_2$ 的方格 $(x,y)$ 也存在于子集中。
计算平衡的子集数量模 $10^9+7$ 的结果。
Farmer John 的草地可以被看作是由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘），对于每一个 $1\le i\le N$、$1\le j\le N$，方格可以用有序对 $(i,j)$ 表示（$1\le N\le 150$）。某些方格中含有草。
方格的一个非空子集被称为是「平衡的」，如果以下条件成立：
1. 所有子集中的方格均含有草。
2. 子集是四连通的。换句话说，从子集中的任一方格到另一方格均存在一条路径使得路径中的相邻方格均水平或竖直方向上相邻。
3. 如果方格 $(x_1,y)$ 和 $(x_2,y)$（$x_1\le x_2$）存在于子集中，那么所有满足 $x_1\le x\le x_2$ 的方格 $(x,y)$ 也存在于子集中。
4. 如果方格 $(x,y_1)$ 和 $(x,y_2)$（$y_1\le y_2$）存在于子集中，那么所有满足 $y_1\le y\le y_2$ 的方格 $(x,y)$ 也存在于子集中。
计算平衡的子集数量模 $10^9+7$ 的结果。
输入格式
输入的第一行包含 $N$。
以下 $N$ 行每行包含一个长为 $N$ 的字符串。如果方格 $(i,j)$ 中有草，则第 $i$ 行的第 $j$ 个字符为
以下 $N$ 行每行包含一个长为 $N$ 的字符串。如果方格 $(i,j)$ 中有草，则第 $i$ 行的第 $j$ 个字符为
G，否则为 .。输出格式
输出平衡的子集数量模 $10^9+7$ 的结果。
输入输出样例
输入 #1
2 GG GG
输出 #1
13
输入 #2
4 GGGG GGGG GG.G GGGG
输出 #2
642
说明/提示
- 测试点 1-4 满足 $N\le 4$。
- 测试点 5-10 满足 $N\le 20$。
- 测试点 11-20 没有额外限制。
供题：Benjamin Qi
- 测试点 5-10 满足 $N\le 20$。
- 测试点 11-20 没有额外限制。
供题：Benjamin Qi