[ARC162D] Smallest Vertices 题解

题目链接

点击打开链接

题目解法

这种树的形态计数题首先可以想到 \(prufer\) 序列计数，如果没有任何限制，那么方案数为 \(\prod \frac{(n-2)!}{deg_i}\)，其中 \(deg_1=d_1-1,deg_i=d_i(2\le i\le n)\)

对于每个点分开求贡献
考虑这个式子只和点的个数和子树内的 \(\sum deg\) 有关
所以说，如果我们知道了 点数为 \(x\)，且 \(\sum deg=y\) 的方案数，是容易求出最后的方案数的（系数可以直接看代码）
点数为 \(x\)，且 \(\sum deg=y\) 的方案数 是容易背包求解的，只要从后往前加点，就可以做到 \(O(n^3)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=510,P=998244353;
int n,fac[N],ifac[N],d[N],f[N][N];
int qmi(int a,int b){
    int res=1;
    for(;b;b>>=1){ if(b&1) res=1ll*res*a%P;a=1ll*a*a%P;}
    return res;
}
void comb(int n){
    fac[0]=1;F(i,1,n) fac[i]=1ll*fac[i-1]*i%P;
    ifac[n]=qmi(fac[n],P-2);DF(i,n-1,0) ifac[i]=1ll*ifac[i+1]*(i+1)%P;
}
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
int main(){
    n=read();
    comb(n);
    F(i,1,n) d[i]=read();
    int tot=1ll*fac[n-2]*ifac[d[1]-1]%P;
    F(i,2,n) tot=1ll*tot*ifac[d[i]]%P;
    int ans=tot;
    f[0][0]=1;
    DF(i,n,2){
        if(!d[i]) inc(ans,tot);
        else{
            int res=1ll*ifac[d[1]-1]*ifac[d[i]-1]%P;
            F(j,2,n) if(i!=j) res=1ll*res*ifac[d[j]]%P;
            F(j,d[i],n-i) inc(ans,1ll*res*f[j][j-d[i]]%P*fac[max(0,n-j-2)]%P*fac[j-1]%P);
        }
        DF(p,n,1) DF(q,n,d[i]) inc(f[p][q],f[p-1][q-d[i]]);
    }
    printf("%d\n",ans);
    return 0;
}