マトリックスツリーMatrix-Tree定理実装テンプレート(Gauss消元解行列式)

大男1ブログ:https://www.cnblogs.com/zj75211/p/8039443.html
大男2ブログ:https://www.cnblogs.com/yangsongyi/p/10697176.html
3つの定理:

は無方向図を与え、この図の生成ツリー個数

を求める.

は有向図とその中の1つの点を与え、この点をルートとする生成外向ツリー個数

を求める.

は有向図とその中の1つの点を与える、この点をルートとする生成内向木個数

を求める.
上記3つの定理については,まずキルホフKirchhoff行列を構築する必要があり,構造方法は以下の通りである.
キルホフKirchhoff行列K=度数行列D-隣接行列A
上記の3つの定理について、それぞれ解く:

D行列:度数、A行列:無方向図、任意のr行目とr列目を削除した後の行列式の絶対値が答え

である.

D行列:入度、A行列:有向図、仮定点がxであれば、x行目とx列目を削除した後の行列式の絶対値が答え

となる.

D行列:出度、A行列:有向図、仮に点がxであれば、x行目とx列目を削除した後の行列式の絶対値が解答

となる.
最後にガウス消元を掛けて行列式のテンプレートを解いて、時間の複雑度はn^3で、空間の複雑度はn^2で、型を取ることを許可します
コード:

const int N=110;

const int mod=998244353;

LL a[N][N];

LL q_pow(LL a,LL b)
{
    LL ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

LL Gauss(int n)
{
    LL ans=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
            if(!a[i][i]&&a[j][i]) 
            {
                ans=-ans;
                swap(a[i],a[j]);
                break;
            }
        LL inv=q_pow(a[i][i],mod-2);
        for(int j=i+1;j<=n;j++)
        {
            LL temp=a[j][i]*inv%mod;
            for(int k=i;k<=n;k++)
                a[j][k]=(a[j][k]-a[i][k]*temp%mod+mod)%mod;
        }
        ans=ans*a[i][i]%mod;
    }
    return ans;
}