P5296 [北京省选集训2019]生成树计数（矩阵树定理+生成函数）

· · 题解

P5296 [北京省选集训2019]生成树计数

一个结论： a^i 的 EGF 卷 b^i 的 EGF 的结果为 (a+b)^i 的 EGF。

证明：

 (a+b)^i=\sum\limits_{j=0}^i{i\choose j}a^jb^{i-j}=\sum\limits_{j=0}^i\frac{i!}{j!(i-j)!}a^jb^{i-j}\\\frac{(a+b)^i}{i!}=\sum\limits_{j=0}^i\frac{a^j}{j!}\frac{b^{i-j}}{(i-j)!}

矩阵树定理的实际含义： Laplacian 矩阵的主余子式等于 \sum_T \prod_{(u, v)\in T} w(u,v)

我们构造一个多项式矩阵，其中 w(u,v)=\sum_{i=0}^k\frac{w^i}{i!}x^i，然后对这个矩阵进行高斯消元即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace FGF
{
    int n,m;
    const int N=35,mo=998244353;
    int fac[N],inv[N];
    int qpow(int x,int y)
    {
        int s=1;
        while(y)
        {
            if(y&1)s=1ll*s*x%mo;
            x=1ll*x*x%mo;
            y>>=1;
        }
        return s;
    }
    struct poly{
        int a[N];
        poly():a(){};
        poly(int x):a(){for(int i=0,w=1;i<=m;i++,w=1ll*w*x%mo)a[i]=1ll*w*FGF::inv[i]%mo;}
        int &operator [](const int &x){return a[x];}
        const int &operator [](const int &x)const {return a[x];}
        friend poly operator +(const poly &a,const poly &b)
        {
            poly ans;
            for(int i=0;i<=m;i++)
                ans[i]=(a[i]+b[i])%mo;  
            return ans;
        }
        friend poly operator -(const poly &a,const poly &b)
        {
            poly ans;
            for(int i=0;i<=m;i++)
                ans[i]=(a[i]-b[i]+mo)%mo;   
            return ans;
        }
        friend poly operator *(const poly &a,const poly &b)
        {
            poly ans;
            for(int i=0;i<=m;i++)
                for(int j=0;j<=i;j++)
                    ans[i]=(ans[i]+1ll*a[j]*b[i-j]%mo)%mo;  
            return ans;
        }
        poly operator -() const
        {
            poly ans;
            for(int i=0;i<=m;i++)
                ans[i]=(-a[i]+mo)%mo;   
            return ans;
        }
        inline poly inv() const 
        {
            poly b;
            b[0]=qpow(a[0],mo-2);
            for(int i=1;i<=m;i++)
            {
                for(int j=0;j<i;j++)
                    b[i]=(b[i]-1ll*b[j]*a[i-j]%mo+mo)%mo;
                b[i]=1ll*b[i]*b[0]%mo;
            }
            return b;
        }
        friend poly operator /(const poly &a,const poly &b){return a*b.inv();}
    }a[N][N],ans;
    void work()
    {
        scanf("%d%d",&n,&m);
        inv[0]=fac[0]=1;
        for(int i=1;i<=m;i++)
            fac[i]=1ll*fac[i-1]*i%mo;
        inv[m]=qpow(fac[m],mo-2);
        for(int i=m-1;i>0;i--)
            inv[i]=1ll*inv[i+1]*(i+1)%mo;
        for(int i=0;i<n;i++)
            for(int j=0,x;j<n;j++)
            {
                scanf("%d",&x);
                if(i!=j)a[i][j]=-poly(x),a[i][i]=a[i][i]-a[i][j];
            }
        ans[0]=1;
        for(int i=1;i<n;i++)
        {
            poly tmp=a[i][i].inv();
            ans=ans*a[i][i];
            for(int j=i;j<n;j++)a[i][j]=a[i][j]*tmp;
            for(int j=1;j<n;j++)    
                if(j!=i)
                {
                    poly cur=a[j][i];
                    for(int k=i;k<n;k++)
                        a[j][k]=a[j][k]-a[i][k]*cur;
                }       
        }
        printf("%lld",1ll*ans[m]*fac[m]%mo);        
    }   
}
int main()
{
    FGF::work();
    return 0;
}