欧拉路条数（BEST定理 + 矩阵树定理 ）

前置技能：行列式（整数取模）求解模板

int Gauss(int n){    //求解行列式的值
    int ans = 1; 
    for(int i=2;i<=n;i++){
        for(int k=i+1;k<=n;k++){
            while(a[k][i]) {
                int d = a[i][i] / a[k][i];
                for(int j=i;j<=n;j++) a[i][j] = (a[i][j] - 1LL * d * a[k][j] % mod + mod) % mod;
                swap(a[i],a[k]),ans = -ans;   //必须交换，因为不是浮点数运算可能存在d = 0，导致a[k][i]一直不变
            }
        }
        ans = 1LL * ans * a[i][i] % mod,ans = (ans + mod) % mod;
    }
    return ans;
}

矩阵树定理：用于求解一个无向图的生成树个数，允许有重边和自环。

http://old.orzsiyuan.com/articles/algorithm-Matrix-Tree-Theorem/

#include <cstdio>
#include <algorithm>

const int N=305;
const int mod=1e9+7;
int n,m,a[N][N];

int Gauss(int n) {    //求解行列式的值
    int ans=1; 
    for(int i=1;i<=n;++i) {
        for(int k=i+1;k<=n;++k) {
            while(a[k][i]) {
                int d=a[i][i]/a[k][i];
                for(int j=i;j<=n;++j) a[i][j]=(a[i][j]-1LL*d*a[k][j]%mod+mod)%mod;
                std::swap(a[i],a[k]),ans=-ans;
            }
        }
        ans=1LL*ans*a[i][i]%mod,ans=(ans+mod)%mod;
    }
    return ans;
}
int main() {
    scanf("%d%d",&n,&m);
    while(m--) {
        int u,v;
        scanf("%d%d",&u,&v);
        --a[u][v],--a[v][u],++a[u][u],++a[v][v];
    }
    printf("%d\n",Gauss(n-1));
    return 0;
}

BZOJ4894

题解：有向图外向生成树的个数。

步骤；

• 对角线为点入度的个数。（如果是内向生成树，那么为出度的个数）
• 如果存在从i到j的边，那么a[i][j]--。
• 去掉根节点所在的行和列

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 305;
const int mod = 1e9+7;
int n,a[N][N];
char s[N];
int Gauss(int n){    //求解行列式的值
    int ans = 1; 
    for(int i=2;i<=n;i++){
        for(int k=i+1;k<=n;k++){
            while(a[k][i]) {
                int d = a[i][i] / a[k][i];
                for(int j=i;j<=n;j++) a[i][j] = (a[i][j] - 1LL * d * a[k][j] % mod + mod) % mod;
                swap(a[i],a[k]),ans = -ans;   //必须交换，因为不是浮点数运算可能存在d = 0，导致a[k][i]一直不变
            }
        }
        ans = 1LL * ans * a[i][i] % mod,ans = (ans + mod) % mod;
    }
    return ans;
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    	scanf(" %s",s+1);
    	for(int j=1;j<=n;j++){
    		if(s[j] == '1')	a[j][j]++,	a[i][j]--;   
    	}
    }
    printf("%d\n",Gauss(n));   
    return 0;
}

BEST定理：有向图欧拉回路个数

tw表示外向生成树的个数。deg表示出度。

bzoj3695

题解：https://blog.csdn.net/Jaihk662/article/details/79338437