poj-2170 Lattice Animals *****

这是一道比较经典的计数问题。题目描述如下：

给定一个 $n \times n$ 的网格图，其中一些格子被标记为障碍。一个连通块是指一些被标记为障碍的格子的集合，满足这些格子在网格图中连通。一个格子是连通的当且仅当它与另一个被标记为障碍的格子在网格图中有公共边。

现在，你需要计算在这个网格图中，有多少个不同的连通块，满足这个连通块的大小（即包含的格子数）恰好为 $k$。

这是一道比较经典的计数问题，一般可以通过计算生成函数的方法来解决。具体来说，我们可以定义一个生成函数 $F(x)$，其中 $[x^k]F(x)$ 表示大小为 $k$ 的连通块的个数。那么，我们可以考虑如何计算这个生成函数。

对于一个大小为 $k$ 的连通块，我们可以考虑它的形状。具体来说，我们可以考虑以该连通块的最左边、最上边的格子为起点，从上到下、从左到右遍历该连通块，把每个格子在该连通块中的相对位置记录下来。由于该连通块的大小为 $k$，因此这些相对位置一定是 $(x,y) \in [0,n-1]^2$ 中的 $k$ 个不同点。

现在，我们需要考虑如何计算这些点对应的连通块是否合法。具体来说，我们可以考虑从左到右、从上到下依次处理这些点，对于每个点 $(x,y)$，我们需要考虑它是否能够与左边的点和上边的点连通。具体来说，如果 $(x-1,y)$ 和 $(x,y)$ 都在该连通块中且它们在网格图中有公共边，那么它们就是连通的；同样，如果 $(x,y-1)$ 和 $(x,y)$ 都在该连通块中且它们在网格图中有公共边，那么它们也是连通的。如果 $(x,y)$ 与左边和上边的点都不连通，那么说明这个点不属于该连通块。

考虑到每个点最多只有两个方向需要检查，因此时间复杂度为 $O(n^2 k)$。不过，我们可以使用类似于矩阵乘法的思想，将这个过程优化到 $O(k^3)$ 的时间复杂度。

具体来说，我们可以设 $f_{i,j,k}$ 表示状态 $(i,j)$ 所代表的点在连通块中，且连通块的大小为 $k$ 的方案数。显然，对于一个合法的 $(i,j,k)$，我们可以考虑 $(i-1,j,k-1)$ 和 $(i,j-1,k-1)$ 这两个状态，然后把点 $(i,j)$ 加入到它们所代表的连通块中。因此，我们可以设计一个 $O(k^3)$ 的 DP 状态转移，计算 $f_{i,j,k}$。

具体来说，我们可以考虑枚举连通块所包含的最右边和最下边的格子的坐标 $(x,y)$，然后计算 $f_{x,y,k}$。对于一个合法的 $(x,y,k)$，我们可以考虑将 $(x,y)$ 所代表的点加入到 $(x-1,y,k-1)$ 和 $(x,y-1,k-1)$ 所代表的连通块中。不过，这里需要注意一个细节：如果 $(x-1,y)$ 和 $(x,y)$ 在网格图中没有相邻边，那么它们不能算作连通的。因此，我们需要特判这个情况。

最终，$f_{n,n,k}$ 就是大小为 $k$ 的连通块的个数，时间复杂度为 $O(n^2 k + k^3)$。

参考代码：