📖 第 2.9 章：倍增与构造

2.9.0 从两道题出发

先看两道题——它们代表了本章的两大主题。

📋 题目 1：巨蟒跳格 有一条 N 格的线，棋子从第 1 格出发，每次可以向前跳 1、2、4、8、… 格——也就是恰好 2 的幂次方格（不能超出第 N 格）。 问：最少跳几次能恰好到达第 N 格？ 数据范围： 1 ≤ N ≤ 10^18。

📋 题目 2：构造回文 给你一个由小写字母组成的字符串 s（长度 n ≤ 10^6）。 请你重排其中的字母，输出一个是回文的字符串；如果有多种方案，输出任意一种。如果无论怎么重排都无法构成回文，输出 NO SOLUTION。

两道题，两种思想

巨蟒跳格：N 最大到 10^18，一步步模拟肯定不行。但「每次跳 2 的幂」这个条件暗示了答案与 N - 1 的二进制表示有关——最少步数就是「能凑出 N - 1 的最少几个 2 的幂」。这正是倍增思想的入口：用 2 的幂组合出任意数量。

构造回文：题目不是问你「最优值是多少」，而是要你亲手交出一个合法方案。答案是「构造」出来的，不是「搜索」出来的。你需要先想清楚「回文什么时候存在」（判定），再设计「怎么摆」（构造）。

这一章是全书的「思想总纲」：

1. 倍增——你在很多后续章节会反复遇到它（快速幂、LCA、函数图跳步……），这里先把统一的思想讲透；
2. 构造——竞赛中独立的一类题型，这里建立基本方法论，深入版见 Ad Hoc 一章。

拆解本章需要回答的问题

学习目标（学完本章你将能够）：

1. 说出倍增适用的两个条件（可组合 + 结合律），并据此判断一道题能否倍增
2. 用一张「统一视角表」把快速幂、LCA、函数图跳步等应用归到同一框架下
3. 手写「跳 k 步」的倍增数组 f[j][x]，并用二进制分解完成查询
4. 掌握构造题的三大入手思路：从特殊到一般、从下界反推、逐步交换
5. 养成「构造完用小数据暴力验证」的习惯（衔接 2.8 的枚举×模拟）

2.9.1 倍增（Doubling）

核心洞察：任何正整数都是若干 2 的幂之和

这是一个看似简单却威力巨大的事实：

13 = 8 + 4 + 1      = 2^3 + 2^2 + 2^0
5  = 4 + 1          = 2^2 + 2^0
10^18 ≈ 2^59.79     —— 最多 60 个 2 的幂就够了

换成算法语言：「走 k 步」可以拆成「走若干段，每段长度是 2 的幂」。比如「走 13 步」=「走 8 步 + 走 4 步 + 走 1 步」。

于是，如果一个问题满足两个条件：

1. 可组合：「走 2^i 步」的结果能由「走 2^(i-1) 步」的结果算出来；
2. 结合律：分段走的顺序拼接后效果与连走相同（或者说「走 a 步再走 b 步 = 走 a+b 步」）；

那么只需要预处理出所有 2 的幂长度的「一步到位」信息（共 O(log k) 个），查询时按 k 的二进制分解拼起来，就能把 O(k) 的过程压缩到 O(log k)。

💡 一个直观比喻：你要坐地铁从 A 到 E 站。与其一站一站数，不如记住「从任何一站坐 1 站到哪、坐 2 站到哪、坐 4 站到哪……」。要坐 13 站？= 坐 8 站 + 坐 4 站 + 坐 1 站，查三次表就到。

统一视角：全书中的倍增应用

倍增在本书出现了很多次，长相各不相同，但骨架完全一样。请对照下表体会「同一思想、不同化身」：

它们的共同骨架是：

预处理：f[j][·] 由 f[j-1][·] 复合一次得到      // "跳 2^j 步 = 跳两次 2^(j-1) 步"
查询：  把 k 写成二进制，按位拼接               // "走 k 步 = 走若干段 2 的幂"

本章不重复各章的实现细节，只在下面用「跳 k 步」这个最纯粹的版本完整实战一遍——学会了它，其他版本只是换了个「步」的含义。

完整实战一：巨蟒跳格

回到开篇题目。从第 1 格到第 N 格，需要向前跨越的距离是 d = N - 1。每次跳的格数是 2 的幂，问最少几次。

关键转化：每次跳跃的长度是 2 的幂，而任何正整数 d 都能写成若干不同的 2 的幂之和（这正是二进制表示！）。那么最少步数是多少？

