P12059 [THUPC2025决赛] I'm Here(DP)

Shui_Dream · 2025-04-10 19:44:22 · 题解

现有一棵 dfs 序为 1,2,...,n 的树。对于所有 i 求选出 i 个点的好排列的方案数。

好排列满足以下条件：

• 若点 u,v 都被选中且 u 是 v 的祖先，那么在排列中 u 在 v 后面。

• 若点 u 被选中，那么 u 必须出现在序列中前 (n-i+1) 个位置。

考虑如果没有限制 2，第一个限制是简单的内向树拓扑序计数问题。简单树上背包可以做到 O(n^2)。设 g_{u,i} 表示 u 子树内选出 i 个点且 u 被选中的满足限制的序列个数。

考虑限制 2，容易发现最终序列中是后缀最大值的位置的限制是更严格的。其他位置只要满足限制 1 即可。考虑从大到小将每个被选中的数插入序列，如果插入时插在了序列末尾，那么其为后缀最大值。

设 f_{i,j,k} 表示填完了 \ge i 的数，填了 j 个，强制当前序列最后一个数填在位置 k 的方案数。

分类讨论：

复杂度 O(n^4)。代码很好写。

#include<bits/stdc++.h>
#define psb push_back
using namespace std;
typedef long long LL;
inline int read(){
    char ch=getchar(); while(!isdigit(ch) && ch!='-') ch=getchar();
    int x=0,ff=1; if(ch=='-') ff=-1,ch=getchar();
    while(isdigit(ch)) x=(x<<3) + (x<<1) + (ch^48),ch=getchar();
    return x*ff;
}
const int N=85,P=998244353;
inline void add(int &x,int y) {x+=y; x=x>=P?x-P:x;}
int n,fz[N][N],fzu[N][N],fz2[N],sz[N],rd[N],C[N][N],f[N][N][N]; vector<int> e[N];
void dfs1(int u){
    sz[u]=0; fz[u][0]=1; rd[u]=u;
    for(int v:e[u]){
        dfs1(v); rd[u]=rd[v];
        for(int i=0;i<=sz[u]+sz[v];i++) fz2[i]=fz[u][i],fz[u][i]=0;
        for(int i=0;i<=sz[u];i++) for(int j=0;j<=sz[v];j++) add(fz[u][i+j],1ll*fz2[i]*fz[v][j]%P*C[i+j][i]%P);
        sz[u]+=sz[v];
    }
    ++sz[u]; for(int i=sz[u];i>=1;i--) fzu[u][i]=fz[u][i-1],add(fz[u][i],fzu[u][i]);

}
int main(){
    for(int i=0;i<N;i++){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
    }
    n=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read(); if(u>v) swap(u,v);
        e[u].psb(v);
    }
    dfs1(1); f[n+1][0][0]=1;
    for(int i=n,bf;i>=1;i--){
        if(i>1){
            for(int j=0;j<=n-rd[i];j++) for(int k=j;k<=n;k++) if((bf=f[rd[i]+1][j][k]))
                for(int l=1;l<=sz[i] && l<=k-j;l++) add(f[i][j+l][k],1ll*C[k-j][l]*fzu[i][l]%P*bf%P);
        }
        for(int j=0;j<=n-i;j++) for(int k=j;k<=n;k++) if((bf=f[i+1][j][k])){
            if(i>1) add(f[i][j][k],bf);
            for(int l=k+1;l<=n;l++) if(l<=n-i+1) add(f[i][j+1][l],bf);
        }
    }
    for(int i=1;i<=n;i++) printf("%d ",f[1][i][i]);
    puts("");
    return 0;
}