生成树计数

发表于 | 分类于 | 阅读次数:

这两天阴差阳错的研究了邹等周冬前辈的两篇论文～～
##理论
###图的关联矩阵
对于无向图 $G$ ，我们定义它的关联矩阵 $B$ 是一个 $n\times m$ 的矩阵，并且满足：如果 $e_k=(v_i,v_j)$ ，那么 $B_{ik}$ 和 $B_{jk}$ 一个为 $1$ ，另一个为$-1$ ，而第 $k$ 列其它元素均为 $0$ 。

举例说明：
1

对于此图 $G$ ，其矩阵如下：
$$
\begin{bmatrix}
1 & -1 & 0 \[0.3em]
-1 & 0 & -1 \[0.3em]
0 & 1 & 1
\end{bmatrix}
$$

###Kirchhoff 矩阵
为研究 $B$ 的性质，我们需要考察一下 $B$ 与 $B$ 的转置矩阵（把矩阵 $A$ 的行换成相应的列，得到的新矩阵称为 $A$ 的转置矩阵，记作 $A^T$ ） $B^T$ 的乘积，根据矩阵乘法法则，我们可以得到：$$BB_{ij}^T=\sum_{k=1}^mB_{ik}B_{kj}^T=\sum_{k=1}^mB_{ik}B_{jk}$$

可以发现：

  • $i=j$ 时， $BB_{ij}^T=v_i的度数$
  • $i\neq j$ 时
    • 如果存在 $e(v_i,v_j)$ ，那么 $BB_{ij}^T=-1$
      • 否则 $BB_{ij}^T=0$

$BB_{ij}^T$ 即为图的 Kirchhoff 矩阵

对于无向图 $G$ ，它的 Kirchhoff 矩阵 $C$ 定义为它的度数矩阵 $D$ 减去他的邻接矩阵 $A$ 。
###Matrix-Tree 定理
####本体
对于一个无向图 $G$ ，他的生成树个数等于其 $Kirchhoff$ 矩阵任何一个 $n-1$ 阶主子式的行列式的绝对值。

$n-1$ 阶主子式：任取一个 $r$ ，将 $C$ 的第 $r$ 行和第 $r$ 列同时删去后的新矩阵，用 $C_r$ 表示。

####证明
以后再说……

##应用
###[bzoj1002]轮状病毒[FJOI2007]
Time Limit: 1 Sec Memory Limit: 162 MB

题目描述

轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个 N 轮状基由圆环上 N 个不同的基原子和圆心处一个核原子构成的， 2 个原子之间的边表示这 2 个原子之间的信息通道。如下图所示：
1

N 轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有 16 个不同的 3 轮状病毒，如下图所示
2

现给定 N( $N\leq100$ )，编程计算有多少个不同的 N 轮状病毒

输入格式

第一行有 1 个正整数 N

输出格式

计算出的不同的 N 轮状病毒数输出

样例输入

3

样例输出

16

这道题是一道很明显地在考察 Matrix-Tree 定理，但是我们不能直接用程序计算，这样会超时，我们可以应用此定理推出一个递推式：$$f[i]=3\times f[i-1]-f[i-2]+2$$

然后本题并没有让我们取模输出，故要用到高精度。

其实还可以用矩阵快速幂再优化一下递推，不过没加就 AC 了十年前的省选还是简单啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN=105;

int n;

struct BN
{
	int num[105],len;
	BN(){memset(num,0,sizeof(num));len=-1;}
	void adjust()
	{
		for(int i=0;i<=len;i++)
		if(num[i]>9)
		{
			num[i+1]+=num[i]/10;num[i]%=10;
			len=max(len,i+1);
		}
		for(int i=0;i<=len;i++)
		if(num[i]<0)
		{
			num[i-1]-=(-num[i])/10;num[i]=10-((-num[i])%10);
		}
		while(!num[len]) len--;
	}
	BN operator * (int x)const
	{
		BN res=*this;
		for(int i=0;i<=len;i++)	res.num[i]*=x;
		res.adjust();
		return res;
	}
	BN operator + (int x)const
	{
		BN res=*this;
		for(int i=0;i<=len||x;i++) res.num[i]+=x%10,x/=10;
		res.adjust();
		return res;
	}
	BN operator - (BN x)const
	{
		BN res;
		for(int i=0;i<=max(len,x.len);i++) res.num[i]-=x.num[i];
		res.adjust();
		return res;
	}
} f[MAXN];

int main()
{
	int i;
	scanf("%d",&n);
	f[1]=BN()+1;f[2]=BN()+5;
	for(i=3;i<=n;i++)
		f[i]=f[i-1]*3-f[i-2]+2;
	for(i=f[n].len;i>=0;i--) putchar(f[n].num[i]+'0');
	printf("\n");
	return 0;
}