• 一种跳法对应一个「2 的幂的多重集」，其和为 d；
• 如果允许重复（比如 8+1+1 凑 10），步数只会更多；
• 二进制表示给出了一种「每个幂最多用一次」的方案，它用的幂的个数 = d 的二进制中 1 的个数，这已经是最少的——因为 k 个 2 的幂（允许重复）相加，和的二进制中 1 的个数不会超过 k（每合并两个相同的 2^i 就进位成一个 2^(i+1)，个数不减、位数不增）。

结论：最少步数 = d = N - 1 的二进制表示中 1 的个数。

验证一下 N = 10：d = 9 = 8 + 1，二进制 1001，1 的个数为 2。也就是跳 8 格再跳 1 格（1 → 9 → 10），共 2 步。而「8+1+1」需要 3 步，不是最优。手算核对：✅。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long d = n - 1;              // 需要跨越的总距离
    int steps = 0;
    for (long long p = 1; p <= d; p <<= 1)   // 从小幂到大幂逐一检查
        if (d & p) steps++;
    cout << steps << "\n";
    return 0;
}

N = 10 输出 2；N = 10^18 时 d 约需 60 位二进制，循环也只有 60 次——O(log N)，再大的 N 也不怕。

🤔 为什么不叫「DP」？ 这里「贪心地从大幂到小幂凑」之所以对，是因为二进制表示的唯一性——每一步选择都是被迫的、无后悔的。识别「这道题其实是二进制」是本题真正的考点。

完整实战二：跳 k 步的倍增数组 f[j][x]

巨蟒跳格里「一步跳多远」由我们自己选。更一般的问题是：每步的走法是固定的（由题目给定的函数决定），要跳指定的 k 步。

设有一个函数图：n 个节点 1..n，每个节点 x 恰好一条出边指向 f(x)。问从 x 出发走 k 步到哪个节点（即求 f^k(x)，函数的 k 次复合）。k 可以大到 10^9，一步步走太慢。

倍增做法：定义 f[j][x] = 从 x 出发走 2^j 步后所在的节点。则：

f[0][x] = f(x)                        // 走 1 步（题目给定）
f[j][x] = f[j-1][ f[j-1][x] ]         // 走 2^j 步 = 先走 2^(j-1) 步，再走 2^(j-1) 步

查询时把 k 按二进制分解，每一位是 1 就跳一次：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 6;                                  // 节点 1..6
    int nxt[7] = {0, 3, 1, 5, 2, 6, 3};         // 1->3, 2->1, 3->5, 4->2, 5->6, 6->3
    const int LOG = 3;                          // 2^2=4 < 5 步 ≤ 2^3=8，够用
    static int f[LOG][7];
    for (int x = 1; x <= n; x++) f[0][x] = nxt[x];
    for (int j = 1; j < LOG; j++)
        for (int x = 1; x <= n; x++)
            f[j][x] = f[j - 1][f[j - 1][x]];

    int x = 1, k = 5;                           // 查询：从 1 出发走 5 步
    for (int j = 0; k; j++, k >>= 1)            // k=5=101₂：跳 1 步，再跳 4 步
        if (k & 1) x = f[j][x];
    cout << "f^5(1) = " << x << "\n";
    return 0;
}

运行输出 f^5(1) = 5。手算核对：1 → 3 → 5 → 6 → 3 → 5，第 5 步确实到 5。✅

逐层看这个数组（建议在纸上自己推一遍）：

查询 k = 5 = 101₂ 时：第 0 位是 1 → x = f[0][1] = 3；第 2 位是 1 → x = f[2][3] = 5。两次跳表，代替五次模拟。

💡 什么时候用倍增？ 检查两个条件：①「一步」可不可以复合（走两段 2^(j-1) 步 = 走 2^j 步）；②复合是否满足结合律（先走 a 再走 b = 走 a+b）。树上的祖先关系、函数图的复合、矩阵乘法、取模乘法都满足。不满足的典型例子：带「途中不能经过某点」这类约束的路径，因为两段拼起来可能在中途违规——这时不能直接倍增。

🔗 延伸阅读：这个模型的完整竞赛版（含环、k ≤ 10^9、判「最近公共后继」等）见函数图与基环树 5.3.3；树上版本（up[j][v] 找祖先、求 LCA）见二叉树与树 5.5.8；乘法版本（快速幂）见数论基础 8.1.2。

