[SHOI2016]黑暗前的幻想乡 & 矩阵树学习笔记

这题的主要特点是一旦了解所用算法就非常模板。
那么前置知识就是 容斥原理 和 矩阵树定理。

即便没有学过容斥，理解本题容斥思路也很容易。

给定一个有重边无自环无向图，每条边有一个颜色，考虑如何计算它的 所有 \(n-1\) 条树边颜色互不相同 的生成树个数。

上面是举了一个例子。事实上，一般地：

\[ANS(T=\{1,2,...,n-1\})=\sum_{i=n-1}^0\left((-1)^{n-1-i}\sum_{|S|=i,S\subseteq\{1,2,...,n-1\}}ANS(T\subseteq S)\right) \]

如何求 \(ANS(T\subseteq S)\) 呢？显然这个时候我们就是已知一张新图，需要求这个新图的生成树数量。我们了解到，Matrix-Tree 定理（矩阵树定理）就是用来干这个事的，于是就很板了。

什么是 Matrix-Tree 定理

1.Kirchhoff 矩阵

Kirchhoff 矩阵（又称拉普拉斯矩阵） \(L=V-E\)，其中 \(V\) 定义为 \(V_{i,i}=deg_i,V_{i,j}=0(i\ne j)\)，\(E\) 为无向图的邻接矩阵（当然关于对角线对称）。矩阵减法是指两个矩阵对应位置上的数相减，即 \(L_{i,j}=V_{i,j}-E_{i,j}\)。

2.余子式

一个矩阵同时去掉某些行、某些列后得到新矩阵的行列式的是他的一个余子式。

3.矩阵行列式

矩阵行列式 针对的是一个 \(n\times n\) 的矩阵。其定义式为

\[\det(A)=\sum_p(-1)^{\tau(p)}\prod_{i=1}^n a_{i,p_i} \]

其中 \(p\) 为一个 \(1\sim n\) 的全排列，\(\tau(p)\) 表示 \(p\) 的逆序对数。\(\det(A)\) 的另一种记法为 \(|A|\)。

这个式子极少用来直接求解。对矩阵行列式的简单理解方式为 一个矩阵的定义新运算“值”。

矩阵行列式性质

矩阵行列式经过矩阵初等变换后值会发生调整，具体地：

1. 交换矩阵的两行或两列，\(\det(A')=-\det(A)\)。
2. 交换矩阵的一行和一列，\(\det(A’)=\det(A)\)。
3. 矩阵的一行同 \(\times k\)，行列式同时 \(\times k\)。

\[\begin{vmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,n}\\ a_{2,1} &a_{2,2} &\cdots &a_{2,n}\\ \vdots &\vdots &\ddots &\vdots\\ k\times a_{i,1} &k\times a_{i,2} &\cdots &k\times a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1} &a_{n,2} &\cdots &a_{n,n}\\ \end{vmatrix} =k\times \begin{vmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,n}\\ a_{2,1} &a_{2,2} &\cdots &a_{2,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{i,1} &a_{i,2} &\cdots &a_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1} &a_{n,2} &\cdots &a_{n,n}\\ \end{vmatrix} \]

4. 矩阵的一行加上另一行的若干倍，行列式不变。

在这部分内容中，我们需要用到的是规律 1 和 4。

4.Matrix-Tree 定理

一个图的生成树个数为它的 Kirchhoff 矩阵的去掉第 \(i\) 行、第 \(i\) 列的余子式，\(i\) 任意。

通常为了方便，我们选 \(i=n\)。

5.用高斯消元求矩阵行列式

在初学阶段，一些看起来 forbidding 的推导过程可能不利于理解，因此在这里直接摆结论：

• 求一个矩阵的行列式可以通过将它利用矩阵初等变换化为一个 上三角矩阵 后计算。
• 上三角矩阵的行列式等于其对角线的数乘积，即

而将一个一般的矩阵化为上三角矩阵，就可以通过高斯消元的方法。

下面展示出高斯消元求解线性方程组的核心代码。

int a[N][N];
for(int i=1;i<=n;i++)
    for(int p=1;p<=n;p++)if(p!=i){
        double d=a[p][i]/a[i][i];
        for(int q=1;q<=n+1;q++)a[p][q]-=d*a[i][q];
    }

这里我们是用的小数，但是现在说在 \(\bmod p\) 下的答案，就不能这么干了。于是我们项要求 \(a[i][i]\) 的逆元，但这是不可能的因为有可能它没有逆元，而且里面的数一直在变会要求很多次也是不可能的。

这里介绍一种辗转相除的方法。你在求 gcd 的时候用过，但其实它的作用不止于求 gcd 还正可以用来消元！因为最后一定会有两数中的一个变成了 0，把这个 0 给到上面 \(a[p][i]\) 的位置，就实现了消元，而在此过程中，我们不断地辗转相减第 \(i,p\) 两行的数，进行矩阵初等变换，并适时调整 \(\det\) 的值。具体见：

for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++){
        while(a[i][i]){
            int d=a[j][i]/a[i][i];
            for(int k=1;k<=n;k++)a[j][k]=(a[j][k]-1ll*d*a[i][k]%mod+mod)%mod;
            swap(a[i],a[j]),det=-det;//交换两行，根据规律1，det要变成相反数
        }
        swap(a[i],a[j]),det=-det;
    }

这样一来求本题要求的生成数个数就不在话下了，代码：

#include 
using namespace std;
const int mod=1e9+7;
int n,ans,m[18],e[18][18],cnt[18];
pairq[18][180];
int sol(int s){
	memset(e,0,sizeof(e));
	for(int i=0;i>i)&1){
		for(int j=1;j<=m[i];j++)
			e[q[i][j].first][q[i][j].second]--,e[q[i][j].second][q[i][j].first]--,
			e[q[i][j].first][q[i][j].first]++,e[q[i][j].second][q[i][j].second]++;
	}
	int det=1;
	for(int i=1;i>n;
	for(int i=0;i>m[i];
		for(int j=1;j<=m[i];j++)cin>>q[i][j].first>>q[i][j].second;
	}
	for(int i=0;i<(1<<(n-1));i++)(cnt[__builtin_popcount(i)]+=sol(i))%=mod;
	for(int i=n-1,j=1;~i;i--,j=-j)ans=((ans+j*cnt[i]%mod)%mod+mod)%mod;//注意这个地方，卡了我好久，一个取模都不能掉！
	cout<