2026年3月专项训练巩固总结

组合数学特殊数列

卡特兰数

卡特兰数最重要的两个东西：

折线法推导

常见模型

$C_0 = 1, C_ns = \sum_{i=0}^{n - 1}C_i \times C_{n - 1 - i}$

前几项是： $1,1,2,5,14,42...$

其有众多经典的现实模型，我们分两类介绍，下面是第一类：

长度为 $2n$ 的合法括号序列的个数。
从 $(0, 0)$ 走到 $(n, n)$ 的不穿过 $y = x$ 的路径条数。
$n$ 个数，按照顺序入栈，只要不是空栈就随时可以出栈，得到的出栈序列种类数。

这一类强调的是，我们要做 $2n$ 次决策，决策有两种，决策序列的每个前缀中，第一种决策的个数不应该少于第二种决策的个数。

再看一下第二类：

圆周上给你 $2n$ 个点，两两配对连成弦，问有多少种使得弦两两不相交的方案。
凸 $n + 2$ 边形，剖分成 $n$ 个三角形的方案数。
含有 $n$ 个结点的不同的二叉树形态数。

这一类突出的是，我们有一个规模为 $n$ 的问题，通过枚举中间点，能将问题拆成规模为 $i$ 的问题和规模为 $n - 1 - i$ 的问题的乘积的和。

只要一个事情能转化得和这两类中的某类一样，就说明该上卡特兰数了。

卡特兰数的定义式不好算，我们要找一些更好的办法。

我们以 $(0, 0)$ 到 $(n, n)$ 的不穿过 $y = x$ 的路径条数来推导一下，已知所有路径有 $C(2n, n)$ 种，减去穿过的就是不穿过的。我们考虑某个穿过的路径，其肯定和 $y = x + 1$ 有交点，设第一次交点是 $p$ 。我们把 $(0, 0)$ 到 $p$ 的这段路径，以 $y = x + 1$ 为对称轴，对称过去，就能发现变成了一条由 $(-1, 1)$ 到 $(n, n)$ 的路径。容易说明每条从 $(-1, 1)$ 到 $(n, n)$ 的路径，唯一对应一条从 $(0, 0)$ 走到 $(n, n)$ 且穿过了 $y = x$ 的路径，所以非法路径条数其实就是 $C(2n, n + 1)$ ，所以合法路径条数就是 $C(2n, n) - C(2n, n + 1)$ 。

这个式子显然只需要预处理阶乘及其逆元就能算了，比定义式好算多了。

这个推导方法叫做折线法，使用这个办法也能推导出从 $(0, 0)$ 走到 $(n, m)$ ，不穿过 $y = x$ 的路径条数，这个东西叫做广义卡特兰数，结果是 $C(n + m, n) - C(n + m, n + 1)$ ， $n \ge m$ 。

会这个方法，基本上就不愁不会算卡特兰数了，其他的公式可以暂时不管。

第二类斯特林数（集合）

将 $n$ 个互不相同的物品，分到 $k$ 个不可区分的盒子里，每个盒子里必须有东西，且每个盒子里的东西看成一个无序集合，方案数就是第二类斯特林数，设为 $S(n, k)$ 。

容易得到递推公式： $S(n, k) = S(n - 1, k - 1) + k\times S(n - 1, k)$ ，即要么第 $n$ 个物品单独放到一个盒子里，要么插入到某个已有的盒子里。

边界条件 $S(n, 0) = [n = 0]$ 。

第一类斯特林数（圆排列）

将 $n$ 个互不相同的物品，分到 $k$ 个不可区分的盒子里，每个盒子里必须有东西，且每个盒子里的东西看成一个圆排列，方案数就是第一类斯特林数，设为 $s(n, k)$ 。

容易得到递推公式： $s(n, k) = s(n - 1, k - 1) + (n - 1) \times s(n - 1, k)$ ，即要么第 $n$ 个物品单独放到一个盒子里，要么插入到某个盒子里某个数的前面（之前一共插了 $n - 1$ 个数了）。

边界条件 $s(n, 0) = [n = 0]$ 。

拉赫数（线性排列）

