正題

題目鏈接:https://www.luogu.com.cn/problem/P6624

---

題目大意

$n$個點的一張圖，每條邊有權值，一棵生成樹的權值是所有邊權和乘上邊權的$gcd$，即
$$val(T)=\left(\sum _{i=1}^{n?1}{w}_{e_i}\right)\times \gcd (w_{e_1},w_{e_2},\dots ,w_{e_{n?1}})$$

求所有生成樹的權值和

---

解題思路

首先要知道一個東西$\phi ?I=id$，于是我們就有
$$gcd(w_1,w_2,\dots ,w_n)=\sum _{d|w_1,d|w_2,\dots ,d|w_n}\phi (d)$$
然后化進這個式子里就是
$$\left(\sum _{i=1}^{n?1}{w}_i\right)\times \sum _{d|w_1,d|w_2,\dots ,d|w_n}\phi (d)$$
然后把$\phi (d)$丟出去就是
$$\sum _{d=1}^n\phi (d)\times ?\sum _{i=1,d|w_i}^{n?1}{w}_i?$$
之后就是怎么快速算后面那個東西的事情了。

一個比較樸素的做法是枚舉每一條邊產生的貢獻，然后固定這條邊然后矩陣樹求一次答案乘上這條邊就好了。

但是這個比較慢，我們可以利用生成函數的思想，每一條邊權變為$F_i(x)=w_{i}x+1$的一個多項式，然后所有多項式乘起來之后的一次項系數就是答案了。因為這樣只會選擇一條邊的$w_i$

多項式除法的話用的比較少，這里化一下
$$\frac{ax+b}{cx+d}=zx+w?ax+b=zc{x}^2+(zd+cw)x+wd$$
然后二次項我們直接丟掉就有
$$b=wd?w=\frac{b}{d}$$
帶進后面那個去就有
$$a=zd+c\frac{b}{d}?z=\frac{ad?cb}{d^2}$$
所以
$$\frac{ax+b}{cx+d}=\frac{ad?cb}{d^2}x+\frac{b}{d}$$

這樣時間復雜度是$O(max\{w_i\}(m+n^3))$的，好像過不了，可以把邊數不夠$n?1$的直接不管，這樣可以省去很多無用情況

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=2e5+10,P=998244353; struct fuc{ll x,y;fuc(ll xx=0,ll yy=0){x=xx;y=yy;return;} }; ll power(ll x,ll b){ll ans=1;x%=P;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; }; ll inv(ll x){return power(x,P-2);} fuc operator+(fuc a,fuc b) {return fuc((a.x+b.x)%P,(a.y+b.y)%P);} fuc operator-(fuc a,fuc b) {return fuc((a.x-b.x+P)%P,(a.y-b.y+P)%P);} fuc operator*(fuc a,fuc b) {return fuc((a.x*b.y+a.y*b.x)%P,a.y*b.y%P);} fuc operator/(fuc a,fuc b) {return fuc((a.x*b.y-b.x*a.y+P)%P*inv(b.y*b.y)%P,a.y*inv(b.y)%P);} ll n,m,ans,x[N],y[N],w[N],phi[N],pri[N],cnt; bool v[N];fuc a[31][31]; fuc det(){fuc ans(0,1);ll f=1;for(ll i=1;i<n;i++){ll w=i;for(ll j=i;j<n;j++)if(a[i][j].y){if(i!=j)f=-f;w=j;break;}swap(a[i],a[w]);if(!a[i][i].y)return fuc(0,0);ans=ans*a[i][i];fuc inv=fuc(0,1)/a[i][i];for(ll j=n-1;j>=i;j--)a[i][j]=a[i][j]*inv;for(ll j=i+1;j<n;j++){fuc rate=a[j][i];for(ll k=i;k<n;k++)a[j][k]=a[j][k]-rate*a[i][k];}}return (ans.x*f+P)%P; } void init(ll n){phi[1]=1;for(ll i=2;i<=n;i++){if(!v[i])pri[++cnt]=i,phi[i]=i-1;for(ll j=1;j<=cnt&&i*pri[j]<=n;j++){v[i*pri[j]]=1;if(i%pri[j]==0){phi[i*pri[j]]=phi[i]*pri[j];break;}phi[i*pri[j]]=phi[i]*phi[pri[j]];}}return; } signed main() {scanf("%lld%lld",&n,&m);ll mx=0;for(ll i=1;i<=m;i++){scanf("%lld%lld%lld",&x[i],&y[i],&w[i]);x[i]--;y[i]--;mx=max(mx,w[i]);}init(mx);for(ll i=1;i<=mx;i++){ll cnt=0;for(ll j=1;j<=m;j++)if(w[j]%i==0)cnt++;if(cnt<n-1)continue;memset(a,0,sizeof(a));for(ll j=1;j<=m;j++) if(w[j]%i==0){a[x[j]][x[j]]=a[x[j]][x[j]]+fuc(w[j],1);a[y[j]][y[j]]=a[y[j]][y[j]]+fuc(w[j],1);a[x[j]][y[j]]=a[x[j]][y[j]]-fuc(w[j],1);a[y[j]][x[j]]=a[y[j]][x[j]]-fuc(w[j],1);}(ans+=phi[i]*det().x%P)%=P;}printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的P6624-[省选联考2020A卷]作业题【矩阵树定理,欧拉反演】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。