「SAO」关卡顺序计数题解

问题分析

给定一棵树和边上的方向约束（< 或 >），求满足所有约束的拓扑序列个数。

核心思路

使用树形DP + 组合数学的方法，在DFS过程中合并子树信息。

算法详解

1. 状态定义

• f[x][i]: 在节点x的子树中，x在左边部分排名为第i位的方案数
• g[x][i]: 在节点x的子树中，x在右边部分排名为第i位的方案数
• dp[x][i]: 在节点x的子树中，x排名为第i位的总方案数

2. 关键函数

int c2(int x, int y) {
    return g2[x] * f2[y] % mod * f2[x - y] % mod;
}

计算组合数 $C_x^y$，用于合并不同子树的排列。

3. DFS过程

初始化

void dfs(int x, int y) {
    int la = 0, ra = 0;  // 左右子树大小
    // 遍历所有子节点...
}

处理左子树 (v=0, 表示x在k之前)

if (!a[i].v) {  // x < k, x在k前面
    if (!la) {  // 第一个左子树
        for (int j = 0; j <= siz[k]; j++)
            f[x][j] = dp[k][j];
        la = siz[k];
        continue;
    }
    // 合并当前左子树与已有左子树...
}

处理右子树 (v=1, 表示x在k之后)

else {  // x > k, x在k后面
    reverse(dp[k] + 1, dp[k] + siz[k] + 1);
    // 合并逻辑与左子树类似...
}

4. 合并策略

使用组合数合并的方法：

对于两个排列A(长度la)和B(长度lb)，合并成长度la+lb的排列，方案数为：

在代码中体现为：

f[x][j + l] = (f[x][j + l] + nw * dp[k][l] % mod * 
    c2(j + l - 1, l) % mod * 
    c2(siz[k] - l + la - j, la - j)) % mod;

5. 最终合并

将左右子树的结果合并：

for (int i = 0; i <= la; i++) {
    for (int j = 0; j <= ra; j++) {
        int nw = f[x][i] * g[x][j + 1] % mod * 
                 c2(i + j, i) % mod * 
                 c2(la - i + ra - j, ra - j) % mod;
        dp[x][i + j + 1] = (dp[x][i + j + 1] + nw) % mod;
    }
}

复杂度分析

• 时间复杂度: $O(n^3)$，每个节点最多处理$n^2$状态
• 空间复杂度: $O(n^2)$

关键技巧

1. 分离左右子树: 根据边方向将子树分为"x在子节点前"和"x在子节点后"两类
2. 前缀和优化: 使用前缀和加速DP转移
3. 组合数合并: 使用组合数计算不同排列的合并方案
4. 逆序处理: 对于右子树，通过reverse操作统一处理逻辑

样例验证

对于样例：

5
0 < 2
1 < 2  
2 < 3
2 < 4

输出为4，符合预期。

这种解法通过巧妙的树形DP设计和组合数学的应用，高效地解决了带约束的拓扑排序计数问题。