OI - 作业题「十二省联考2020」

口胡Matrix-Tree定理就是香啊~ (。・∀・)ノ

---

# 题面

> 洛谷P6624

点击展开/折叠题面

给定一个 n 个顶点 m 条边（点和边都从 1 开始编号）的无向图 G，保证图中无重边和无自环。每一条边有一个正整数边权 $w_i$​，对于一棵 G 的生成树 T，定义 T 的价值为：T 所包含的边的边权的最大公约数乘以边权之和，即：

$$val(T)=\left(\sum\limits_{i=1}^{n-1} w_{e_i}\right) \times \gcd(w_{e_1},w_{e_2},\dots,w_{e_{n-1}})$$

其中 $e_1,e_2,\dots,e_{n-1}$ 为 T 包含的边的编号。

求 G 的所有生成树 T 的价值之和对 998244353 取模后的结果。

---

# 解析

补了一下莫比乌斯反演，又新学了 Matrix-Tree 定理，这道题就会做了……

碰到 GCD，又要求和，往莫比乌斯反演这方面想，就会想到一个结论（你也可以把它当作 $\varphi(n)$ 的性质，不过实际上是通过莫比乌斯反演得到的）：

$$\sum_{d|n}\varphi(d)=n$$

这个式子就经常被拿来拆 GCD，比如这道题：

$$\operatorname{val}(T)=\left(\sum_{e_i\in T}w_{e_i}\right)\times\sum_{d\mid\gcd}\varphi(d)$$

然后我们就要求（$d|T$ 表示 d 整除 T 中每一条边的边权）：

$$\begin{aligned} \sum_{T}\operatorname{val}(T)&=\sum_{T}\left(\sum_{e_i\in T}w_{e_i}\right)\times\sum_{d\mid\gcd}\varphi(d)\\ &=\sum_{d=1}^{\max w_i}\varphi(d)\sum_{d|T}\sum_{e_i\in T}w_{e_i} \end{aligned}$$

然后 $\varphi(d)$ 和后面那一坨些求和式就分开了，考虑求和式的意义：取所有权被 d 整除的边构成生成子图 $G_d$，求 $G_d$ 所有生成树的权值和，生成树的权值定义为生成树上所有边的边权和。

求无向图所有生成树的边权和问题也是一个比较经典的 trick~

如果考虑暴力计算，即枚举图上的一条边 $i$，计算有多少个生成树有这条边，记为 $n_i$，则它对答案的贡献为 $w_in_i$；所有边都算一遍就可以了。

但是这样太慢了——能不能一遍算出 $\sum w_in_i$？我们发现可以把生成函数的思想运用到 Matrix-Tree 的矩阵上，把一条边的贡献写成多项式 $(1+w_ix)$。则 Matrix-Tree 的基尔霍夫矩阵可以形式化地表示为（记 $E_i$ 为与点 i 相连的边集）：

$$M_{i,j}=\begin{cases}\sum\limits_{e\in E_i}(1+w_ex)&i=j\\-\sum\limits_{e\in E_i\cap E_j}(1+w_ex)&i\neq j\end{cases}$$

多项式的加减乘除均是在模 $x^2$ 意义下进行（这意味着你需要手推一下模 $x^2$ 意义下多项式的逆元），这样求得的行列式的值也是一个多项式，该多项式的一次项系数就是 $\sum w_in_i$。

为什么？因为是一次项，在所有多项式中只有一个多项式取了 $w_ix$ 这一项，其余都是取的常数项，若只看这些常数项的乘积，便是 $n_i$，再乘上 $w_ix$，就是 $n_iw_ix$（意会一下）。

于是可以先枚举 d，然后把被 d 整除的边建生成子图 $G_d$，求生成子图的所有生成树的权值和即可。但是这样复杂度是 $O(n^3\max w_i)$ 的，看起来好像卡不过去。

但是我们注意到能让 $G_d$ 的边数大于等于 $(n-1)$（有生成树的必要条件）的 d 很少，于是先看 $G_d$ 的边数，若有 $(n-1)$，再做 Matrix-Tree。

洛谷上开O2跑到榜3了（至少现在是） awa

---

# 源代码

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef pair<int,int> pii;
const int N=33,M=N*N,V=153000,MOD=998244353;

