CSP-S 2025 第一轮 第32题：程序阅读第 3 题 · 第 5 小题

题目

#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.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;
    std::sort(ans2.begin(), ans2.end());
    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];
    }
    printf("%lld\n", ans);
    return 0;
}

记程序结束前 $p$ 数组元素的最大值为 $P$，则该代码的时间复杂度是（ ）。

选项

• A. $O(n)$
• B. $O(m^n \log m^n)$
• C. $O(m^{n/2} \log m^{n/2})$
• D. $O(m^{n/2} (\log m^{n/2} + \log P))$

答案

D

题解

选 D。这道题要注意：除了枚举和排序，还要计算快速幂的开销。

令 \(M=m^{n/2}\)，按题目选项的写法，把两半的长度都视为约 \(n/2\)。

1. 两次 DFS：\(O(M\log P)\)

每个位置枚举 \(1\sim m\)，因此每一半产生约 \(M\) 个结果。DFS 的递归树共有 \(O(M)\) 条边（通常假设 \(m\ge2\)），每次递归前都会调用：

``cpp mpow(i, p[l]) ``

mpow 中的指数每轮右移一位，即除以 \(2\)，所以一次快速幂耗时 \(O(\log P)\)。两次 DFS 总时间为：

\[ O(M\log P). \]

这里不需要再乘 \(n\)：DFS 会共享前缀的计算，不是对每种完整方案重新计算全部项。

2. 排序：\(O(M\log M)\)

ans1、ans2 各有约 \(M\) 个元素，两次排序总时间为 \(O(M\log M)\)。随后对 ans1 的去重计数是 \(O(M)\)。

3. 最后匹配：\(O(M)\)

虽然代码看起来有两层循环，但 las 只增不减，整个过程中最多移动 cnt1 次，所以总时间为 \(O(\text{cnt1}+\text{cnt2})=O(M)\)。

合起来：

\[ \boxed{O\!\left(m^{n/2}\left(\log m^{n/2}+\log P\right)\right)} \]

所以选 D；C 漏掉了快速幂的时间开销。