[模板]Matrix Tree定理

结论：一个图的生成树个数等于它的度数矩阵减邻接矩阵得到的矩阵（基尔霍夫矩阵）的任意一个n-1阶主子式的行列式的绝对值

证明：不会

求法：高斯消元

例题：[HEOI2013]小Z的房间

#include <iostream>

#include <cstdio>

#include <cstring>

#define int long long

using namespace std;

const int dx[]={0,1,0,-1},dy[]={1,0,-1,0},mod=1e9;

int n,m,mp[10][10],kir[90][90],cnt;

char s[10][10],ch[10];

inline bool ck(int x,int y) {return x&&(x<=n)&&y&&(y<=m)&&mp[x][y];}

inline void add(int x,int y) {if(x>y) return;kir[x][x]++,kir[y][y]++,kir[x][y]--,kir[y][x]--;}

inline int gauss() {

    int ans=1;

    for(int i=1;i<cnt;i++) {

        for(int j=i+1;j<cnt;j++)

            while(kir[j][i]) {

                int p=kir[i][i]/kir[j][i];

                for(int k=i;k<cnt;k++)

                    kir[i][k]=(kir[i][k]-p*kir[j][k]+mod)%mod;

                swap(kir[i],kir[j]);

                ans=-ans;

            }

        ans=(ans*kir[i][i])%mod;

    }

    return (ans+mod)%mod;

}

char c;

signed main() {

    scanf("%lld%lld",&n,&m);

    for(int i=1;i<=n;i++) {

        for(int j=1;j<=m;j++) {

            cin>>c;

            if(c=='.') mp[i][j]=++cnt;

        }

    }

    for(int i=1;i<=n;i++) {

        for(int j=1;j<=m;j++) {

            if(mp[i][j])

            for(int d=0;d<4;d++) {

                const int nx=i+dx[d],ny=j+dy[d];

                if(mp[nx][ny]) add(mp[i][j],mp[nx][ny]);

            }

        }

    }

    /*

    for(int i=1;i<=cnt;i++) {

        for(int j=1;j<=cnt;j++) printf("%d ",kir[i][j]);

        printf("\n");

    }

    */

    cout<<gauss();

}

luogu 3790 文艺数学题

求无向图的所有生成树的权值gcd之和。

枚举所有gcd的值，然后反演一下。luogu的题解写的很清楚。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

const int mod=1000000007;

const int N = 1000005;

int ph[N],prime[N],cnt;

bool vis[N];

void phi() {

    ph[1]=1;

    for(int i=2; i<=N-5; i++) {

        if(!vis[i]) {

            prime[++cnt]=i;

            ph[i]=i-1;

        }

        for(int j=1; j<=cnt; j++) {

            if(i*prime[j]<=N-5) {

                vis[i*prime[j]]=1;

            }

            else break;

            if(i%prime[j]==0){

                ph[i*prime[j]]=ph[i]*prime[j];break;

            }

            else ph[i*prime[j]]=ph[i]*ph[prime[j]];

        }

    }

}

int ksm(int d,int z) {

    int res=1;

    while(z) {

        if(z&1) res=(1ll*res*d)%mod;

        d=(1ll*d*d)%mod;

        z>>=1;

    }

    return res;

}

int top,st[3605],ed[3605],val[3605],kir[65][65],n,m,mx;

int bark[10000005],fa[65];

int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}

inline int gauss() {

    for(int i=0;i<n;i++)for(int j=0;j<n;j++) kir[i][j]=(kir[i][j]+mod)%mod;

    int ans=1,f=1;

    for(int i=1;i<n;i++) {

    	int p=i;

    	for(;!kir[p][i]&&p<n;p++);

    	if(p!=i) f=-f,swap(kir[p],kir[i]);

    	if(!kir[i][i]) return 0;

    	ans=1ll*ans*kir[i][i]%mod;

    	int inv=ksm(kir[i][i],mod-2);

    	for(int j=i+1;j<n;j++) {

    		if(!kir[j][i]) continue;

    		int tp=1ll*kir[j][i]*inv%mod;

    		for(int k=1;k<n;k++) kir[j][k]=(kir[j][k]-1ll*kir[i][k]*tp%mod+mod)%mod;

    	}

    }

    return (ans*f%mod+mod)%mod;

}

int main() {

    phi();

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++) scanf("%d%d%d",&st[i],&ed[i],&val[i]),st[i]--,ed[i]--;

    for(int i=1;i<=m;i++) {

        for(int j=1;j*j<=val[i];j++) {

            if(val[i]%j==0) {

                bark[j]++;

                if(j*j!=val[i]) bark[val[i]/j]++;

            }

        }

    }

    long long ans=0;

    for(int i=1;i<=1000000;i++) {

        if(bark[i]<n-1) continue;

        int cnt=0;

        for(int j=0;j<=n;j++) fa[j]=j;

        memset(kir,0,sizeof kir);

        for(int j=1;j<=m;j++) {

            if(val[j]%i==0) {

                if(find(st[j])!=find(ed[j]))

                cnt++,fa[find(st[j])]=fa[find(ed[j])];

                if(st[j]!=ed[j])

                kir[st[j]][st[j]]++,kir[ed[j]][ed[j]]++,kir[st[j]][ed[j]]--,kir[ed[j]][st[j]]--;

            }

        }

        if(cnt==n-1) ans=(ans+1ll*ph[i]*gauss())%mod;

    }

    printf("%lld",ans);

    return 0;

}

巴特西

[模板]Matrix Tree定理

最新文章

热门文章