2018-team4-modules-生成树计数

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
// a[i][j] = D[i][j] - G[i][j]
// 基尔霍夫矩阵a[i][j]为度数矩阵D[i][j]与邻接矩阵G[i][j]的差
// 生成树数目为det(n-1) (a[1..n][1..n])
int a[maxn][maxn];
inline int det(int n){
    int ret = 1,s=0;
    rep(i,1,n){
        rg r = i;
        for(r=i;r <= n;++r) if(a[r][i] != 0) break;
            if(r == n+1) return 0;
        if(r != i){
            s ^= 1;
            rep(j,i,n) swap(a[r][j],a[i][j]);
        }
        rep(j,i+1,n){
            while(a[j][i]){
                int x = a[j][i]/a[i][i];
                rep(k,i,n){
                    a[j][k] -= 1LL*a[i][k]*x % mod;
                    if(a[j][k] < 0) a[j][k] += mod;
                }
                if(a[j][i] == 0) break;
                s ^= 1;
                rep(k,i,n) swap(a[j][k],a[i][k]);
            }
        }
        ret = 1LL*ret*a[i][i] % mod;
    }
    if(s) ret = mod - ret;
    return ret;
}
}}}

// a[i][j] = D[i][j] - G[i][j]
// 基尔霍夫矩阵a[i][j]为度数矩阵D[i][j]与邻接矩阵G[i][j]的差
// 生成树数目为det(n-1) (a[1..n][1..n])
int a[maxn][maxn];
inline int det(int n){
    int ret = 1,s=0;
    rep(i,1,n){
        rg r = i;
        for(r=i;r <= n;++r) if(a[r][i] != 0) break;
            if(r == n+1) return 0;
        if(r != i){
            s ^= 1;
            rep(j,i,n) swap(a[r][j],a[i][j]);
        }
        rep(j,i+1,n){
            while(a[j][i]){
                int x = a[j][i]/a[i][i];
                rep(k,i,n){
                    a[j][k] -= 1LL*a[i][k]*x % mod;
                    if(a[j][k] < 0) a[j][k] += mod;
                }
                if(a[j][i] == 0) break;
                s ^= 1;
                rep(k,i,n) swap(a[j][k],a[i][k]);
            }
        }
        ret = 1LL*ret*a[i][i] % mod;
    }
    if(s) ret = mod - ret;
    return ret;
}