菜鸡博主开始看matrix tree定理辣！

今天在hackerrank上刷水时，突然发现一个150pts的题，可是我不会（我好菜啊.jpg）（附链接: https://www.hackerrank.com/challenges/alex-vs-fedor ）

打开editorial,发现是生成树计数相关，要用matrix tree定理，然后就一脸懵逼(智力-=2)，决定学习matrix tree定理这个神奇的东西。

以下内容纯属博主口胡，不足之处希望dalao予以指出与更正。

前置技能：矩阵的行列式 (线代大佬们请手动忽略)

对于矩阵A[n][n]，det(A)=sigma(sign*(A[1][p1]*A[2][p2]*...*A[n][pn])).

其中,p1....pn是1....n的一个排列，而sign=(-1)^( inv(p) mod 2)，inv(p)=排列p中的逆序对数量.

矩阵行列式的一些性质：

1. 一个矩阵行列互换(A'[i][j]=A[j][i])得到矩阵A’，det(A)=det(A')

    这个性质，根据行列式的定义，显然成立。

2.互换行列式两行或两列的位置，det(A')=-det(A).

   若交换了i,j两行，考虑对于A矩阵的排列p=p1,p2...pi...pj....pn，不考虑符号，其对答案的贡献为s1=A[1][p1]*A[2][p2]*....*A[n][pn].

                                  再考虑对于A’矩阵的排列p‘=p1,p2....pj...pi....pn,不考虑符号，其对答案的贡献s2=A'[1][p1]*...A'[i][pj]*...*A'[j][pi]*....*A'[n][pn].

   因为只有i,j两行发生了交换，显然有s1=s2，而两个排列p与p’只有在i,j位置发生了互换，此时逆序对的奇偶性发生变化（对于中间的数分类讨论即可证明），sign符号相反.

   由此就可以得出结论2.

   一个很妙的推论：若矩阵第i行与第j行的值完全相同，det=0

3.矩阵A中某一行的元素全部乘以常数k，则det(A')=k*det(A).

  由行列式的定义，显然成立。

4. 由2,3可以得到，若存在1<=i,j<=n,k为实数满足A[i][l]=k*A[j][l]对于所有1<=l<=n均成立，则det(A)=0.

5. 将第i行所有元素加上任意其他行元素的实数倍，det(A)不变.

    证明: 考虑排列p1,p2,p3.....pn对于答案的贡献，

             原始矩阵:s1=sign*A[1][p1]*A[2][p2]*....*A[n][pn]，

             新矩阵: s2=sign*A[1][p1]*A[2][p2]*...*A[n][pn]+sign*k*A[1][p1]*A[2][p2]*..*A[j][pi]*..A[n][pn].

    而sigma(s2-s1)=0，所以得证（Why?---------转至定理4）

有了这些，下面就将介绍一种O(n^3)求解矩阵行列式的一种办法，

这种办法类似于高斯消元，通过将矩阵消成上三角矩阵进行行列式的求解，

对于上三角矩阵行列式的求解，显然det(A)=A[1][1]*A[2][2]*....*A[n][n].

具体步骤: 对于第i行，我们希望将满足i+1<=j<=n的A[j][i]的值变为0 。

                 所以考虑过程gauss(i,j)表示将第j行第i项消为0。

                 由定理5，可以考虑构造实数k使得A’[j][i]=0.

                                    解方程A[j][i]+k*A[i][i]=0.

                                    则k=(-A[j][i])/A[i][i].

                 通过定理5，我们可以将第j行元素加上第i行同列元素的k倍从而实现消元过程。

                 这样就可以O（n^3）实现矩阵行列式的求解。

附上博主的代码(博主码风不是很和谐，希望dalao们不要吐槽):

注:此代码并没有经过检验，若有问题，还望大牛指正！

 
#include <bits/stdc++.h>
#define eps 1e-8
using namespace std;
double a[305][305];
int n;
inline double calc()
{int i,j,k;
for (i=1;i<=n;i++)
{if (a[i][i]<eps&&a[i][i]>-eps) {return 0;}
for (j=i+1;j<=n;j++)
{double rat=(-a[j][i])/a[i][i];
for (k=i;k<=n;k++)
{a[j][k]+=a[i][k]*rat;}
}
}
double ret=1;
for (i=1;i<=n;i++)
{ret*=a[i][i];}
return ret;
}
int main (){
	int i,j;
	scanf ("%d",&n);
	for (i=1;i<=n;i++)
	{for (j=1;j<=n;j++)
	{scanf ("%lf",&a[i][j]);}
	}
	printf ("%.6lf\n",calc());
	return 0;
}


嗯，没错，有关行列式的部分就是这样，

毕竟博主太弱，一天只能看这么点内容，

有关matrix tree定理的介绍就请看下一篇辣！