线性代数 删边计数

发表于
字数统计: 996字 | 阅读时长 ≈ 5min

线性代数 删边计数

问题描述

给你一个由n个点m条边构成的无向图。要你从图中删除m-n条边，使得剩下的图示连通的。
问总共有多少种删边方案？

输入格式

第一行，两个整数n,m
接下来m行，每行两个整数x和y,表示点x与点y之间有边相连。
图中没有自环，也没有重边。

输出格式

输出一个整数，表示答案，答案可能很大，mod 998244353再输出。

数据范围

$1\leq n\leq 16,n\leq m\leq \frac{n(n-1)}{2}$

首先意识到最后的图一定是一个基环树，如果把环缩成一个点就可以套用矩阵树定理计数了。自然的想法就是枚举这个环。需要注意双连通分量的算法是行不通的——并没有找出所有环；仅枚举成环的点集也是不行的——不同形态的环是不同的，不能简单用集合计数。

因此考虑这样设计状压DP：设$f[s][p]$是以$p$为终点，以集合$s$中编号最小的点（即二进制状态的lowbit）作为起点，经过集合$s$中所有点恰一次的简单路径条数。这样做的话转移比较显然，而且保证了每个环仅被计算两次——枚举环时判断简单路径两端是否有边相连，那么一个环会在与起点相邻的两个点作为终点时被算到。所以最后不要忘了把答案乘上2的逆元。

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;
const ll mod=998244353;

void add(int &a,int b){a+=b;a-=a<mod?0:mod;}
void sub(int &a,int b){a-=b;a+=a<0?mod:0;}
void mul(int &a,int b){a=(ll)a*b%mod;}

int N,M,U,Map[20][20],f[66666][20],A[200],B[200],Ans;
int n,R,C,Mat[20][20],id[20];

int ksm(int a,int b){
	int ans=1;
	while(b){
		if(b&1)mul(ans,a);
		mul(a,a);b>>=1;
	}
	return ans;
}

int Gauss(){
	int x,y,i,j,id,sign=0,ret=1,t,inv;
	for(x=y=1;x<=n&&y<=n;x++,y++){
		for(i=x,id=-1;i<=n;i++)if(Mat[i][y]){id=i;break;}
		if(id==-1)return 0;
		if(id!=x){
			sign^=1;
			for(i=y;i<=n;i++)swap(Mat[x][i],Mat[id][i]);
		}
		inv=ksm(Mat[x][y],mod-2);
		for(i=x+1;i<=n;i++){
			t=inv;mul(t,Mat[i][y]);
			for(j=y;j<=n;j++)sub(Mat[i][j],(ll)Mat[x][j]*t%mod);
		}
	}
	for(i=1;i<=n;i++)mul(ret,Mat[i][i]);
	if(sign)ret=mod-ret;
	return ret;
}

int solve(int st){
	int i,j,k,x,y;
	for(i=k=1;i<=N;i++){
		if(st>>i-1&1)id[i]=1;
		else id[i]=++k;
	}
	n=k-1;
	memset(Mat,0,sizeof(Mat));
	for(i=1;i<=M;i++){
		x=id[A[i]];y=id[B[i]];
		if(x==y)continue;
		Mat[x][x]++;Mat[y][y]++;
		Mat[x][y]--;Mat[y][x]--;
	}
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)Mat[i][j]=(Mat[i][j]%mod+mod)%mod;
	return Gauss();
}

int main(){
	int i,j,k,t,x,y;
	scanf("%d%d",&N,&M);
	for(i=1;i<=M;i++){
		scanf("%d%d",&x,&y);
		Map[x][y]=Map[y][x]=1;
		A[i]=x;B[i]=y;
	}
	U=(1<<N)-1;
	for(i=1;i<=N;i++)f[1<<i-1][i]=1;
	for(i=1;i<=U;i++)
	for(j=1;j<=N;j++)if(f[i][j]&&(i>>j-1&1)){
		t=i&-i;
		for(k=1;(1<<k-1)<=t;k++);
		for(;k<=N;k++)if((!(i>>k-1&1))&&Map[j][k])add(f[i|(1<<k-1)][k],f[i][j]);
	}
	for(i=1;i<=U;i++){
		for(j=i,k=0;j;j^=j&-j,k++);
		if(k<3)continue;
		t=i&-i;
		for(j=1;j<=N;j++)if((1<<j-1)==t)break;
		for(k=1;k<=N;k++)if((i>>k-1&1)&&Map[j][k]&&f[i][k]){
			t=(ll)solve(i)*f[i][k]%mod;
			add(Ans,t);
		}
	}
	mul(Ans,(mod+1)/2);
	Ans=(Ans%mod+mod)%mod;
	printf("%d\n",Ans);
}