矩阵树定理

参考 生成树计数

升级版的高斯消元

//首先是浮点数高斯消元
//这个和普通gauss一样
double gauss()
{
    double res=1.0;
    rep(i,1,n-1)
    {
        int r=i;
        rep(j,i+1,n-1)
            if(fab(a[r][i])<fabs(a[j][i])) r=j;
        if(r!=i) swap(a[r],a[i]),res=-res;
        if(fabs(a[r][i])<eps) return 0;
        rep(j,i+1,n-1)
        {
            double f=a[j][i]/a[i][i];
            rep(k,i,n-1)
                a[j][k]-=f*a[i][k];
        }
        res*=a[i][i];
    }
    return res;
}

//辗转相除可取模避免浮点数
//准确准确而说就是第i行的所有数和第j行的所有数辗转相除一次
//然后交换位置使得大的在i行小的在j行持续下去最后第j行的第i列为0
int gauss()
{
    int res=1;
    rep(i,1,n-1)
    {
        rep(j,i+1,n-1)
        {
            while(a[j][i])//辗转相除
            {
                int t=a[i][i]/a[j][i];
                rep(k,i,n-1)
                a[i][k]=(a[i][k]-t*a[j][k]+mod)%mod;
                swap(a[i],a[j]);
                res=-res;
            }
        }
        res=(res*a[i][i]+mod)%mod;//有可能负数
    }
    return  res;
}