矩阵树定理

惊鸿一瞥 .

double版本

这个是oi wiki上的原原本本的代码,我直接照抄了 .

参考资料:
https://oi-wiki.org/math/gauss/
https://oi-wiki.org/graph/matrix-tree/

// https://oi-wiki.org/math/gauss/ 
// https://oi-wiki.org/graph/matrix-tree/ 
// 本篇中的图,无论无向还是有向,都允许重边,但是不允许自环。
// double 版本
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define MOD 100000007
#define eps 1e-7

struct matrix {
  static const int maxn = 20;
  int n, m;
  double mat[maxn][maxn];
  matrix() { memset(mat, 0, sizeof(mat)); }
  void print() {
    cout << "MATRIX " << n << " " << m << endl;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        cout << mat[i][j] << "\t";
      }
      cout << endl;
    }
  }
  void random(int n) {
    this->n = n;
    this->m = n;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) mat[i][j] = rand() % 100;
  }
  void initSquare() {
    this->n = 4;
    this->m = 4;
    memset(mat, 0, sizeof(mat));
    mat[0][1] = mat[0][3] = 1;
    mat[1][0] = mat[1][2] = 1;
    mat[2][1] = mat[2][3] = 1;
    mat[3][0] = mat[3][2] = 1;
    mat[0][0] = mat[1][1] = mat[2][2] = mat[3][3] = -2;
    this->n--;  // 去一行
    this->m--;  // 去一列
  }
  double gauss() {
    double ans = 1;
    for (int i = 0; i < n; i++) {
      int sid = -1;
      for (int j = i; j < n; j++)
        if (abs(mat[j][i]) > eps) {
          sid = j;
          break;
        }
      if (sid == -1) continue;
      if (sid != i) {
        for (int j = 0; j < n; j++) {
          swap(mat[sid][j], mat[i][j]);
          ans = -ans;
        }
      }
      for (int j = i + 1; j < n; j++) {
        double ratio = mat[j][i] / mat[i][i];
        for (int k = 0; k < n; k++) {
          mat[j][k] -= mat[i][k] * ratio;
        }
      }
    }
    for (int i = 0; i < n; i++) ans *= mat[i][i];
    return abs(ans);
  }
};
int main() {
  srand(1);
  matrix T;
  // T.random(2);
  T.initSquare();
  T.print();
  double ans = T.gauss();
  T.print();
  cout << ans << endl;
}

mod版本

题目链接 : https://www.luogu.com.cn/problem/P4111

这一份是根据之前hdu6836通过的代码改编的.

具体的约束条件参考double版本的代码,应该也是本篇中的图,无论无向还是有向,都允许重边,但是不允许自环。

// ac
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

#define LL ll

const int N=110;
const LL mod= 1e9;
const ll MOD=mod;

ll ksm(ll a,ll n){
	ll res=1;
	while(n){
		if(n&1) res=res*a%mod;
		a=a*a%mod;
		n>>=1;
	}
	return res;
}

ll inv(ll a){
	return ksm(a,mod-2);
}



LL K[N][N];

void add(int x,int y){
	K[x][y]--;
	K[y][x]--;
	K[x][x]++;
	K[y][y]++;
}

LL gauss(int n){
	LL res=1;
	for(int i=1;i<=n-1;i++){
		for(int j=i+1;j<=n-1;j++){
			while(K[j][i]){
				int t=K[i][i]/K[j][i];
				for(int k=i;k<=n-1;k++)
					K[i][k]=(K[i][k]-t*K[j][k]+MOD)%MOD;
				swap(K[i],K[j]);
				res=-res;
			}
		}
		res=(res*K[i][i])%MOD;
	}
	return (res+MOD)%MOD;
}


const int maxv=1e3+10;
char pic[maxv][maxv];
int id[maxv][maxv];
int main(){
	int n,m;while(~scanf("%d%d",&n,&m)){
		// 如果tle 可以考虑把memset改成for循环
		// 或者 直接单组数据 :-) 
		memset(K,0,sizeof K);
		memset(id,0,sizeof id);
		inc(i,1,n) scanf("%s",pic[i]+1);
		int pos=0;
		inc(i,1,n) inc(j,1,m) if(pic[i][j]=='.') id[i][j]=++pos;
		inc(i,1,n) inc(j,1,m)  if(pic[i][j]=='.') {
			if(id[i-1][j]) add(id[i][j],id[i-1][j]);
			if(id[i][j-1]) add(id[i][j],id[i][j-1]);
		}
		cout<<gauss(pos)<<"\n";
	}
	return 0;
}

hdu6836

是hdu多校某场的一个题, 和队友商讨确定主体思路后,自己参考网上矩阵树定理模板,编写了代码.

有时间记得在补区域赛题和学习知识点的空余时间补一下之前牛客和多校的题目啊 : - )

// 场上通过的代码
// 之后又提交了一下 
// 33697467	2020-08-07 09:57:15	Accepted	6836	312MS	5180K	1565 B	G++	mainland
//


#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

#define LL ll

const int N=110;
const LL mod= 998244353;
const ll MOD=mod;

ll ksm(ll a,ll n){
	ll res=1;
	while(n){
		if(n&1) res=res*a%mod;
		a=a*a%mod;
		n>>=1;
	}
	return res;
}

ll inv(ll a){
	return ksm(a,mod-2);
}


LL K[40][N][N];
LL gauss(int p,int n){
	LL res=1;
	for(int i=1;i<=n-1;i++){
		for(int j=i+1;j<=n-1;j++){
			while(K[p][j][i]){
				int t=K[p][i][i]/K[p][j][i];
				for(int k=i;k<=n-1;k++)
					K[p][i][k]=(K[p][i][k]-t*K[p][j][k]+MOD)%MOD;
				swap(K[p][i],K[p][j]);
				res=-res;
			}
		}
		res=(res*K[p][i][i])%MOD;
	}
	return (res+MOD)%MOD;
}
int main(){
	int T,n,m;
	scanf("%d",&T);
	while(T--){
		memset(K,0,sizeof K);
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++){
			int x,y;
			ll w;
			scanf("%d%d",&x,&y);
			scanf("%lld",&w);
			K[32][x][y]--;
			K[32][y][x]--;
			K[32][x][x]++;
			K[32][y][y]++;
			for(ll p= 0;p<=30;p++){
				if((1LL<<p)&w){
					K[p][x][y]--;
					K[p][y][x]--;
					K[p][x][x]++;
					K[p][y][y]++;
				}
			}
		}
		ll ans=0;
		for(ll p=0;p<=30;++p){
			//	cout<<p<<" "<<gauss(p,n)<<endl;
			ans=(ans+gauss(p,n)*(1LL<<p)%mod)%mod;
		}
		ll Mu=gauss(32,n)%mod;
		ans=ans*inv(Mu)%mod;
		printf("%lld\n",ans);
	}
	return 0;
}


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!