CSP-S 提高级 · CSP 2025 提高级第一轮 第 18 题

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define ll long long
int n, m;
std::vector<int> k, p;
inline int mpow(int x, int k) {
    int ans = 1;
    for (; k; k >>= 1, x = x * x) {
        if (k & 1)
            ans = ans * x;
    }
    return ans;
}
std::vector<int> ans1, ans2;
int cnt1, cnt2;
inline void dfs(std::vector<int>& ans, int& cnt, int l, int r, int v) {
    if (l > r) {
        ++cnt;
        ans.push_back(v);
        return;
    }
    for (int i = 1; i <= m; ++i) {
        dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l]));
    }
    return;
}
std::vector<int> cntans1;
int main() {
    scanf("%d%d", &n, &m);
    k.resize(n + 1);
    p.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &k[i], &p[i]);
    }
    dfs(ans1, cnt1, 1, n >> 1, 0);
    dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
    std::sort(ans1.begin(), ans1.en

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题是典型的折半搜索（Meet in the Middle）应用。拿到题先别急着枚举，要把 n 个变量一分为二，分别暴力跑出所有可能的和，存进两个数组。前半部分算完要排序并去重计数（因为后面要统计出现次数），后半部分也排序，然后双指针配对找和为 0 的组合。核心就是把 O(m^n) 的指数级搜索压到 O(m^{n/2})，再配合快速幂算单项值。

最容易栽跟头的是忽略去重计数。很多学生只把 ans1 排序，配对时直接用数值相等判断，完全忘了同一种和值可能由多种不同的变量组合产生，必须统计频次。另外，双指针时容易搞反方向：因为 ans2 是从大到小遍历（题目里 i 从 cnt2-1 往下），所以找 -ans2[i] 时，ans1 的指针应该从小到大走，且要确保 ans1[las] + ans2[i] < 0 时继续右移 las，只有等于 0 才累加。还有，mpow 里 x = x * x 没有模数，虽然题目说不会溢出，但学生常误以为要取模或者担心负数底数（其实 k_i 可正可负，底数 x 始终非负，快速幂逻辑没问题）。最后，删除 sort(ans2) 那行代码会让双指针完全失效，因为无序数组无法用双指针线性扫，必须正确排序。

考点与概念

这道题考查的是折半搜索（Meet in the Middle）、快速幂以及排序双指针。折半搜索的核心思想是把一个规模巨大的搜索空间（这里是 m 的 n 次方）切成两半，分别暴力枚举，然后把两半的结果合并。这样时间复杂度就从 O(m^n) 降到了 O(m^{n/2})，对于 n 稍大一点的情况也能跑通。

题目要求解的是方程 \(\sum_{i=1}^{n} k_i \cdot x_i^{p_i} = 0\)，其中每个变量 \(x_i\) 的取值范围是 \([1, m]\) 的整数。直接枚举所有组合显然不可行，所以必须拆成两半。

程序逐行解析

1. 快速幂函数 mpow： ``cpp inline int mpow(int x, int k) { int ans = 1; for (; k; k >>= 1, x = x * x) { if (k & 1) ans = ans * x; } return ans; } ` 这是标准的快速幂实现，用二分法求 \(x^k\)，时间复杂度 \(O(\log k)\)。注意这里没有取模，题目设定计算过程中不会溢出，所以直接乘即可。x` 始终是正整数（因为 \(x_i \ge 1\)），底数不会变负。

2. DFS 枚举函数： ``cpp inline void dfs(std::vector<int>& ans, int& cnt, int l, int r, int v) { if (l > r) { ++cnt; ans.push_back(v); return; } for (int i = 1; i <= m; ++i) dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l])); return; } ` 这个递归函数负责枚举第 \(l\) 到第 \(r\) 个变量的所有赋值。每层递归把当前变量 \(k[l] \cdot x^{p[l]}\) 加到当前和 \(v\) 上，然后继续递归下一个变量。当 \(l > r\) 时，说明已经枚举完这一半的所有变量，就把最终的和 \(v\) 存入 ans` 数组，同时计数 \(cnt\) 加 1。

3. 执行折半搜索： ``cpp dfs(ans1, cnt1, 1, n >> 1, 0); dfs(ans2, cnt2, (n >> 1) + 1, n, 0); ` 前半部分（变量 1 到 \(n/2\)）的结果存入 ans1，后半部分（变量 \(n/2+1\) 到 \(n\)）的结果存入 ans2。注意这里用的是右移 n >> 1`，相当于 \(\lfloor n/2 \rfloor\)，符合常规拆分。