将 $n$ 个互不相同的物品，分到 $k$ 个不可区分的盒子里，每个盒子里必须有东西，且每个盒子里的东西看成一个线性排列，方案数设为 $L(n, k)$ 。

仍然考虑递推求解： $L(n, k) = L(n - 1, k - 1) + (n + k - 1) \times L(n - 1, k)$ ，即要么第 $n$ 个物品单独放到一个盒子里，要么就插入到某个已有的排列里，由于可以选择插到每个数的左边，或者插到所有数的右边，所以实际上有 $n - 1 + k$ 个空能插。

边界条件 $L(n, 0) = [n = 0]$ 。

此外，也可以考虑直接求解，对于这 $n$ 个物品的一个确定的排列，直接在 $n - 1$ 个间隔处选 $k - 1$ 个插板，即可得到 $k$ 个线性排列，乘以 $n!$ 再除以掉 $k!$ （即盒子的顺序）也可以得到答案，即 $L(n, k) = \frac{n!}{k!}C(n - 1, k - 1)$ 。

贝尔数

将 $n$ 个互不相同的物品（或者说，包含 $n$ 个元素的集合），划分成若干个非空集合，这些集合互相之间交集为空，全部并起来是全集，方案数就是贝尔数 $B_n$ 。

可以很明显地看出来贝尔数和第二类斯特林数的关系： $B_n = \sum_{k=0}^{n}S(n, k)$ 。

分拆数

对于数 $n$ ，将其拆成若干个递降正整数的和，方案数是多少。

考虑将 $i$ 拆成最大的部分不超过 $j$ 的方案数，设为 $dp[i][j]$ ，则 $dp[i][j] = dp[i][j - 1] + dp[i - j][j]$ 。

分拆数之所以说是拆成若干递降正整数的和，是因为这个问题我们一般不关心顺序。

如果关心拆出来的数的顺序，那么其实就是 $2^{n - 1}$ 的隔板法，不要想复杂了。

树上背包

我们直接看代码：

int n, p;
vector<vector<int>> e;
vector<vector<int>> dp;
vector<int> sz;

void dfs(int u) {
    dp[u][1] = 0;
    sz[u] = 1;
    vector<int> tmp(n + 1, INF);

    for (auto v : e[u]) {
        dfs(v);
        for (int j = 0; j <= p; j++) {
            tmp[j] = INF;
        }

        // 注意遍历上限，不能无脑是 n 或者 p，因为连通块本来就没那么大
        for (int j = 0; j <= sz[u]; j++) {
            for (int k = 0; k <= sz[v]; k++) {
                tmp[j + k] = min(tmp[j + k], dp[u][j] + dp[v][k]);
            }
            tmp[j] = min(tmp[j], dp[u][j] + 1);
        }

        for (int j = 0; j <= p; j++) {
            dp[u][j] = tmp[j];
        }
        // DP 算完一个子树后，再把这个子树的 size 更新过来
        sz[u] += sz[v];
    }
}

我想说的是，树上背包的复杂度经常实现错误，如果想实现对的话，需要边 dfs 边维护 size， DP 更新时只把这部分 size 的容量进行更新，这样才能保证树上的两个节点只在 LCA 处被合并一次，复杂度才是平方级别。

矩阵快速幂

矩阵快速幂，之所以能把一个矩阵的 $n$ 次方，拆成 $2$ 的若干次幂相乘，核心在于矩阵乘法有结合律，所以矩阵的 $n$ 次方可以随便结合，二进制只是比较方便实现的一种方式。

我们考虑广义的情况，考虑 ABC445F 这道题，这里也使用了类似矩阵快速幂或者倍增的方式。

这种“组装”能成功的数学前提是：这种运算满足结合律。即：

(A \otimes B) \otimes C = A \otimes (B \otimes C)

让我们推导一下 $(\min, +)$ 矩阵乘法中，第 $(i, j)$ 个元素的计算式：

$(A \otimes B)_{i,j} = \min_{p} \{ A_{i,p} + B_{p,j} \}$

当我们计算 $(A \otimes B) \otimes C$ 时：

((A \otimes B) \otimes C)_{i,j} = \min_{q} \{ (\min_{p} \{ A_{i,p} + B_{p,q} \}) + C_{q,j} \}

由于 $\min$ 运算可以外提（分配律）：