2.9.2 构造（Constructive）

构造题长什么样

大多数题问「最优值是多少」或「有多少种方案」，构造题问的是：

• 「给出一组任意合法方案」——不要求最优，只要求合法；
• 「能否做到？若能，输出方案」——判定与构造二合一；
• 「构造一个满足某某性质的 X」——性质千奇百怪，但都要你亲手造出来。

构造题的难点在于：没有固定算法可套，每题像一道谜题。但也有章法可循——下面三条思路覆盖了大部分入手方向。

构造三思路

思路一：从特殊到一般。 先在纸上摆小样例（N=3、N=4 时手动画一画），找规律，再猜一般公式，最后证明或用暴力验证。绝大多数构造题的第一步都是画小样例——不画直接想，等于闭眼走路。

思路二：从下界反推。 如果题目隐含一个「不可能比 X 更好」的下界，而你能构造出恰好达到 X 的方案，那它就是最优的（这也是「证明最优」的标准姿势）。这一思路的系统讲解见Ad Hoc 题 7.3.5「下界 + 构造」。

思路三：逐步交换。 从一个显然合法但可能不满足额外要求的初始方案出发，每次用一个保持合法性的局部交换把它往目标推进（比如排序算法就是靠不断交换逆序对把任意排列变成有序排列）。交换的正当性需要交换论证支撑，深入内容见 Ad Hoc 7.3.9。

完整实战一：构造回文（思路：判定 + 直接摆放）

第一步——判定什么时候有解。 回文从左往右读和从右往左读相同，意味着除正中间的一个位置外，字母必须成对出现（第 i 位和倒数第 i 位相同）。所以：

• 统计 26 个字母的出现次数，出现奇数次的字母最多只能有 1 个（它独占正中间）；
• 奇数次的字母 ≥ 2 个 → NO SOLUTION。

第二步——构造。 把每个字母的一半从左到右摆好，中间放那个奇数字母（若有），右半镜像。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int cnt[26] = {0};
    for (char c : s) cnt[c - 'a']++;

    int odd = 0;                       // 出现奇数次的字母个数
    for (int i = 0; i < 26; i++)
        if (cnt[i] % 2 == 1) odd++;
    if (odd > 1) {
        cout << "NO SOLUTION\n";
        return 0;
    }

    string half = "", mid = "";
    for (int i = 0; i < 26; i++) {
        half += string(cnt[i] / 2, char('a' + i));   // 每个字母取一半
        if (cnt[i] % 2 == 1) mid = char('a' + i);    // 奇数字母放中间
    }
    string rev = half;
    reverse(rev.begin(), rev.end());
    cout << half + mid + rev << "\n";
    return 0;
}

样例核对：aabbb → 计数 a:2, b:3，奇数字母只有 b，half = "ab"，mid = "b"，输出 abbba。验证：abbba 反转还是 abbba，是回文，且用的字母与输入完全一致。✅

abc → a:1, b:1, c:1，奇数字母 3 个 > 1 → NO SOLUTION。✅

注意两个工程细节：判定在前、构造在后（无解时不进入构造代码），以及 10^6 的长度用 std::string 拼接依然高效。

完整实战二：构造排列（思路：从特殊到一般 + 找规律）

📋 题目：美丽的排列 构造 1..N 的一个排列 p，使得任意相邻两个数的差的绝对值 ≥ 2。若不存在这样的排列，输出 NO SOLUTION。 1 ≤ N ≤ 10^6。

第一步——画小样例（思路一）。

• N = 2：只有 1 2 和 2 1，差都是 1 → 无解；
• N = 3：排列如 1 3 2，|1-3|=2 但 |3-2|=1；枚举所有 6 个排列都有一条相邻差为 1 → 无解；
• N = 4：2 4 1 3 → 差依次为 2, 3, 2 ✅；
• N = 5：在 N=4 的方案后面接 5？|3-5|=2 ✅，得 2 4 1 3 5。

第二步——归纳规律。 「差为 1」只发生在相邻整数之间。如果把所有偶数排在前面、所有奇数排在后面：

• 偶数段内部：2, 4, 6, …，相邻差为 2 ✅；
• 奇数段内部：…, 5, 3, 1，相邻差为 2 ✅；
• 衔接处：最小的偶数 2 和最大的奇数 N-1（或反过来）差远大于 2 ✅。

偶数和奇数永不相邻产生差 1，而段内相邻差恰为 2——整个构造只有一种相邻关系需要检查（衔接处），其余由「隔一个数」天然保证。

