题解：P9535 [YsOI2023] 连通图计数

· · 题解

数树好题。拼尽全力没想出来怎么处理 m=n+1 鉴定为失败至极。

循序渐进的考虑，先考虑树的情况。

显然那个 a_i 变成描述度数，然后套 prufer 序列经典结论：一个点会在这个树的 prufer 序列中出现度数减一次，直接对着这个 prufer 序列组合计数即可。

考虑加一条边，基环树。

基环树肯定是要对着环刻画的，考虑把环展平断开成森林，不在环上的点依旧描述度数，在环上的 a_i 会比度数多一个。

考虑给定都是度数怎么做。

这个是经典问题有标号有根森林计数，经典处理办法是加一个超级源点，然后转变成有标号固定根计数，即有标号无根树计数。

显然把超级源点删去后得到的图就是有标号有根森林，这俩玩意是双射的。

然后把环上的点看成根，于是你会发现多一个的度数刚好描述了连向超级源点的边，所以直接往图里丢一个点然后按照树来数就可以了……吗？

考虑到这样的话环的形态所带来的贡献就消失了。

但是注意到我们可以根据 prufer 序列剩下的空位来反推出源点的度数，因此环的大小是固定的 c，我们只需要对于 c 个不同的球再数一遍能构成多少环就好了。

显然可以枚举全排列，但是一个排列循环同构不能重复计数，一个排列会有 c 个循环同构的排列，因此除一下就好了。

考虑再加一条边！

仔细研读上面的树的处理，我们发现这个源点是对于环上的点一一连边，然后环内原有的边全部断开。

这个不是圆方树吗！

于是类似的，我们考虑继续建圆方树，但对于两个多出来的边需要进行分讨。

图是一个仙人掌，有两个边不重合的环。

此时是一个 n+2 个点的圆方树，每个 a_i 依旧描述这个点的树上度数。

直接拍 prufer 序列然后把所有圆点的出现方案给算掉，然后接着枚举其中一个方点的出现次数，固定下来后一样可以计算连出来的环的种数，把每个情况的方案和全计数一遍即可。

注意禁止重边的话环至少得有三个数，也就是方点度数不能低于 3。

然后注意到我们不能让方点相邻，直接限制是困难的，考虑容斥一步，我们先按照上面计数出无限制的情况，然后强行把这两个点先连一个边，看成一个点数一遍，然后再枚举度数划分套用上面的方法计数所有方案即可。

注意这里所有的都是把方点视作可区分的，但事实上方点只是描述所连向的点是一个环，不可区分，因此交换编号是一种方案，需要折半一下。

考虑两个环有交的情况，此时依然建圆方树，插入一个方点，然后 a_i 依旧描述树上点的度数。

直接跑 prufer 序列计数，然后计算出方点的度数 t，我们需要对 t 求有 t+1 个边的点双数量。

这样的点双应该长的和滚木（见下图）差不多，我们把中间那个线的两端拆掉就变成了三个链。

考虑怎么得到三个链的分配，我们把剩下的点任意重排，然后插两个板进去分成三段，每段截出来当一个链，于是可以计数。

然后注意到三个链至多可以任意选择一个链设置为完全没有点，如果有两个链的话就会出现重边，因此板子不能全部放在左右极端位置，这里共计三种情况。

三个链任意重排上中下方案等价，于是要除掉。

那么做完了。

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
#define N 100000
using namespace std;
int qpow(int a,int b=mod-2){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
int A[N+5],inv[N+5]; 
void init(){
    A[0]=1;
    for(int i=1;i<=N;i++)
    A[i]=A[i-1]*i%mod;
    inv[N]=qpow(A[N]);
    for(int i=N;i;i--)
    inv[i-1]=inv[i]*i%mod;
}
int C(int n,int m){
    return A[n]*inv[m]%mod*inv[n-m]%mod;
}
int qry(int x){
    return qpow(2)*A[x-1]%mod;
}
int a[N+5],n;
void solve1(){
    int ans=1,flc=n-2;
    for(int i=1;i<=n;i++)
    ans=ans*C(flc,a[i]-1)%mod,
    flc-=a[i]-1;
    cout<<ans;
    return;
}
void solve2(){
    int ans=1,flc=n-1;
    for(int i=1;i<=n;i++)
    ans=ans*C(flc,a[i]-1)%mod,
    flc-=a[i]-1;
    ans=ans*qry(flc+1)%mod;
    cout<<ans;
    return;
}
int cc(int t){
    return C(t,2)*A[t-2]%mod*((C(t,2)-3+mod)%mod)%mod*qpow(6)%mod;
}
int solve4(){
    int ans=1,flc=n-1;
    for(int i=1;i<=n;i++)
    ans=ans*C(flc,a[i]-1)%mod,
    flc-=a[i]-1;
    return ans*cc(flc+1);
}
int solve3(){
    int ans=1,flc=n;
    for(int i=1;i<=n;i++)
    ans=ans*C(flc,a[i]-1)%mod,
    flc-=a[i]-1;
    int ans2=1,flc2=n-1;
    for(int i=1;i<=n;i++)
    ans2=ans2*C(flc2,a[i]-1)%mod,
    flc2-=a[i]-1;
    ans-=ans2,ans+=mod,ans%=mod;
    int qwq=0;
    for(int i=2;i<=flc-2;i++)
    qwq=(qwq+C(flc,i)*qry(i+1)%mod*qry(flc-i+1)%mod)%mod;
    ans=(ans*qpow(2))%mod;
    return qwq*ans%mod;
}
void solve(){
    cout<<(solve3()+solve4())%mod;
    return;
}
signed main(){
    init();
    int m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    if(m==n-1)solve1();
    if(m==n)solve2();
    if(m==n+1)solve();
    return 0;
}
//『我曾经希望一个人幸福，他是我很重要的家人，但是……』

//『我杀了他，了结了他的生命。』
//『这样的我，才没有资格获得幸福。』