「Codeplus 2」白金元首与独舞（矩阵树定理）

题目大意

「Codeplus 2」白金元首与独舞（Luogu 4033）

给定 $n \times m$ 的棋盘，每个格子上要么有一个指向上、下、左、或右的箭头，要么是空白的。现在你要在所有空白的格子中填入箭头，使得从图中任意一个格子出发，每次按照当前格子中箭头的方向走一步，都一定能走到棋盘的外面。问一共有多少种填法$\bmod 10^9 + 7$ 的结果。

数据范围：$n, m \le 200$，空格子的个数 $k \le 300$。

思路分析

首先我们将棋盘外的空间视作一个虚点。发现如果一个填好的棋盘是合法的，那么我们将每个格子向它指向的格子连一条有向边（如果它指向棋盘外，那么就连向虚点）后，一定会形成一个以该虚点为根的内向树。于是这个问题就转化成了一个生成树计数的问题了。将每个格子向四周连四条边，其他格子照常连边，然后求建好的图以虚点为根的内向树个数即可。

这里简要讲解一下生成树计数的过程。对于一张无向图，我们构造矩阵 $K = D - A$，其中 $K$ 是基尔霍夫矩阵，$D$ 是度数矩阵，$A$ 是邻接矩阵。根据矩阵树定理，这张图的不同生成树个数等于其基尔霍夫矩阵 $K$ 的任意一个主余子式，其中主余子式表示去掉第 $i$ 行第 $i$ 列的余子式，即 $M_{i, i}$。对于一张有向图，如果要求的是外向树个数，那么度数矩阵中的度数就是入度；如果要求的是内向树个数，那么度数矩阵中的度数就是出度。之后，如果要求以 $x$ 为根的生成树个数，那么答案就是 $M_{x, x}$。

但是直接这么做点数是 $O(nm)$ 的，时间复杂度为 $O(n^3 m^3)$。我们考虑缩点，从每个点的相邻的格子开始一直走，知道碰到另外一个点或者走出棋盘。那么，我们从原来的点向走到的线连一条边，然后求生成树个数即可。这样点数就减少到了 $O(k)$，求生成树个数的部分的复杂度为 $O(k^3)$，但是之前建边的复杂度是 $O(k n m)$ 的，不够优秀。我们使用记忆化搜索，就把建边优化到了 $O(nm)$。这样总时间复杂度 $O(nm + k^3)$，可以通过本题。

听说还有个 $O(2^{\sqrt k})$ 的做法？太神仙了，我怎么可能会啊！

代码实现

#include <cstdio>