[ARC165E] Random Isolation 题解

题目链接

点击打开链接

题目解法

略有些套路的概率题，不过中间的把操作序列看成排列的操作还是很妙的

首先套路的考虑期望的线性性，有两个方式：把贡献放在点上或点集上，这里采用后面的方式做
对于每一个树上的集合 \(S\)，假设大小为 \(n\)，相邻的点为 \(m\)
考虑这个集合独立的限制为：相邻的 \(m\) 个点在点集 \(S\) 中的所有点被删之前删，即把这些数看成排列，前 \(n\) 个数和后 \(m\) 个数是什么已经固定了，只需要内部排列，不难得到概率为 \(\frac{n!m!}{(n+m)!}\)
我们只需要求出点对 \((n,m)\) 的方案数，然后统计答案即可
不难用树形 \(dp\) 维护
时间复杂度 \(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 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=110,P=998244353;
int n,k,f[N][N][N],ans,g[N][N];
int fac[N],ifac[N],siz[N];
int e[N<<1],h[N],ne[N<<1],idx;
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
void add(int x,int y){ e[idx]=y,ne[idx]=h[x],h[x]=idx++;}
void dfs(int u,int fa){
    siz[u]=1,f[u][1][0]=1;
    for(int i=h[u];~i;i=ne[i]){
        int v=e[i];if(v==fa) continue;
        dfs(v,u);
        F(j,1,siz[u]+siz[v]) F(k,0,siz[u]+siz[v]) g[j][k]=0;
        //cut 
        F(j,1,siz[u]) DF(k,siz[u],1) inc(g[j][k],f[u][j][k-1]);
        //do not cut
        F(j,1,siz[u]) F(k,1,siz[v]) F(p,0,siz[u]) F(q,0,siz[v]) inc(g[j+k][p+q],1ll*f[u][j][p]*f[v][k][q]%P);
        siz[u]+=siz[v];
        F(j,1,siz[u]) F(k,0,siz[u]) f[u][j][k]=g[j][k]; 
    }
    F(j,k+1,siz[u]) F(q,0,siz[u]) if(f[u][j][q]){
        int nq=q+(u!=1);
        inc(ans,1ll*f[u][j][q]*fac[j]%P*fac[nq]%P*ifac[j+nq]%P);
    }
}
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;
}
int main(){
    n=read(),k=read();
    ms(h,-1);
    F(i,1,n-1){
        int x=read(),y=read();
        add(x,y),add(y,x);
    }
    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;
    dfs(1,-1);
    printf("%d\n",ans);
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}