以前接触了好多次行列式的题，然后口胡了好多行列式的做法，但到现在我也没写过行列式的题。准备恶补一下。
对一个N×NN×N矩阵A=⎡⎣⎢⎢⎢⎢a11a21⋮an1a12a22⋮an2⋯⋯⋱⋯a1na2n⋮ann⎤⎦⎥⎥⎥⎥A=[a11a12⋯a1na21a22⋯a2n⋮⋮⋱⋮an1an2⋯ann]，
定义它的行列式detA=|A|=∑P(−1)τ(P)∏iaiPidetA=|A|=∑P(−1)τ(P)∏iaiPi。
其中τ(P)τ(P)是排列PP的逆序对数。大大大
大大
这个定义了解一下就可以了，计算是阶乘复杂度，顶多用于二阶或三阶行列式。
最基本的性质几条：
转置行列式不变。
交换行列式两行（列），行列式取反。
同一行（列）乘数KK，行列式乘数KK。
如果两行（列）成比例，行列式为00。
一行（列）加上另一行（列）的KK倍，行列式不变。
detA=detATdetA=detAT
detA⋅detB=detABdetA⋅detB=detAB
detA≠0⇔rank(A)=n⇔∃B,A×B=I⇔detA≠0⇔rank(A)=n⇔∃B,A×B=I⇔所有行（列）向量线性无关。
行列式的组合意义是NN维空间下NN个向量组成的一个NN维体的有向体积。
二阶或者三阶行列式可以阶乘算。
二阶：detA=v1×v2=ad−bcdetA=v1×v2=ad−bc
三阶：detA=a1b2c3+a2b3c1+a3b1c2−a1b3c2−a2b1c3−a3b2c1detA=a1b2c3+a2b3c1+a3b1c2−a1b3c2−a2b1c3−a3b2c1
高阶的消成上三角矩阵。
有这么个定理：
上三角矩阵的行列式detA=∏iaiidetA=∏iaii。直接暴力带入原计算式可以证得。
正好可以发现如果∃aii=0∃aii=0，说明矩阵无逆，则detA=0detA=0。
利用行对换和一行乘另一行KK倍，使用辗转相除来实现类似高斯消元的过程。要注意行对换的时候行列式取反。这个复杂度是O(N3logN)O(N3logN)。
选定一个(i,j)(i,j)，删去行列式的第ii行和第jj列，留下的部分的行列式就是元素aijaij的余子式，记为MijMij。
aijaij的代数余子式Aij=(−1)i+jMijAij=(−1)i+jMij
aijaij的代数余子式AijAij与aijaij的值无关，仅与其位置有关。
∑iakiAki=detA∑iakiAki=detA
∑iakiAli=0(k≠l)∑iakiAli=0(k≠l)
用这个定理可以多次单点修改询问行列式。
从平面上NN个点依次连到另NN个点，不相交路径的方案数是一个行列式，其中aijaij表示一侧第ii个点连到另一侧第jj个点的方案数。
考虑两个相交的路径，在第一个交点对换后续路径的话相当于交换排列中两个数，容斥一下即可。
先讨论无向图。
定义度数矩阵DD，其中dii=degree(i)dii=degree(i)。
再定义邻接矩阵AA，其中aij=−[link(i,j)]aij=−[link(i,j)]。
则这个无向图的基尔霍夫矩阵C=D−AC=D−A。
CC的每行每列和均为00，所以detC=0detC=0。
生成树个数是MiiMii，即主对角线上的任意一个元素的余子式。
如果图是有向图，考虑求内向树还是外向树，度数和邻接变得有向，再枚举根，求这个根在主对角线上的元素的余子式。
另外，对于完全图的基尔霍夫矩阵，对角线元素的余子式Mii=nn−2Mii=nn−2。（和Prufer序列结果相同）
