洛谷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\) 个，则为 \(\dbinom{i+j-1}{j}\)
- 同理， \(u\) 后面有 \(\text{sz}[u]+\text{sz}[v]-i-j\) 个元素，
  
  其中 \(\text{sz}[v]-j\) 个是 \(v\) 的，则为 \(\dbinom{\text{sz}[u]+\text{sz}[v]-i-j}{\text{sz}[v]-j}\)
故转移方程为 \[ dp[u][i+j]=dp[u][i+j]+\dbinom{i+j-1}{j}\times \dbinom{\text{sz}[u]+\text{sz}[v]-i-j}{\text{sz}[v]-j} \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;
}