#define fir first
#define sec second
#define cs const int &
inline int Add(cs a,cs b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(cs a,cs b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(cs a,cs b){return 1ll*a*b%MOD;}
inline int Pow(int a,int b){int r=1;while(b){if(b&1)r=Mul(a,r);a=Mul(a,a),b>>=1;}return r;}
inline int Div(cs a,cs b){return Mul(a,Pow(b,MOD-2));}

pii operator +(const pii &A,const pii &B){return make_pair(Add(A.fir,B.fir),Add(A.sec,B.sec));}
pii operator -(const pii &A,const pii &B){return make_pair(Sub(A.fir,B.fir),Sub(A.sec,B.sec));}
pii operator *(const pii &A,const pii &B){return make_pair(Mul(A.fir,B.fir),Add(Mul(A.fir,B.sec),Mul(B.fir,A.sec)));}
bool operator ~(const pii &A){return A.fir!=0 || A.sec!=0;}
pii operator -(const pii &A){return make_pair(Sub(0,A.fir),Sub(0,A.sec));}
pii operator *(const pii &A,const int &B){return make_pair(Mul(A.fir,B),Mul(A.sec,B));}
pii Inv(const pii &A){return make_pair(Pow(A.fir,MOD-2),Sub(0,Div(A.sec,Mul(A.fir,A.fir))));}

int n,m;
int edg[M][3],cnt[V],phi[V],prn[V];
bool vis[V];
pii E[N][N];

int Det(int siz){
	pii ret(1,0);
	for(int i=1;i<siz;i++){
		int it=-1,better=-1;
		for(int j=i;j<siz;j++)
			if(~E[j][i]){
				if(E[j][i].fir) better=j;
				it=j;
				break;
			}
		if(~better) it=better;
		if(it==-1) return 0;
		if(i!=it){
			ret=-ret;
			for(int j=i;j<siz;j++) swap(E[i][j],E[it][j]);
		}
		ret=ret*E[i][i];
		if(E[i][i].fir){
			pii dv=Inv(E[i][i]);
			for(int j=i;j<siz;j++) E[i][j]=E[i][j]*dv;
			for(int j=i+1;j<siz;j++)
				if(~E[j][i]){
					pii mul=E[j][i];
					for(int k=i;k<siz;k++) E[j][k]=E[j][k]-E[i][k]*mul;
				}
		}
		else{
			int dv=Pow(E[i][i].sec,MOD-2);
			for(int j=i;j<siz;j++) E[i][j].sec=Mul(E[i][j].sec,dv);
			for(int j=i+1;j<siz;j++)
				if(~E[j][i]){
					int mul=E[j][i].sec;
					for(int k=i;k<siz;k++) E[j][k]=E[j][k]-E[i][k]*mul;
				}
		}
	}
	return ret.sec;
}
void Prepare(){
	int nprn=0;
	phi[1]=1;
	for(int i=2;i<V;i++){
		if(!vis[i]) prn[++nprn]=i,phi[i]=i-1;
		for(int j=1;j<=nprn && prn[j]*i<V;j++){
			vis[i*prn[j]]=true;
			if(i%prn[j]) phi[i*prn[j]]=Mul(phi[i],phi[prn[j]]);
			else{
				phi[i*prn[j]]=Mul(phi[i],prn[j]);
				break;
			}
		}
	}
}
inline int Ri(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
	return r;
}
int main(){
	Prepare();
	n=Ri(),m=Ri();
	for(int i=1;i<=m;i++){
		edg[i][0]=Ri(),edg[i][1]=Ri(),edg[i][2]=Ri();
		for(int j=1;j*j<=edg[i][2];j++)
			if(edg[i][2]%j==0){
				cnt[j]++;
				if(edg[i][2]!=j*j) cnt[edg[i][2]/j]++;
			}
	}
	int ans=0;
	for(int d=1;d<=V;d++){
		if(cnt[d]<n-1) continue;
		for(int i=1;i<=m;i++){
			if(edg[i][2]%d) continue;
			pii thi(1,edg[i][2]);
			int u=edg[i][0],v=edg[i][1];
			E[u][u]=E[u][u]+thi,E[v][v]=E[v][v]+thi;
			E[u][v]=E[u][v]-thi,E[v][u]=E[v][u]-thi;
		}
		int res=Det(n);
		// printf("%d %d\n",d,res);
		ans=Add(ans,Mul(phi[d],res));
		memset(E,0,sizeof E);
	}
	printf("%d\n",ans);
	return 0;
}

---

THE END

Thanks for reading!

$$\begin{split} “\ &凉薄如水的月光\\ &能映出什么吗\\ &但仍向你祈求着啊\\ &若是你\ 灰烬般飘洒\\ &在破晓的刹那\\ &你会因我而歌唱吗\ ”\\ ——&\text{《灼之花》By 洛天依/乐正绫/COP} \end{split}$$

> Linked 灼之花-网易云