洛谷P4099 [HEOI2013]SAO 题解

题目链接：P4099 [HEOI2013]SAO

题意：

Welcome to SAO ( Strange and Abnormal Online)。这是一个 VR MMORPG， 含有 $n$ 个关卡。但是，挑战不同关卡的顺序是一个很大的问题。

某款游戏有 $n-1$ 个对于挑战关卡的限制，诸如第 $i$ 个关卡必须在第 $j$ 个关卡前挑战，或者完成了第 $k$ 个关卡才能挑战第 $l$ 个关卡。并且，如果不考虑限制的方向性，那么在这 $n-1$ 个限制的情况下，任何两个关卡都存在某种程度的关联性。即，我们不能把所有关卡分成两个非空且不相交的子集，使得这两个子集之间没有任何限制。

高质量好题👍 做了我一下午+晚上

首先这个题面的意思：给定一棵有方向的树，求拓扑序总数

注意到这个特殊的性质，可以从树形dp的角度去解决这个问题

设 $dp[u][i]$ 表示结点 $u$ 在其子树的拓扑序中位于第 $i$ 位的方案数

对于每个 $u$ 的儿子 $v$ ，将 $v$ 不断合并到 $u$ 上，则有两种情况

• 新拓扑序中 $v$ 在 $u$ 前

  考虑枚举一个 $j$ 表示 $v$ 的子树中有 $j$ 个结点合并到了 $u$ 的前面

  则新的状态为 $dp[u][i+j]$

  • 合并后 $u$ 前面有 $i+j-1$ 个素，

    其中 $j$ 个是 $v$ 的，所以 $i+j-1$ 个格子取 $j$ 个，则为 $\left(\genfrac{}{}{0ex}{}{i+j-1}{j}\right)$

  • 同理， $u$ 后面有 $\text{sz}[u]+\text{sz}[v]-i-j$ 个素，

    其中 $\text{sz}[v]-j$ 个是 $v$ 的，则为 $\left(\genfrac{}{}{0ex}{}{\text{sz}[u]+\text{sz}[v]-i-j}{\text{sz}[v]-j}\right)$

  故转移方程为
  $$dp[u][i+j]=dp[u][i+j]+\left(\genfrac{}{}{0ex}{}{i+j-1}{j}\right)\times \left(\genfrac{}{}{0ex}{}{\text{sz}[u]+\text{sz}[v]-i-j}{\text{sz}[v]-j}\right)\times dp[u][i]\times dp[v][k]$$
  也就是

  for (int i=1;i<=sz[u];++i) for (int k=1;j<=sz[v];++k) for (int j=k;j<=sz[v];++j) dp[u][i+j]+=dp[u][i]*dp[v][k]*C[i+j-1][i-1]*C[sz[u]+sz[v]-i-j][sz[u]-i]); 

  考虑变换一下 $j,k$ 的枚举顺序

  for (int i=1;i<=sz[u];++i) for (int j=1;j<=sz[v];++j) for (int k=1;k<=j;++k) dp[u][i+j]+=dp[u][i]*dp[v][k]*C[i+j-1][i-1]*C[sz[u]+sz[v]-i-j][sz[u]-i]; 

  然后就可以愉快的前缀和优化啦！

• 新拓扑序中 $v$ 在 $u$ 后

  与上一种情况类似

  for (int i=1;i<=sz[u];++i) for (int j=0;j<=sz[v];++j) for (int k=i+1;k<=sz[v];++k) dp[u][i+j]+=dp[u][i]*dp[v][k]*C[i+j-1][i-1]*C[sz[u]+sz[v]-i-j][sz[u]-i]; 

  也可以前缀和优化

然后组合数 $O(n^2)$ 预处理

注意由于 dp[u][i+j]的更新，我们需要记录临时记录旧的 dp[u][i]

所以总的时间复杂度为 $O(n^2)$ （类似于树上背包的复杂度证明，此处略）

别忘了多组数据哦！ qwq

代码：

#include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(2e3+15) const int p=1e9+7; struct Edge { 
    int u,v,w,next; }e[N<<1]; int pos=1,head[N],C[N][N]; int n,sz[N],dp[N][N],tmp[N]; void addEdge(int u,int v,int w) { 
    e[++pos]={ 
   u,v,w,head[u]}; head[u]=pos; } void clear() { 
    pos=1; for(int i=1; i<=n; i++) { 
    head[i]=sz[i]=0; for(int j=1; j<=n; j++) dp[i][j]=0; } } void dfs(int u,int f) { 
    sz[u]=1;dp[u][1]=1; for(int i=head[u]; i; i=e[i].next) { 
    int v=e[i].v; if(v==f)continue; dfs(v,u); for(int i=1; i<=sz[u]; i++) tmp[i]=dp[u][i],dp[u][i]=0; if(e[i].w) { 
    for(int i=1; i<=sz[u]; i++) for(int j=0; j<sz[v]; j++) { 
    dp[u][i+j]=(dp[u][i+j]+C[sz[u]+sz[v]-i-j][sz[v]-j]* C[i+j-1][j]%p*tmp[i]%p*(dp[v][sz[v]]-dp[v][j]+p)%p)%p; } }else { 
    for(int i=1; i<=sz[u]; i++) for(int j=1; j<=sz[v]; j++) { 
    dp[u][i+j]=(dp[u][i+j]+C[sz[u]+sz[v]-i-j][sz[v]-j]* C[i+j-1][j]%p*tmp[i]%p*dp[v][j]%p)%p; } } sz[u]+=sz[v]; } for (int i=1; i<=sz[u]; i++) dp[u][i]=(dp[u][i]+dp[u][i-1])%p; } signed main() { 
    ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); // freopen("check.in","r",stdin); // freopen("check.out","w",stdout); C[0][0]=1; for(int i=1; i<=N-10; i++) { 
    C[i][0]=1; for(int j=1; j<=i; j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p; } int Q;cin >> Q; while(Q--) { 
    clear(); cin >> n; for(int i=1,u,v; i<n; i++) { 
    char ch;cin >> u >> ch >> v; ++u;++v; addEdge(u,v,ch=='<'); addEdge(v,u,ch=='>'); } dfs(1,1); cout << dp[1][n] << endl; } return 0; } 

参考文献

[1] https://www.luogu.com.cn/blog/i-am-zhiyangfan/solution-p4099

[2] https://www.luogu.com.cn/blog/ShadowassIIXVIIIIV/solution-p4099

[3] https://m-sea.blog.luogu.org/solution-p4099

转载请说明出处