向量
叉乘：\((x_1, y_1) \times (x_2, y_2) = x_1y_2 - x_2y_1\).
几何意义：这两个向量构成的有向平行四边形的面积。
行列式
一个方阵 \(A\) 的行列式记作 \(\det(A)\) 或 \(|A|\)，可以理解为高维空间的欧氏体积。
定义 \(P_n\) 表示所有 \(n!\) 个长度为 \(n\) 的排列 \(p\) 构成的集合。矩阵的行列式定义为：
其中 \(\operatorname{sgn}\) 表示 \((-1)^{排列逆序对个数}\).
性质：
- 对矩阵做行（列）交换，行列式反号；
- 对方阵做行（列）数乘，行列式乘上同样的常数；
- 对方阵做行（列）加法（即将矩阵的某一行（列）乘 \(k\) 加到另一行上），行列式不变；
- 对于上（下）三角矩阵，其行列式为主对角线的积。
于是可以通过高斯消元将矩阵变成上三角矩阵，就可以避免枚举排列求行列式。
#include <bits/stdc++.h>
using namespace std;#define int long long
const int N = 605;int a[N][N], n, mod, ans;signed main()
{ios :: sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> mod;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)cin >> a[i][j];int g = 1;for(int i = 1; i <= n; i++)for(int j = i + 1; j <= n; j++){while(a[i][i]){int x = a[j][i] / a[i][i];for(int k = i; k <= n; k++)a[j][k] = (a[j][k] - x * a[i][k] % mod + mod) %mod;swap(a[i], a[j]), g *= -1;}swap(a[i], a[j]), g *= -1;}ans = (g + mod) % mod;for(int i = 1; i <= n; i++)ans = 1ll * a[i][i] * ans % mod;cout << ans;return 0;
}
矩阵的逆
定义单位矩阵（Identity Matrix）为主对角线上元素为 \(1\)，其他元素为 \(0\) 的方阵，记作 \(I\)（乘法单位元）。
定义 \(A\) 的逆矩阵 \(B\) 为使得 \(AB = I\) 的矩阵。若存在这样的 \(B\) 矩阵，则称 \(A\) 可逆。\(A\) 的逆矩阵记作 \(A^{-1} = B\).
矩阵求逆：使用高斯消元将 \((A|I)\) 中的 \(A\) 消成 \(I\)，得到 \((I|B)\)，那么这里的 \(B\) 就是 \(A^{-1}\).
矩阵树定理
矩阵树定理（Matrix-Tree Theorem）是将图的生成树个数和矩阵行列式联系起来的一个定理。
有向图内向生成树计数：对于无自环（允许有重边）的有向图 \(G =(V,E)\)，设出度矩阵 \(D(G)\) 表示每个点的出度的对角矩阵（\(d_{i,i}\) 表示 \(i\) 号点的出度，其余位置均为 \(0\)）。而 \(A(G) = [a_{i, j}]\) 表示邻接矩阵，\(a_{i,j}\) 表示 \((i \to j)\) 的边数。那么可以得到对应的拉普拉斯矩阵（Laplace Matrix）\(L(G) = D(G) - A(G)\). 则有 \(L(G)\) 关于 \({L(G)}_{k, k}\) 的余子式（主子式）是以 \(k\) 为根的内向生成树的个数。
余子式：对于矩阵 \(A\)，\(A_{i, j}\) 的余子式定义为 \(A\) 去掉第 \(i\) 行第 \(j\) 列的矩阵的行列式，记作 \(|A_{[n] \backslash \{i\}, [m] \backslash \{j\}}|\).
证明：
只需证两个结论：
- \(|L(G)|\) 的组合意义是通过容斥计算 \(G\) 的只有平凡环（即自环）的基环内向生成森林的个数。
- \(|{L(G)}_{[n] \backslash \{k\}, [n] \backslash \{k\}}|\) 的组合意义是通过容斥计算 \(G\) 的以 \(k\) 为根的内向生成树的个数。
注：若一个图中没有自环，它就不存在只有平凡环的基环内向生成森林，也就是说对简单有向图，\(|L(G)| = 0\).
先证引理 \(1\).
定义 \(U = \{\text{所有 } n \text{ 个点的基环内向森林}\}\) 作为容斥的全集。P.S. \(|U| = \prod_{i = 1}^n \text{节点 } i \text{ 的出度}\)。
无法直接计算，因为非平凡环的总数太多了。
但是这个式子告诉我们：在容斥过程中，如果钦定了 \(t\) 个非平凡环要出现，那么这部分贡献的容斥系数就是 \((-1)^t\).
回顾行列式的定义：\(\displaystyle |L(G)| = \sum_{p \in P_n} \operatorname{sgn}(p) \prod_{i = 1}^n a_{i, p_i}\).
在行列式中，我们枚举了一个排列 \(p\).
首先分析排列的组合意义。如果我们让 \(i\) 向 \(p_i\) 连边，我们会得到若干个环（每个点恰好有一条出边，恰好一条入边）。也就是说枚举排列的组合意义是枚举 \(n\) 个点的环覆盖。
P.S. 环覆盖是指 \(n\) 个数划分为若干个环排列（单独的数视为长度为 \(1\) 的环，即平凡环）。
\(a_{i, p_i}\) 有两种情况：
- 若 \(i \ne p_i\)，此时 \(a_{i, p_i}\) 表示 \(i \to p_i\) 的边数的相反数；
- 若 \(i = p_i\)，此时 \(a_{i, p_i}\) 表示 \(i\) 的出度。
且该排列的行列式系数 \(\operatorname{sgn}(p)\) 是一个与排列奇偶性（即逆序对个数的奇偶性）相关的东西。
拆成两部分考虑：\(\displaystyle \operatorname{sgn}(p) \prod_{i = 1}^n a_{i, p_i} = \displaystyle \operatorname{sgn}(p) \prod_{i \ne p_i} a_{i, p_i} \times \prod_{i = p_i} a_{i, p_i} = \operatorname{sgn}(p) \prod_{i \ne p_i} -(i \to p_i \text{ 的边数}) \times \prod_{i = p_i} i \text{ 的出度}\).
注意到 \(i \ne p_i\) 的边会构成若干个非平凡环，故前半部分的组合意义为钦定这些非平凡环的方案数（原图可能有重边），乘上 \({(-1)}^{\text{钦定的非平凡环的环长之和}}\)（排列上的非平凡环就是图上钦定的非平凡环）。
后半部分意义：所有 \(i = p_i\) 的点任意选择一条出边的方案数。
合并两部分组合意义，\(\displaystyle \operatorname{sgn}(p) \prod_{i = 1}^n a_{i, p_i}\) 表达的组合意义是，钦定所有 \(i \ne p_i\) 的边构成的非平凡环必须出现，其他边随便连的基环内向森林方案数，乘上 \((-1)^{p \text{ 中非平凡环的环长之和}}\).
容斥过程中，如果钦定了 \(t\) 个非平凡环出现，那么这部分贡献的容斥系数就是 \((-1)^t\).
只需证明：这部分的系数，即 \({(-1)}^{\text{钦定的非平凡环的环长之和}}\)，就是 \((-1)^t\).
\(\operatorname{sgn}(p) = (-1)^{N(p)}\)，\(N(p)\) 表示排列 \(p\) 中逆序对个数。
注意到，对一个排列中的非平凡环，可以通过一次交换把这个换拆成一个平凡环和一个长度减一的环。而一次交换操作会使逆序对的奇偶性发生变化，也就是说，交换操作数和逆序对变化量的奇偶性相同。
设 \(p\) 的非平凡环的环长之和为 \(l\)，且 \(p\) 有 \(t\) 个非平凡环，则执行 \((l-t)\) 次交换操作，就可以消除所有非平凡环。这是我们会得到单位排列，逆序对数量为 \(0\)（偶数）。
因此 \((-1)^{N(p)} = (-1)^t\)，左边是逆序对变化量的奇偶性，右边是交换操作的奇偶性。于是 \(\operatorname{sgn}(p) \times (-1)^{p \text{ 中非平凡环的环长之和}}\space \space \space \space \space \space \space \space \space = (-1)^l \times (-1)^{l - t} = (-1)^t\).
如何理解 \(|{L(G)}_{[n] \backslash \{k\}, [n] \backslash \{k\}}|\)？
容斥的过程是，在 \(\{1, 2, \cdots, n\} \backslash \{k\}\) 中钦定非平凡环出现，其他点随便连边（可连到 \(k\)，因为其他点的出度包含到 \(k\) 的边）的方案数，乘上一个系数.
那么这个容斥的结果将会是：\(\{1,2,\cdots, n\}\backslash \{k\}\) 中不存在非平凡环，且其中每个点都要连出去一条边的方案数。
删掉了第 \(k\) 行、第 \(k\) 列，则容斥过程中不会考虑从 \(k\) 出发的边，即 \(k\) 被视为根节点，没有出边。
其他每个点都要连出去一条边，且不能出现非平凡环。若原图没有自环，那么这样构造出来的必然是一个以 \(k\) 为根的内向生成树。