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

现有一棵 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

的方案数。

分类讨论：

$i$ 没被选中，继承 $f_{i+1}$ 的状态即可。
$i$ 被选中，且为后缀最大值， $i$ 填在当前序列末尾，枚举一个位置 $x$ ，满足 $k<x\le n-i+1$ ，从 $f_{i+1}$ 转移过来。显然满足限制 1。
$i$ 被选中，且不为后缀最大值，枚举子树内包括 $i$ 共选了 $x$ 个数，那么这 $x$ 个数填在 $k$ 前面即可。有 $f_{i,j+x,k}\leftarrow f_{i+sz_i,j,k}\times g_{i,x}\times \binom{k-j}{x}$ 。

复杂度

O(n^4)

。代码很好写。

CPP

#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;
}

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

文章操作

相关推荐

评论

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