= \min_{q} \{ \min_{p} \{ A_{i,p} + B_{p,q} + C_{q,j} \} \} = \min_{p, q} \{ A_{i,p} + B_{p,q} + C_{q,j} \}

同理，计算 $A \otimes (B \otimes C)$ 得到的结果也是 $\min_{p, q} \{ A_{i,p} + B_{p,q} + C_{q,j} \}$ 。

既然满足结合律，那么 $C^{11}$ 既可以写成 $(((C^1 \cdot C^1) \cdot C^1) \dots)$ ，也可以写成 $(C^8 \cdot C^2 \cdot C^1)$ 。二进制拆分只不过是结合律的一种高效利用方案。

因此，这个题我们可以预处理走 $2^k$ 步的答案，用 $2^k$ 的答案能拼出 $2^{k + 1}$ 的答案，以及可以二进制拆分拼出恰好 $n$ 步的答案。

曼哈顿距离与莫队

莫队算法，本质上是想找一种回答若干个 $[l_i, r_i]$ 的询问的顺序，使得指针总移动量尽可能小。

在空间上，相当于有若干个点，坐标为 $(l_i, r_i)$ ，要找一条哈密顿路径，使得路径上相邻点的曼哈顿距离之和尽可能小。这就是莫队算法的几何意义。

ABC448F 使用了莫队算法的几何意义进行命题。

既然说到了莫队，不妨再分析一遍莫队的时间复杂度。

假设块长为 $B$ ，有 $Q$ 次询问，序列长度是 $N$ 。

对于询问，我们按照左端点所在块编号为第一关键字升序，同一个块内按照右端点升序排序。

对于相邻的两个询问，假如他们是同一个块内的，则左端点至多移动 $B$ ，如果不是同一个块里的，则左端点也至多移动 $2B$ 。右端点单独分析相邻两个移动量没意义，但在同一个块内的询问右端点总共移动 $N$ 。一共有 $\frac{N}{B}$ 块，所以左端点的总移动量是 $O(QB)$ 级别，右端点的总移动量是 $O(\frac{N^2}{B})$ 级别，所以总共就是 $O(QB + \frac{N^2}{B})$ ，如果忽略常数，利用基本不等式，当 $QB = \frac{N^2}{B}$ ，即 $B = \frac{N}{\sqrt{Q}}$ 时，能让这个东西取到最小值。

在上面这道题中， $N = 2 \times 10^7$ ， $Q = 6 \times 10^4$ ，所以 $B$ 大约是 $81649$ 最好。

由于右端点目前是一律按照块内升序排序的，这会导致从一个块变到另一个块时，右端点需要先移动左边，再重新移动回右边。如果按照奇数块右端点升序，偶数块右端点降序排序，则可以少走一趟冤枉路。这个就是奇偶块优化。

因此，我们按照这个思路对所有点进行排序，然后找到 $1$ 号点，先把 $1$ 号点右边的都走了，再走 $1$ 号点左边的，就可以了。

struct Node {
    int x, y, id, block_id;

    bool operator<(const Node &o) const {
        if (block_id == o.block_id) {
            if (block_id % 2 == 0) {
                return y > o.y;
            } else {
                return y < o.y;
            }
        }
        return block_id < o.block_id;
    }
};

void solve() {
    LL n;
    cin >> n;
    vector<Node> nodes(n);
    for (int i = 0; i < n; i++) {
        cin >> nodes[i].x >> nodes[i].y;
        nodes[i].id = i + 1;
    }
    
    LL B = 81649;
    for (int i = 0; i < n; i++) {
        nodes[i].block_id = nodes[i].x / B + 1;
    }

    sort(nodes.begin(), nodes.end());

    int one_pos = -1;
    for (int i = 0; i < n; i++) {
        if (nodes[i].id == 1) {
            one_pos = i;
            break;
        }
    }

    for (int i = one_pos; i < n; i++) {
        cout << nodes[i].id << " ";
    }
    for (int i = 0; i < one_pos; i++) {
        cout << nodes[i].id << " ";
    }
}

GCD计数容斥/倍数容斥

我们定义两个状态：

