P6624 [省选联考 2020 a 卷] 作业题

,

Solution

感觉这个要求的形式很矩阵树，考虑矩阵树定理。

答案是加和的形式，不能直接矩阵树。考虑求对于每条边的贡献。

令当前枚举的边的编号为 $i$ 。枚举 $w_i$ 的因数 $d$ ，钦定所有边权的 $\gcd$ 的值必须是 $d$ 的倍数。用两遍矩阵树定理算加上和不加上这条边产生的生成树的个数，之差即为这条边的贡献。不妨设 $g_d$ 表示所有边权的 $\gcd$ 的值必须是 $d$ 的倍数的这条边的贡献。同样的，设 $f_d$ 为所有边权的 $\gcd$ 的值为 $d$ ** 的个数。注意到 $g$ 和 $f$ 都是对于枚举的这条边 $i$ 来说的。**

现在有关系
$$
g_i=\sum_{i|d} f_d
$$
要求的即为
$$
ans=\sum_{i=1}^n f_i\times i
$$
考虑反演：
$$
f_i=\sum_{d|i} \mu(\dfrac{d}{i})g_d
$$
其实好像可以直接算，但是为了回忆一下反演。考虑继续化简：
$$
ans=\sum\limits_{i=1}^nf_i\times i=\sum_{i=1}^ni\sum_{d|i} \mu(\dfrac{d}{i})g_d
$$

$$
=\sum_{d=1}^ng_d\sum_{d|i}i\mu(\dfrac{d}{i})=\sum_{d=1}^n\varphi(d) g_d
$$

每次处理出每条边的 $g$，即可。

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
94
95
96
97
98
99
100
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 35
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int a[maxn][maxn],n,m;
struct node{
	int x,y,z,id;
}e[maxn*maxn],h[maxn*maxn];
int g[100005],ans,rt[100005];
const int mod=998244353;
inline int power(int x,int y) {
	int ans=1;
	while (y) {
		if (y&1) ans=ans*x%mod;
		x=x*x%mod;y>>=1;
	}
	return ans;
}
inline int calc(int n) {
	int i,j,k,sum=1;
	for (i=1;i<=n;i++) {
		int inv=power(a[i][i],mod-2); 
		if (!a[i][i]) {
			for (j=i+1;j<=n;j++) if (a[j][i]) {
				swap(a[i],a[j]);sum*=-1;break;
			}
		}
		for (j=i+1;j<=n;j++) {
			int tmp=a[j][i]*inv%mod;
			for (k=i;k<=n;k++) {
				a[j][k]=(a[j][k]-a[i][k]*tmp%mod+mod)%mod;
			}
		}
	}
	sum=(sum+mod)%mod;
	for (i=1;i<=n;i++) sum=sum*a[i][i]%mod;
	return sum;
}
int prime[200005],cnt,fi[200005],vis[200005],f[200005];
inline void getprime(int n) {
	vis[1]=1;fi[1]=1;int i,j;
	for (i=2;i<=n;i++) {
		if (!vis[i]) prime[++cnt]=i,fi[i]=i-1;
		for (j=1;j<=cnt&&prime[j]*i<=n;j++) {
			vis[prime[j]*i]=1,fi[prime[j]*i]=fi[i]*(prime[j]-1);
			if (i%prime[j]==0) {fi[i*prime[j]]=fi[i]*prime[j];break;}
		}
	}
}
signed main(void){
	int i,j,tot,k,l;
	read(n);read(m);
	for (i=1;i<=m;i++) {
		read(e[i].x),read(e[i].y),read(e[i].z);e[i].id=i;
	}
	getprime(200000);
	for (l=1;l<=m;l++) {
		tot=0;
		for (j=1;j*j<=e[l].z;j++) if (e[l].z%j==0) {rt[++tot]=j,rt[++tot]=e[l].z/j;}
		sort(rt+1,rt+1+tot);tot=unique(rt+1,rt+1+tot)-rt-1;
		
		for (i=tot;i>=1;i--) {
			tot=0;
			for (j=1;j<=m;j++) if (e[j].z%rt[i]==0) h[++tot]=e[j];
			if (tot<n-1) continue; //显然只选边数>=n-1的跑，否则没有贡献
			memset(a,0,sizeof(a));
			for (j=1;j<=tot;j++) a[h[j].x][h[j].y]-=1,a[h[j].y][h[j].x]-=1,a[h[j].x][h[j].x]+=1,a[h[j].y][h[j].y]+=1;
			for (k=1;k<=n;k++) for (j=1;j<=n;j++) a[k][j]=(a[k][j]%mod+mod)%mod;
			int sum1=calc(n-1);
			
			memset(a,0,sizeof(a));
			for (j=1;j<=tot;j++) a[h[j].x][h[j].y]-=1,a[h[j].y][h[j].x]-=1,a[h[j].x][h[j].x]+=1,a[h[j].y][h[j].y]+=1;
			a[e[l].x][e[l].y]+=1,a[e[l].y][e[l].x]+=1,a[e[l].x][e[l].x]-=1,a[e[l].y][e[l].y]-=1;
			for (k=1;k<=n;k++) for (j=1;j<=n;j++) a[k][j]=(a[k][j]%mod+mod)%mod;
			int sum2=calc(n-1);
//			gdb(e[l].x,e[l].y,e[l].z,fi[i],rt[i],sum1,sum2);
			ans=(ans+(sum1-sum2)*fi[rt[i]]%mod*e[l].z%mod+mod)%mod;
		}
//		for (i=1;i<=tot;i++) f[rt[i]]=0;
	}
	printf("%lld",ans);
	return 0;
}

复杂度 $O(n^2\sum \sigma_o(w_i))$

实际跑不满。