文章目錄

• 前言
• 解析
• • 無(wú)向圖
  • 有向圖
  • • 根向樹(shù)
    • 葉向樹(shù)
    • code
  • 帶權(quán)圖
  • • code

所謂矩陣樹(shù)定理，就是用矩陣解決樹(shù)問(wèn)題的定理。

（逃）

前言

神奇科技。
之前一直沒(méi)有寫博客，覺(jué)得還是寫一發(fā)比較好。
證明什么的是不可能會(huì)的
背下來(lái)背下來(lái)！

解析

無(wú)向圖

定義一個(gè)矩陣 $A$：
$$\begin{gathered} A_{i,i}=d_i \\ {A}_{i,j}=?\#(i,j)(i=j) \end{gathered}$$
其中 $\#(i,j)$ 表示這條邊的數(shù)量。
求出這個(gè)矩陣的任意一個(gè)余子式即可。

有向圖

根向樹(shù)

定義一個(gè)矩陣 $A$：
$$\begin{gathered} A_{i,i}=d_i^{+} \\ {A}_{i,j}=?\#(i,j)(i=j) \end{gathered}$$
去掉第 $i$ 行得到的余子式就是以 $i$ 為根的答案。

葉向樹(shù)

定義一個(gè)矩陣 $A$：
$$\begin{gathered} A_{i,i}=d_i^{?} \\ {A}_{i,j}=?\#(i,j)(i=j) \end{gathered}$$
唯一的區(qū)別就是主對(duì)角線從出度變成了入度（為什么呢？因?yàn)楦乃枷胩惻f，已經(jīng)out了）

code

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") using namespace std;const int N=305; const int mod=1e9+7;inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }inline ll ksm(ll x,ll k){ll res(1);while(k){if(k&1) res=res*x%mod;x=x*x%mod;k>>=1;}return res; }int n,m; ll a[N][N]; ll calc(int n){ll ans(1);for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){if(a[j][i]){if(j!=i) swap(a[i],a[j]);break;}}for(int j=i+1;j<=n;j++){ll d=a[j][i]*ksm(a[i][i],mod-2)%mod;for(int k=i;k<=n;k++) a[j][k]=(a[j][k]+mod-a[i][k]*d%mod)%mod;}}for(int i=1;i<=n;i++) ans=ans*a[i][i]%mod;return ans; } void work0(){for(int i=1;i<=m;i++){int x=read(),y=read(),w=read();if(x==y) continue;(a[x][x]+=w)%=mod;(a[y][y]+=w)%=mod;(a[x][y]+=mod-w)%=mod;(a[y][x]+=mod-w)%=mod;}printf("%lld\n",calc(n-1)); } void work1(){for(int i=1;i<=m;i++){int x=read(),y=read(),w=read();if(x==y) continue;(a[y][y]+=w)%=mod;(a[x][y]+=mod-w)%=mod;}for(int i=1;i<n;i++){for(int j=1;j<n;j++) a[i][j]=a[i+1][j+1];}printf("%lld\n",calc(n-1)); }signed main(){ #ifndef ONLINE_JUDGE // freopen("a.in","r",stdin); // freopen("a.out","w",stdout); #endifn=read();m=read();int op=read();if(op==0) work0();else work1();return 0; } /* 3 2 1 1 1 1 */

帶權(quán)圖

如果一棵生成樹(shù)的權(quán)值定義為邊權(quán)乘積，直接把邊理解成邊權(quán)條1權(quán)邊在對(duì)應(yīng)的位置加邊權(quán)即可。

如果一棵生成樹(shù)的權(quán)值定義為邊權(quán)加和，需要在矩陣內(nèi)維護(hù)一個(gè)一次函數(shù)，最終在 $\mathrm{m}\mathrm{o}\mathrm{d}{x}^2$ 意義下求出的行列式的一次項(xiàng)就是答案。
因?yàn)檫@就相當(dāng)于單獨(dú)考慮一條邊的邊權(quán)，看它能加入多少棵生成樹(shù)中。

code

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") using namespace std;const int N=35; const int M=1050; const int S=2e5+100; const int inf=1e9; const int mod=998244353;inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }inline ll ksm(ll x,ll k){ll res(1);while(k){if(k&1) res=res*x%mod;x=x*x%mod;k>>=1;}return res; }int n,m; int mx; int prime[S],vis[S],tot; ll mu[S]; void init(int n){mu[1]=1;for(int i=2;i<=n;i++){if(!vis[i]){prime[++tot]=i;mu[i]=-1;}for(int j=1;j<=tot&&prime[j]<=n/i;j++){int now=prime[j];vis[i*now]=1;if(i%now==0){mu[i*now]=0;break;}mu[i*now]=-mu[i];}}for(int i=1;i<=n;i++) mu[i]=(mu[i]+mod)%mod;return; }struct node{ll a,b; }; node operator + (const node x,const node y){return (node){(x.a+y.a)%mod,(x.b+y.b)%mod};} node operator - (const node x,const node y){return (node){(x.a+mod-y.a)%mod,(x.b+mod-y.b)%mod};} node operator * (const node x,const node y){return (node){(x.a*y.b+x.b*y.a)%mod,x.b*y.b%mod};} node operator / (const node x,const node y){ll niv=ksm(y.b,mod-2);return (node){(x.a*y.b-x.b*y.a%mod+mod)%mod*niv%mod*niv%mod,x.b*niv%mod}; } void operator += (node &x,const node y){x=x+y;} void operator -= (node &x,const node y){x=x-y;} void operator *= (node &x,const node y){x=x*y;} void operator /= (node &x,const node y){x=x/y;}int u[M],v[M],w[M]; node a[N][N]; ll g[S],f[S]; void print(int n){puts("\n------\n");for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) printf("(%lld %lld) ",a[i][j].a,a[i][j].b);puts("");} } ll calc(int n){node ans=(node){0,1};for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){node d=a[j][i]/a[i][i];for(int k=i;k<=n;k++) a[j][k]-=(a[i][k]*d);}}for(int i=1;i<=n;i++){//printf(" i=%d a=%lld ans=%lld\n",i,a[i][i],ans[i])ans=ans*a[i][i];}return ans.a; } void work(int x){memset(a,0,sizeof(a));int cnt(0);for(int i=1;i<=m;i++){if(w[i]%x) continue;a[u[i]][u[i]]+=(node){w[i],1};a[v[i]][v[i]]+=(node){w[i],1};a[u[i]][v[i]]-=(node){w[i],1};a[v[i]][u[i]]-=(node){w[i],1};cnt++;}if(cnt<n-1) return;//printf("\n---x=%d\n",x);//print(n);g[x]=calc(n-1);//printf("ans=%lld\n",g[x]);return; }signed main() { #ifndef ONLINE_JUDGE // freopen("a.in","r",stdin); // freopen("a.out","w",stdout); #endifn=read();m=read();for(int i=1;i<=m;i++){u[i]=read();v[i]=read();w[i]=read();mx=max(mx,w[i]);}init(mx);for(int x=1;x<=mx;x++) work(x);ll ans(0);for(int i=1;i<=mx;i++){for(int j=1;j*i<=mx;j++) (f[i]+=g[i*j]*mu[j])%=mod;(ans+=i*f[i])%=mod;}printf("%lld\n",ans);return 0; } /* 3 2 1 1 1 1 */

總結(jié)

以上是生活随笔為你收集整理的模板：矩阵树定理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。