$F(g)$ ： $\gcd$ 是 $g$ 的倍数的满足条件的结构（子序列、元组之类的）的个数（这个很好算，直接通过统计数组中 $g$ 的倍数个数 $cnt[g]$ ，然后简单计算可以得到）。
$f(g)$ ： $\gcd$ 恰好是 $g$ 的结构个数（这是我们要的结果）。

显然， $F(g)$ 比 $f(g)$ 更容易求。

二者的关系是：

F(g) = f(g) + f(2g) + f(3g) + f(4g) + \dots

变形一下，求 $f(g)$ 的公式就是：

f(g) = F(g) - \sum_{k=2, 3, \dots} f(kg)

观察这个公式：

为了算出 $f(g)$ ，你必须先知道 $f(2g), f(3g), f(4g) \dots$ 。这些项全都是比 $g$ 大的数。

所以为了算这个东西，你需要从大到小枚举 $g$ 去做容斥。

诈骗题

结论与等价变换类

这类题目给出一个复杂的动态过程，诱导你写模拟、搜索或高精数据结构，但核心逻辑可以被一行代码取代。

典型案例：[P1007 独木桥]（相遇转身 $\rightarrow$ 擦肩而过）、[CF1951E 回文切分]（复杂切分 $\rightarrow$ 证明只需检查 $k=2$ ）。
武器库逻辑：
- 对称抵消：如果两个个体完全相同，其相互作用的状态改变可以视为互换，从而忽略物理碰撞。
- 答案范围极小：如果一个复杂目标在 $99\%$ 的随机数据下都能由极简方案解决，那么任务就变成了寻找剩下的 $1\%$ 极端情况。

复杂度与势能分析类

这类题目通过数学性质保证了看似 $O(N^2)$ 的暴力其实是 $O(N \log N)$ 甚至更低。

典型案例：[调和级数枚举]（枚举倍数）、[Segment Tree Beats]（区间取模/开根号）、[ODT/珂朵莉树]（区间覆盖）。
武器库逻辑：
- 总量有限性：一个数值（势能）被“削减”是有上限的（例如 $10^{18}$ 只能被开根号 6 次，或被取模 $\log$ 次）。只要保证**“无效操作不递归，有效操作必削减”**，暴力就是最优解。
- 调和级数： $\sum_{i=1}^n \frac{n}{i} \approx n \ln n$ 。在 $10^6$ 级别下，枚举约数/倍数是安全的。

数学性质与剪枝类

利用乘法增长远快于加法，或者特定的数论定理，强制缩减搜索空间。

典型案例：[P8912 ijk]（乘积 vs 加和）、[P5535 小道消息]（伯特兰定理）。
武器库逻辑：
- 三维乘积约束：在 $10^6$ 范围内，三个数的乘积只要稍大，变量就会被迅速压制到 $1$ 或极小范围。
- 根号分布 $\sqrt{N}$ ：若 $\sum a_i = N$ ，则不同的 $a_i$ 种类只有 $O(\sqrt{N})$ 个。利用这一点可以将多重背包、组合计数等问题从 $O(N^2)$ 优化到 $O(N\sqrt{N})$ 。

随机化与哈希类

对于那些难以维护的动态集合属性，利用随机权值将其转化为数值特征，实现 $O(1)$ 校验。

典型案例：[CSP-S 2022 星战]（动态出度校验 $\rightarrow$ 随机权值和哈希）。
武器库逻辑：
- 异或/和哈希：给每个点/边分配一个 unsigned long long 随机值。判断“集合相等”、“每个元素出现一次”等结构化问题，只需判断哈希值之和是否符合预期。
- 错误率控制：双哈希可以使冲突概率降至 $10^{-18}$ 以下，在竞赛环境下视为绝对安全。

2026年3月专项训练巩固总结

2026年3月专项训练巩固总结

组合数学特殊数列

卡特兰数

第二类斯特林数（集合）

第一类斯特林数（圆排列）

拉赫数（线性排列）

贝尔数

分拆数

树上背包

矩阵快速幂

曼哈顿距离与莫队

GCD计数容斥/倍数容斥

诈骗题

结论与等价变换类

复杂度与势能分析类

数学性质与剪枝类

随机化与哈希类

连续段DP

mex问题

思维题

感谢您的支持，我会继续努力的!