【学习笔记】BEST定理

时间：2023-10-03 08:28:44
  • 害怕忘记简单写一点：
  • 无向图的生成树计数：https://www.cnblogs.com/zj75211/p/8039443.html   （*ZJ学长 ORZ ）
  • 有向图的欧拉回路计数：https://blog.csdn.net/john123741/article/details/76586690
  • 连通图$G = (V,E)$，欧拉回路条数$ec(G)$，$t_{s}$为有向图以$s$为根的树（内或外）个数，；
  • 令$N_{x}(K)$为矩阵$K$去掉$x$阶的主子式，省略$x$表任意一阶，

  • 无向图的生成树：

  • 令$K = D - A$,D为度数矩阵，$A$为邻接矩阵;
  • 无向图生成树个数$t = det(N(K))$

  • 有向图的生成树：

  • 分内向(边由叶子指向根)和外向(由根指向叶子)；
  • 外向树：$K = D - A$，$D$为入度矩阵，$A$为邻接矩阵;
  • $t_{s} = det(N_{s}(K))$;
  • 内向树：$K = D - A$，$D$为出度矩阵，$A$为邻接矩阵;
  • 同样有$t_{s} = det(N_{s}(K))$;

  • 有向图的欧拉回路：

  • 如果每个点出度和入度不相等为0；
  • $deg(u)$表示每个点的度数=出度=入度，以s为起点，$t_{s}$指外向树；
  • $ec_{s}(G) \ =  \  t_{s}  \  \Pi_{u \in V} (\deg(u)-1)!$
  • 另外我发现其实这里的$t_{s}$的$s$可以换成任意点，也就是说有欧拉回路的图所有点的外向树个数都是一样的不知道对不对？？
  • 如果边的环同构不算一种方案再乘上一个起点度数$deg(s)$;
  • 所以大家的式子会有些小差异就是因为这个；
  • 放一个裸题bzoj3659：
  •  #include<bits/stdc++.h>
    
 using namespace std;
    
 const int N=,M=,mod=;
    
 int n,m,fac[M],deg[N],a[N][N];
    
 int pw(int x,int y){
    
     int re=;
    
     for(;y;y>>=,x=1ll*x*x%mod){
    
         if(y&)re=1ll*re*x%mod;
    
     }
    
     return re;
    
 }
    
 int gauss(){
    
     int fg=,re=;
    
     for(int i=;i<n;++i){
    
         int pos=i;
    
         for(int j=i;j<n;++j)if(a[j][i]){
    
         pos=j;break;
    
         }
    
         if(pos!=i){
    
             fg^=;
    
             for(int j=i;j<n;++j)swap(a[i][j],a[pos][j]);
    
         }
    
         re=1ll*re*a[i][i]%mod;
    
         int tmp = pw(a[i][i],mod-);
    
         for(int j=i;j<n;j++)a[i][j]=1ll*a[i][j]*tmp%mod;
    
         for(int j=i+;j<n;++j)
    
         for(int k=n-;k>=i;--k)a[j][k]=(a[j][k]-1ll*a[j][i]*a[i][k]%mod+mod)%mod;
    
     }
    
     if(fg)re=mod-re;
    
     return (re+mod)%mod;
    
 }
    
 int main(){
    
     freopen("bzoj3659.in","r",stdin);
    
     freopen("bzoj3659.out","w",stdout);
    
     for(int i=fac[]=;i<=2e5;++i)fac[i]=1ll*fac[i-]*i%mod;
    
     while(~scanf("%d",&n)&&n){
    
         for(int i=;i<=n;++i){
    
             for(int j=;j<=n;++j)a[i][j]=;
    
         }
    
         for(int i=,s;i<=n;++i){
    
             scanf("%d",&s);
    
             deg[i]=s;
    
             for(int j=,x;j<=s;++j){
    
                 scanf("%d",&x);
    
                 if(i!=x)a[i][x]--,a[i][i]++;
    
             }
    
         }
    
         if(n==){printf("%d\n",fac[deg[]]);continue;}
    
         int ans = gauss();
    
         for(int i=;i<=n;++i)ans=1ll*ans*fac[deg[i]-]%mod;
    
         ans = 1ll * deg[] * ans %mod;
    
         printf("%d\n",ans);
    
     }
    
     return ;
    
 }

    bzoj3659

  • 未完待续。。。。。。。。。。。。。。。。。。

相关文章