第三步——小 N 的无解证明。 N = 2, 3 时无解：N=2 显然；N=3 时 2 必须夹在 1 和 3 之间以外的位置，但排列只有 3 个位置，1 和 3 必有一个与 2 相邻，差为 1。用 2.8 章的枚举（next_permutation）跑一遍也能确认。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n == 1) { cout << 1 << "\n"; return 0; }
    if (n <= 3) { cout << "NO SOLUTION\n"; return 0; }
    for (int i = 2; i <= n; i += 2) cout << i << " ";   // 先输出所有偶数
    for (int i = 1; i <= n; i += 2) cout << i << " ";   // 再输出所有奇数
    cout << "\n";
    return 0;
}

样例：N=6 → 2 4 6 1 3 5，差依次为 2 2 5 2 2，全部 ≥ 2。✅

构造题的检验：写完用小数据暴力验证

构造题的答案不唯一，评测用 special judge 检查合法性，所以你最大的风险是构造出非法方案而不自知。标准保险动作（衔接 2.8 章的「枚举 × 模拟」）：

1. 写一个 check() 函数，模拟检验方案是否满足题目全部性质；
2. 对 N = 1 到 10 的小数据，把构造输出喂给 check()；无解判断用 next_permutation 枚举全部方案对照。

// 以美丽的排列为例的验证器
bool check(const vector<int>& p) {
    for (size_t i = 0; i + 1 < p.size(); i++)
        if (abs(p[i] - p[i + 1]) < 2) return false;
    return true;
}

用暴力枚举对拍 N ≤ 9 的所有情形：N=2, 3 确认无解，N ≥ 4 全部通过 check()——构造的正确性就不是「我觉得对」，而是「机器证明对」。这个习惯在考场上值一道题的分数。

⚠️ 常见错误

倍增类：

1. 数组维度顺序写反：f[j][x] 的第一维是层数（2^j），第二维才是节点。写成 f[x][j] 后，f[j-1][f[j-1][x]] 这类复合就会查错内存——症状是答案偶尔对偶尔错，极难排查。建议统一背下模板 f[j][x]。
2. LOG 开小了：k ≤ 10^9 需要 LOG = 30（2^30 > 10^9），k ≤ 10^18 需要 60。少开一位，大 k 直接越界或漏跳。反过来 LOG 开太大也浪费内存：f 数组大小是 LOG × N。
3. 预处理边界：j 从 1 开始循环（j=0 是题给的一步转移），且 2^j 不能超过 k 的上界。跳 LCA 时「先到同深度再一起跳」两阶段的顺序也不能反。

构造类：

4. 忘记判无解：先判定、后构造。很多选手写完构造直接输出，忘了题目里「若不可能则输出 NO SOLUTION」——有解判定（如回文的奇偶性检查）必须写在构造之前。
5. 构造完不验证：交之前用小数据跑一遍 check()。构造代码改动频繁，一处 off-by-one 可能让「任意合法方案」变成「非法方案」，而编译器和样例都不一定能发现。
6. 把「任意方案」做成「最优方案」：构造题只要合法就行。为了「更漂亮」的输出去加复杂逻辑，只会引入新 bug——KISS（Keep It Simple）。

📝 本章总结

🏋️ 练习题

🟢 简单：巨蟒跳格·改 从第 1 格出发，每次可跳 1、2、4、… 格（2 的幂），问恰好跳到第 N 格的方案数是多少？只需输出方案数模 10^9+7。（提示：N ≤ 10^6，想一想「每个 2 的幂用任意多次」时的递推——f[d] = f[d-1] + f[d-2] + f[d-4] + …，用后缀和优化到 O(N log N)。）

🟡 中等：走 k 步 给定 n 个节点的函数图（每点恰一条出边）与 q 次查询，每次问「从 x 走 k 步到哪」，k ≤ 10^9。（直接使用本章 2.9.1 的 f[j][x] 模板，注意 LOG=30。完整竞赛版见函数图与基环树 5.3.3。）

🔴 较难：回文重排·计数版 给定字符串 s，问有多少种本质不同的重排是回文（模 10^9+7）。（提示：若能构成回文，答案 = 多重集合排列数 (L/2)! / ∏(c_i/2)!，乘法逆元见数论基础 8.1.3。先判定，再计数。）

下一章预告：第三部分将进入数据结构的世界——从数组与前缀和开始，你会看到「预处理 + 查询」这对思想的更多化身。