USACO 2019 Platinum Tree Depth 题解

题目分析

这道题要求对于所有恰好有 $K$ 个逆序对的排列，计算每个位置在对应二叉搜索树中深度的总和。

关键点：

• 排列生成二叉搜索树：最小值作为根，递归构建
• 需要统计所有恰好有 $K$ 个逆序对的排列
• 对每个位置 $i$，求在所有满足条件排列中 $d_i(a)$ 的和

解题思路

核心观察

1. 深度与逆序对：节点 $i$ 的深度等于在排列中 $i$ 作为某个区间最小值的次数
2. 动态规划：逆序对数可以用 DP 统计
3. 生成函数：使用生成函数来处理逆序对分布

算法设计

代码采用了生成函数 + 动态规划的方法：

主要步骤：

1. 生成函数计算：计算逆序对分布的生成函数
2. 深度贡献分析：分析每个位置对深度的贡献
3. 组合计数：统计所有排列中每个位置的深度和

代码详解

#include <bits/stdc++.h>
#define ci const int
#define ll long long
using namespace std;

ci N = 305;
int n, k, mod;

// 模运算工具函数
inline void add(int &x, ci v) {
    x += v, x -= x < mod ? 0 : mod;
}
inline void sub(int &x, ci v) {
    x -= v, x += x < 0 ? mod : 0;
}

int co[N * N], rec[N][N * N], pre[N * N], tmp[N * N], ans[N];

// 生成函数乘法：乘以 (1 + x + ... + x^{x})
void mul(ci x) {
    if (!x) return;
    
    // 前缀和
    for (int i = 1; i <= n * n; ++i)
        add(co[i], co[i - 1]);
    
    // 计算新的系数：滑动窗口和
    for (int i = 0; i <= n * n; ++i)
        tmp[i] = (co[i] - (i >= x + 1 ? co[i - x - 1] : 0) + mod) % mod;
    
    for (int i = 0; i <= n * n; ++i)
        co[i] = tmp[i];
}

// 生成函数除法：除以 (1 + x + ... + x^{x})
void div(ci x) {
    if (!x) return;
    
    // 逆操作：通过前缀和恢复
    for (int i = 0; i <= n * n; ++i) {
        if (i) sub(co[i], (pre[i - 1] - (i >= x + 1 ? pre[i - x - 1] : 0) + mod) % mod);
        pre[i] = (pre[i - 1] + co[i]) % mod;
    }
}

int main() {
    scanf("%d%d%d", &n, &k, &mod);
    
    // 步骤1: 计算逆序对分布的生成函数
    co[0] = 1;
    for (int i = 1; i <= n; ++i)
        mul(i - 1);  // 乘以 (1 + x + ... + x^{i-1})
    
    // 步骤2: 预处理所有区间长度的生成函数
    for (int i = 0; i <= n; ++i) {
        div(i);  // 除以 (1 + x + ... + x^{i})
        
        for (int j = 0; j <= n * n; ++j)
            rec[i][j] = co[j];  // 记录长度为i的排列的逆序对分布
        
        mul(i);  // 恢复
    }
    
    // 步骤3: 计算每个位置的深度贡献
    for (int x = 1; x <= n; ++x) {
        // 情况1: x在某个节点的右子树中
        for (int r = x + 1; r <= n; ++r)
            if (k - (r - x) >= 0)
                add(ans[x], rec[r - x][k - (r - x)]);
        
        // 情况2: x在某个节点的左子树中  
        for (int l = 1; l <= x; ++l)
            add(ans[x], rec[x - l][k]);
    }
    
    for (int i = 1; i <= n; ++i)
        printf("%d ", ans[i]);
    
    return 0;
}

算法原理详解

1. 生成函数表示

令 $f_n(k)$ 表示长度为 $n$ 且有 $k$ 个逆序对的排列个数。

生成函数关系：

$$F_n(x) = \prod_{i=1}^{n-1} (1 + x + x^2 + \cdots + x^i) $$

代码中的 mul(i-1) 和 div(i) 就是在操作这个生成函数。

2. 深度贡献分析

节点 $x$ 的深度等于它在排列中作为某个区间最小值的次数。

有两种情况贡献深度：

情况1：$x$ 在右子树中

• 存在 $r > x$，使得区间 $[x, r]$ 中 $x$ 是最小值
• 这会产生 $r-x$ 个额外的逆序对
• 贡献：$\sum_{r=x+1}^n f_{r-x}(k-(r-x))$

情况2：$x$ 在左子树中

• 存在 $l < x$，使得区间 $[l, x]$ 中 $x$ 是最小值
• 不产生额外逆序对（因为左边元素都大于右边）
• 贡献：$\sum_{l=1}^x f_{x-l}(k)$

3. 生成函数操作

• mul(x)：乘以 $\frac{1-x^{x+1}}{1-x}$，对应前缀和操作
• div(x)：除以 $\frac{1-x^{x+1}}{1-x}$，通过差分恢复

复杂度分析

• 时间复杂度：$O(n^4)$
  • 生成函数计算：$O(n^3)$
  • 深度计算：$O(n^3)$
• 空间复杂度：$O(n^3)$

由于 $n \leq 300$，$300^3 = 27,000,000$ 在可接受范围内。

样例解析

样例1：3 0 192603497

唯一排列：$\{1,2,3\}$

• 树结构：1 为根，2 为右子，3 为右子的右子
• 深度：$d_1=1, d_2=2, d_3=3$
• 输出：1 2 3

样例2：3 1 144408983

两个排列：$\{1,3,2\}$ 和 $\{2,1,3\}$

• 排列1：深度 $d_1=1, d_2=3, d_3=2$
• 排列2：深度 $d_1=2, d_2=1, d_3=2$
• 总和：$d_1=3, d_2=4, d_3=4$
• 输出：3 4 4

关键技巧

1. 生成函数技术：用多项式表示逆序对分布
2. 滑动窗口：高效处理生成函数的乘除
3. 深度分解：将深度分解为区间最小值的出现次数
4. 组合计数：精确统计所有满足条件的排列

总结

这道题的解题亮点：

1. 问题转化：将树深度问题转化为排列组合问题
2. 生成函数应用：用多项式方法处理逆序对约束
3. 贡献分析：系统分析每个位置对深度的贡献
4. 高效计算：通过预处理优化重复计算

算法通过深入的组合数学分析，在 $O(n^4)$ 时间内解决了这个复杂的计数问题，展示了生成函数在组合计数中的强大能力。