傳送門

為什么世界上會有這么傻的題啊……我佛了

很顯然就是矩陣樹強行縫合莫反

設$f(n)$表示所有邊權$\gcd$為$n$的生成樹權值和，$g(d)$表示所有邊權都是 $d$的倍數的生成樹權值和

$$g(d)=\sum _{d\mid n}f(n)$$

$$f(d)=\sum _{d\mid n}g(n)\mu (\frac{n}{d})$$

做完了

開權值大小個vector，把每條邊壓到邊權的約數的vector中

如果一個vector中邊數小于$n?1$就跳過，否則對每條邊構造$(wx+1)$算矩陣樹得到$g$，然后無腦算出$f$統計答案就好了

顯然矩陣樹次數不會超過$O(\frac{md(V)}{n})=O(nd(V))$，總復雜度$O(n^{4}d(v))$

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <vector> using namespace std; struct edge{int u,v,w;}; typedef long long ll; const int MOD=998244353,N=152501; inline int qpow(int a,int p) {int ans=1;while (p){if (p&1) ans=(ll)ans*a%MOD;a=(ll)a*a%MOD;p>>=1;}return ans; } #define inv(x) qpow(x,MOD-2) int np[N+5],pl[N+5],mu[N+5],cnt; inline void init() {np[1]=mu[1]=1;for (int i=2;i<=N;i++){if (!np[i]) mu[pl[++cnt]=i]=-1;for (int j=1,x;(x=i*pl[j])<=N;j++){np[x]=1;if (i%pl[j]==0) break;mu[x]=(MOD-mu[i])%MOD;}} } inline int add(const int& x,const int& y){return x+y>=MOD? x+y-MOD:x+y;} inline int dec(const int& x,const int& y){return x<y? x-y+MOD:x-y;} struct poly{int x,y;poly(const int& x=0,const int& y=0):x(x),y(y){}}; inline poly operator +(const poly& a,const poly& b){return poly(add(a.x,b.x),add(a.y,b.y));} inline poly operator -(const poly& a,const poly& b){return poly(dec(a.x,b.x),dec(a.y,b.y));} inline poly operator *(const poly& a,const poly& b){return poly(((ll)a.x*b.y+(ll)a.y*b.x)%MOD,(ll)a.y*b.y%MOD);} inline poly operator /(const poly& a,const poly& b){ll t=inv(b.y);return poly(dec((ll)a.x*b.y%MOD,(ll)a.y*b.x%MOD)*t%MOD*t%MOD,a.y*t%MOD);} int n,mx; poly g[35][35]; inline int det() {poly ans(0,1);for (int i=1;i<n;i++){ans=ans*g[i][i];for (int j=i+1;j<n;j++){poly t=g[j][i]/g[i][i];for (int k=i;k<n;k++)g[j][k]=g[j][k]-g[i][k]*t;} }return ans.x; } vector<edge> lis[N+5]; int F[N+5],G[N+5]; int main() {init();int m;scanf("%d%d",&n,&m);for (int i=1;i<=m;i++){edge e;scanf("%d%d%d",&e.u,&e.v,&e.w);mx=max(mx,e.w);for (int i=1;i*i<=e.w;i++)if (e.w%i==0){lis[i].push_back(e);if (i*i<e.w) lis[e.w/i].push_back(e);}}for (int k=1;k<=mx;k++){if ((int)lis[k].size()<n-1) continue;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)g[i][j]=poly(0,0);for (vector<edge>::iterator it=lis[k].begin();it!=lis[k].end();++it){poly t(it->w,1);int u=it->u,v=it->v;g[u][u]=g[u][u]+t,g[v][v]=g[v][v]+t;g[u][v]=g[u][v]-t,g[v][u]=g[v][u]-t; } G[k]=det();}for (int d=1;d<=mx;d++)for (int i=1;i*d<=mx;i++)F[d]=(F[d]+(ll)G[i*d]*mu[i])%MOD;int ans=0;for (int i=1;i<=mx;i++) ans=(ans+(ll)i*F[i])%MOD;printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的【省选2020A卷】作业题【矩阵树】【扩域】【莫比乌斯反演】的全部內容，希望文章能夠幫你解決所遇到的問題。

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