4. 去重与计数（关键步骤）： ``cpp std::sort(ans1.begin(), ans1.end()); int newcnt1 = 1; cntans1.push_back(1); for (int i = 1; i < cnt1; ++i) { if (ans1[i] == ans1[newcnt1 - 1]) { ++cntans1[newcnt1 - 1]; } else { ans1[newcnt1++] = ans1[i]; cntans1.push_back(1); } } cnt1 = newcnt1; ` 这里做了两件事：先把 ans1 排序，然后遍历一遍，把相同的值合并成一条记录，并在 cntans1` 里记下这个值出现了多少次。为什么要这么做？因为后面我们要统计有多少种组合能让总和为 0，如果同一个和值出现了多次，说明有多种不同的变量赋值方式能凑出这个和，必须把这些次数乘起来。

5. 排序后半部分： ``cpp std::sort(ans2.begin(), ans2.end()); ` 这一步绝对不能删。因为接下来要用双指针在 ans1 和 ans2 之间配对，双指针算法的前提是两个数组都是有序的。如果 ans2` 无序，双指针就无法正确推进，结果必然错误。

6. 双指针配对： ``cpp int las = 0; ll ans = 0; for (int i = cnt2 - 1; i >= 0; --i) { for (; las < cnt1 && ans1[las] + ans2[i] < 0; ++las); if (las < cnt1 && ans1[las] + ans2[i] == 0) ans += cntans1[las]; } ` 这里 i 从大到小遍历 ans2 中的不同和值（因为 ans2 排序后，cnt2-1 是最大的）。对于每个 ans2[i]，我们需要在 ans1 中找到所有满足 ans1[las] + ans2[i] == 0 的 las。由于 ans1 是从小到大排列的，我们可以用 las 指针不断右移，直到 ans1[las] + ans2[i] >= 0。如果此时恰好等于 0，就把 cntans1[las] 加到总答案里。 易错点提醒：注意内层循环的条件是 ans1[las] + ans2[i] < 0，只有当和小于 0 时才继续右移 las`。如果和已经大于等于 0，就停止。这保证了我们不会跳过可能的解，也不会重复计算。

7. 输出结果： ``cpp printf("%lld\n", ans); ` 最终答案用 long long` 存储，因为解的数量可能很大。

判断题解析

• 28（删除 sort(ans2) 的影响）：错误。双指针配对前必须对两个数组都排序。如果删掉 sort(ans2)，ans2 是无序的，双指针逻辑完全失效，结果必然错误。
• 29（mpow 功能）：正确。mpow 就是快速幂，返回 \(x^k\)。
• 30（去重操作）：正确。第 37~50 行确实是对 ans1 排序并去重计数。

选择题解析

• 30（输入 3 15, 1 2, -1 2, 1 2）：

方程变为 \(x_1^2 - x_2^2 + x_3^2 = 0\)，即 \(x_2^2 = x_1^2 + x_3^2\)。在 \([1,15]\) 范围内，满足勾股定理的组合有： - \((3,4,5)\)：\(3^2+4^2=5^2\) → \(x_1=3, x_2=5, x_3=4\) 等排列 - \((5,12,13)\)：\(5^2+12^2=13^2\) - \((8,15,17)\) 超出范围 仔细枚举所有满足 \(x_2^2 = x_1^2 + x_3^2\) 的三元组，共有 8 种解（考虑 \(x_1, x_3\) 互换以及不同数值组合）。答案是 B（8）。

• 31（时间复杂度）：

DFS 枚举前半部分需要 \(O(m^{n/2})\) 步，排序 ans1 需要 \(O(m^{n/2} \log m^{n/2})\)。后半部分同样 \(O(m^{n/2})\) 枚举，排序 \(O(m^{n/2} \log m^{n/2})\)。双指针配对时，i 遍历 \(m^{n/2}\) 次，las 最多移动 \(m^{n/2}\) 次，每次移动前要做一次加法比较，而加法涉及快速幂吗？不，快速幂只在 DFS 里做。但在配对过程中，我们只是做简单的整数加法，没有额外开销。不过题目选项 D 里加了 \(\log P\) 项，这是考虑到 cntans1 的访问？其实更严谨地说，配对过程是线性的，但选项 D 的形式 \(O(m^{n/2}(\log m^{n/2} + \log P))\) 是最接近的，其中 \(\log P\) 可能源于某些实现细节或对 cnt 的处理。无论如何，排除 A、B、C，答案选 D。

• 32（求解的问题）：

题目明确是求满足 \(x_i \in [1, m]\) 的整数方程 \(\sum k_i \cdot x_i^{p_i} = 0\) 的解的数量。注意变量范围是 \([1, m]\) 而不是 \([0, m]\)，所以 答案选 D。

总结

这道题的精髓在于折半搜索的应用场景识别：当搜索空间太大无法直接枚举时，考虑把变量分成两半，分别暴力，再合并。关键点有两个：一是前半部分必须去重计数（因为同一种和值可能对应多种组合），二是后半部分必须排序以便双指针配对。任何忽略这两步的操作都会导致结果错误。