P13835 返夏题解

Gold14526 · 2026-01-21 10:21:03 · 题解

哦哦哦毛毛虫坐火箭。

把每条边两端的点当作关键点，把环上每两个关键点之间的环缩成一条边，可以得到点数边数都是 O(m) 的一张图。

求这张图的生成树数量显然用矩阵树定理，单次 O(m^2) 求稀疏矩阵行列式即可。

常数太大了 m\le 500 都过不去（难过）。

mt19937 mt(chrono::system_clock().now().time_since_epoch().count());
cint N=1600,M=800;
cint mod=998244353;
int n,m;
int c[N+1];
map<int,int>mp;
int eu[M+1],ev[M+1];
int deg[N+1];
struct edge{
    int to,val,nxt;
}E[(N+M)<<1|1];
int head[N+1];
int tot;
inline void add_edge(cint u,cint v,cint w)
{
    E[++tot]={v,w,head[u]};
    head[u]=tot;
    E[++tot]={u,w,head[v]};
    head[v]=tot;
    ((deg[u]+=w)>=mod)&&(deg[u]-=mod);
    ((deg[v]+=w)>=mod)&&(deg[v]-=mod);
}
int a[N<<1|1],sc[N<<1|1][N+1],base[N+1];
int detb;
inline int qpow(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1)res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        y>>=1;
    }
    return res;
}
int calc()
{
    detb=1;
    for(int i=1;i<n;++i)
    {
        sc[0][i]=mt()%mod;
        base[i]=mt()%mod;
        detb=1ll*detb*base[i]%mod;
    }
    for(int i=1;i<=(n<<1);++i)
    {
        for(int u=1;u<n;++u)
        {
            __int128 s=1ll*sc[i-1][u]*deg[u]%mod*base[u];
            for(int j=head[u];j;j=E[j].nxt)
            {
                cint v=E[j].to;
                s-=1ll*sc[i-1][v]*E[j].val%mod*base[v];
            }
            sc[i][u]=s%mod;
            (sc[i][u]<0)&&(sc[i][u]+=mod);
        }
    }
    for(int i=1;i<n;++i)base[i]=mt()%mod;
    for(int i=0;i<=(n<<1);++i)
    {
        __int128 s=0;
        for(int j=1;j<n;++j)
        {
            s+=1ll*sc[i][j]*base[j];
        }
        a[i]=s%mod;
    }
    vector<int>v,lstv;
    int lst=-1,lstd=0;
    for(int i=0;i<=(n<<1);++i)
    {
        __int128 sd=a[i];
        for(int j=0;j<v.size();++j)
        {
            sd-=1ll*a[i-j-1]*v[j];
        }
        int d=sd%mod;
        (d<0)&&(d+=mod);
        if(!d)continue;
        if(lst<0)
        {
            lst=i;
            lstd=d;
            v=vector<int>(i+1);
            continue;
        }
        vector<int>u=v;
        cint val=1ll*d*qpow(lstd,mod-2)%mod;
        if(v.size()<lstv.size()+i-lst)v.resize(lstv.size()+i-lst);
        ((v[i-lst-1]+=val)>=mod)&&(v[i-lst-1]-=mod);
        for(int j=0;j<lstv.size();++j)
        {
            v[i-lst+j]=(v[i-lst+j]-1ll*val*lstv[j])%mod;
            (v[i-lst+j]<0)&&(v[i-lst+j]+=mod);
        }
        if((int)u.size()-i<(int)lstv.size()-lst)
        {
            lstv=u;
            lst=i;
            lstd=d;
        }
    }
    for(int &x:v)x=(x?mod-x:0);
    v.insert(v.begin(),1);
    return 1ll*v[v.size()-1]*qpow(detb,mod-2)%mod*((n&1)?1:mod-1)%mod;
}
int rn;
void solve(cint m)
{
    n=(m<<1);
    for(int i=1;i<=m;++i)
    {
        c[i]=eu[i];
        c[i+m]=ev[i];
    }
    sort(c+1,c+n+1);
    n=0;
    for(int i=1;i<=(m<<1);++i)
    {
        if(c[i]!=c[n])
        {
            swap(c[i],c[++n]);
        }
    }
    mp.clear();
    for(int i=1;i<=n;++i)mp[c[i]]=i;
    tot=0;
    for(int i=1;i<=n;++i)head[i]=deg[i]=0;
    for(int i=1;i<n;++i)add_edge(i,i+1,qpow(c[i+1]-c[i],mod-2));
    add_edge(1,n,qpow(rn-c[n]+c[1],mod-2));
    int base=1;
    for(int i=1;i<n;++i)base=1ll*base*(c[i+1]-c[i])%mod;
    base=1ll*base*(rn-c[n]+c[1])%mod;
    for(int i=1;i<=m;++i)
    {
        add_edge(mp[eu[i]],mp[ev[i]],1);
    }
    princh(1ll*calc()*base%mod,'\n');
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    rn=read();
    m=read();
    for(int i=1;i<=m;++i)
    {
        eu[i]=read();
        ev[i]=read();
    }
    for(int i=1;i<=m;++i)solve(i);
    return 0;
}

P13835 返夏 题解

P13835 返夏题解