Balanced Subsets

题目描述

Farmer John 的牧场可以看作一个巨大的二维方格网格（想象一个很大的棋盘），每个正方形“格子”用有序对 $(i,j)$ 标记，其中 $1\le i\le N$, $1\le j\le N$（$1\le N\le 150$）。有些格子里有草。

如果一个非空的格子子集满足以下条件，则称其为“平衡”（balanced）： 所有在子集中的格子都包含草。 子集是 4-连通的。也就是说，从子集中任意一个格子到子集中任意另一个格子，都存在一条路径，使得路径上任意两个相邻格子在水平或垂直方向相邻。 如果格子 $(x_1,y)$ 和 $(x_2,y)$（$x_1\le x_2$）都在子集中，那么所有满足 $x_1\le x\le x_2$ 的格子 $(x,y)$ 也都在子集中。 如果格子 $(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$ 个字符：若为 G，则表示格子 $(i,j)$ 包含草；否则为 .。

输出格式

输出平衡子集的数量，对 $10^9+7$ 取模。

2
GG
GG

13

4
GGGG
GGGG
GG.G
GGGG

642

提示

对于该测试用例，所有 4-连通的子集都是平衡的。 G. .G .. .. GG .G .. G. GG .G G. GG GG .., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG

下面是一个满足第二个条件（它是 4-连通）但不满足第三个条件的子集示例： GG.. .G.. GG.. ....

评分（SCORING）： 测试点 1-4 满足 $N\le 4$。 测试点 5-10 满足 $N\le 20$。 测试点 11-20 没有额外限制。 题目来源：Benjamin Qi

标签: USACO|2021|Platinum

来源

USACO|2021|Platinum