详细揭秘：低秩矩阵分解与矩阵树定理极简证明

• 选取一个集合 $S\sube\{1,2,\dots,n\}$；
• $\forall i\in S$，将 $B_{i,*}$ 替换为 $A_{i,*}$；
• $\det(A+B)$ 的值等于所有子集 $S$ 得到的矩阵 $B'$ 的行列式之和；

例：矩阵树定理的证明

证明：给定一张图，令 $D,A$ 分别为图的度数矩阵、邻接矩阵，则任意选定 $x$ 并删除 $D,A$ 中的第 $x$ 行、第 $x$ 列后，$\det(D-A)$ 等于该图生成树个数。

• 如果选出了环，那么这些行加起来就是全零行，故对应贡献为 $0$。
• 如果没有任何环，那么考虑与 $x$ 相连的任意点 $p$，其只能选择 $(p,p)$ 上的 $1$，因为 $(p,x)$ 被删去了，依此递推可以得到贡献为 $1$。

例：Determinant

给定整数 $n,c$，求解 $n\times n$ 的矩阵 $A_{i,j}$ 的行列式： $A_{i,j}=\begin{cases}1,&i=j\\0,&i\ne j\land j\bmod i=0\\c,&\text{otherwise}\end{cases}$

对 $998244353$ 取模。

$n\le 10^9$。

后续优化可以移步完整题解查看。

例：能量场

给你一个长为 $n$ 的序列 $a_{1\dots n}$，定义一条边 $(u,v)$ 的权值为 $a_u+a_v$。对于一张图，定义其权值为包含的所有边的权值乘积。求所有 $n$ 个点的有标号基环树的权值之和。对 $998244353$ 取模。

$n\le 10^3$。

• $|S|=0$，$\prod_{i=1}^nd_i$；
• $|S|=1$，$-2\sum_{i=1}^na_i\prod_{j\ne i}d_j$；
• $|S|=2$，$\sum_{i=1}^n\sum_{j=i+1}^n(2a_ia_j-a_i^2-a_j^2)\prod_{k\ne i,k\ne j}d_k$。

后续优化可以移步完整题解查看。

思考：简单的生成树

给定两棵点数分别为 $n,m$ 的树 $T_1,T_2$ ，再构造一个无向图 $G$，$G$ 包含 $T_1,T_2$ 的所有点、树边，且还包含所有跨越 $T_1,T_2$ 的点对所组成的边。

求无向图 $G$ 的生成树个数，对 $10^9+7$ 取模。

$n,m\le 2\times 10^6$。

思考：Odd Namori

给定一个长为 $n-1$ 的序列 $p_{2\sim n}$，求满足下列条件的有向图的权值和：

• 每个顶点的出度都为 $1$。
• 图中不存在偶环。
• 对于所有 $i\in[2,n]$，图中不包含边 $i \to p_i$。

一张图的权值定义为 $2^c$，其中 $c$ 表示该图中的环数。答案对 $998244353$ 取模。

$n\le 2\times 10^6$。