网站建设完成后 下一步做什么,南昌手机网站制作,培训网站大全,建湖网站建设problem
luogu-P6624
小 W 刚刚在离散数学课学习了生成树的知识#xff1a;一个无向图 G(V,E)G(V,E)G(V,E) 的生成树 TTT 为边集 EEE 的一个大小为 ∣V∣−1|V|-1∣V∣−1 的子集#xff0c;且保证 TTT 的生成子图在 GGG 中连通。
小 W 在做今天的作业时被这样一道题目难住…problem
luogu-P6624
小 W 刚刚在离散数学课学习了生成树的知识一个无向图 G(V,E)G(V,E)G(V,E) 的生成树 TTT 为边集 EEE 的一个大小为 ∣V∣−1|V|-1∣V∣−1 的子集且保证 TTT 的生成子图在 GGG 中连通。
小 W 在做今天的作业时被这样一道题目难住了
给定一个 nnn 个顶点 mmm 条边点和边都从 111 开始编号的无向图 GGG保证图中无重边和无自环。每一条边有一个正整数边权 wiw_iwi对于一棵 GGG 的生成树 TTT定义 TTT 的价值为TTT 所包含的边的边权的最大公约数乘以边权之和。
即val(T)(∑i1n−1wei)×gcd(we1,we2,…,wen−1)val(T)\left(\sum\limits_{i1}^{n-1} w_{e_i}\right) \times \gcd(w_{e_1},w_{e_2},\dots,w_{e_{n-1}})val(T)(i1∑n−1wei)×gcd(we1,we2,…,wen−1)。
其中 e1,e2,…,en−1e_1,e_2,\dots,e_{n-1}e1,e2,…,en−1 为 TTT 包含的边的编号。
小 W 需要求出 GGG 的所有生成树 TTT 的价值之和他做了很久也没做出来请你帮帮他。
由于答案可能很大你只需要给出答案对 998244353 取模后的结果。
solution
众所周知∑d∣nφ(d)n\sum_{d\mid n}\varphi(d)n∑d∣nφ(d)n ∑T∑i1n−1wei×gcd(we1,we2,...,wen−1)\sum_T\sum_{i1}^{n-1}w_{e_i}\times \gcd(w_{e_1},w_{e_2},...,w_{e_{n-1}}) T∑i1∑n−1wei×gcd(we1,we2,...,wen−1)
∑i1n−1wei×∑d∣we1∧⋯∧d∣wen−1φ(d)\sum_{i1}^{n-1}w_{e_i}\times \sum_{d\mid w_{e_1}\wedge\dots\wedge d\mid w_{e_{n-1}}}\varphi(d) i1∑n−1wei×d∣we1∧⋯∧d∣wen−1∑φ(d)
∑d1max{wi}d∑T∧d∣we1⋯∧d∣wen−1∑i1n−1wei\sum_{d1}^{\max\{w_i\}}d\sum_{T\wedge d\mid w_{e_1}\dots\wedge d\mid w_{e_{n-1}}}\sum_{i1}^{n-1}w_{e_i} d1∑max{wi}dT∧d∣we1⋯∧d∣wen−1∑i1∑n−1wei
外层枚举 ddd内层则是求所有生成树的边权和。
矩阵树定理 若为无向图求生成树个数。 a(i,j)−m(i,j)a(i,j)-m(i,j)a(i,j)−m(i,j)其中 m(i,j):i,jm(i,j):i,jm(i,j):i,j 之间有多少边a(i,i)ia(i,i)ia(i,i)i 的度数。 随意去除矩阵 aaa 的某一行某一列习惯上是去掉最后一行最后一列后生成树个数即为新矩阵的行列式。 若为有向图给定根求外向生成树出度为 111个数。 a(i,j)−m(i,j)a(i,j)-m(i,j)a(i,j)−m(i,j)其中 m(i,j):i,jm(i,j):i,jm(i,j):i,j 之间有多少边a(i,i)ia(i,i)ia(i,i)i 的入度度数。 去掉根所在的行和列后的矩阵行列式即为答案。 若为有向图给定根求内向生成树入度为 111个数。 a(i,j)−m(i,j)a(i,j)-m(i,j)a(i,j)−m(i,j)其中 m(i,j):i,jm(i,j):i,jm(i,j):i,j 之间有多少边a(i,i)ia(i,i)ia(i,i)i 的出度度数。 去掉根所在的行和列后的矩阵行列式即为答案。
事实上矩阵树定理求出的行列式可以是所有生成树边权积的和求生成树个数只是钦定所有 wei1w_{e_i}1wei1 罢了。
但这里是让求所有生成树边权和的和。
所以我们可以构造生成函数 (1wix)(1w_ix)(1wix) 表示第 iii 条边的边权。
然后求行列式这样一次项的系数即为答案。
对于 (abx)(abx)(abx) 四则运算
加减法照样相应位加减。乘法 (abx)(cdx)ac(dcad)x(abx)(cdx)ac(dcad)x(abx)(cdx)ac(dcad)x 二次项直接抛掉即可。除法 abxcdxacbc−adc2x\frac{abx}{cdx}\frac{a}{c}\frac{bc-ad}{c^2}xcdxabxcac2bc−adx同理直接抛掉二次项。
code
#include bits/stdc.h
using namespace std;
#define int long long
#define mod 998244353
#define Pair pair int, int
#define maxn 500
#define maxv 153000
int n, m, cnt;
int phi[maxv], vis[maxv], prime[maxv];
int u[maxn], v[maxn], w[maxn], g[maxv];
Pair a[maxn][maxn];int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}Pair operator ( Pair x, Pair y ) {return make_pair( (x.first y.first) % mod, (x.second y.second) % mod );
}
Pair operator - ( Pair x, Pair y ) {return make_pair( (x.first - y.first) % mod, (x.second - y.second) % mod );
}
Pair operator * ( Pair x, Pair y ) {return make_pair( x.first * y.first % mod, (x.first * y.second x.second * y.first) % mod );
}
Pair operator / ( Pair x, Pair y ) {int inv qkpow( y.first, mod - 2 );return make_pair( x.first * inv % mod, (x.second * y.first - x.first * y.second) % mod * inv % mod * inv % mod );
}void divide( int x ) {for( int i 1;i * i x;i )if( x % i 0 ) { g[i];if( i * i ! x ) g[x / i];}
}void sieve( int n ) {phi[1] 1;for( int i 2;i n;i ) {if( ! vis[i] ) phi[i] i - 1, prime[ cnt] i;for( int j 1;j cnt and i * prime[j] n;j ) {vis[i * prime[j]] 1;if( i % prime[j] 0 ) {phi[i * prime[j]] phi[i] * prime[j];break;}elsephi[i * prime[j]] phi[i] * phi[prime[j]];}}
}int Guass( int n ) {Pair ans make_pair( 1, 0 );int tag 0;for( int i 1;i n;i ) {if( ! a[i][i].first ) {for( int j i 1;j n;j )if( a[j][i].first ) {tag ^ 1;swap( a[i], a[j] );break;}}for( int j i 1;j n;j ) {Pair o a[j][i] / a[i][i];for( int k i;k n;k )a[j][k] a[j][k] - o * a[i][k];}ans ans * a[i][i];}ans tag ? make_pair( 0, 0 ) - ans : ans;return ans.second;
}int solve( int x ) {memset( a, 0, sizeof( a ) );for( int i 1;i m;i )if( w[i] % x 0 ) {a[u[i]][u[i]] a[u[i]][u[i]] make_pair( 1, w[i] );a[v[i]][v[i]] a[v[i]][v[i]] make_pair( 1, w[i] );a[u[i]][v[i]] a[u[i]][v[i]] - make_pair( 1, w[i] );a[v[i]][u[i]] a[v[i]][u[i]] - make_pair( 1, w[i] );}return Guass( n - 1 );
}signed main() {scanf( %lld %lld, n, m );int Max 0;for( int i 1;i m;i ) {scanf( %lld %lld %lld, u[i], v[i], w[i] );divide( w[i] );Max max( Max, w[i] );}sieve( Max );int ans 0;for( int i 1;i Max;i )if( g[i] n - 1 ) (ans solve( i ) * phi[i]) % mod;printf( %lld\n, (ans mod) % mod );return 0;
}
