CSP-S 2024 第一轮 第31题：输入“10”，输出的第一行是？（

题目

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1000000 + 5;
const int P1 = 998244353, P2 = 1000000007;
const int B1 = 2, B2 = 31;
const int K1 = 0, K2 = 13;

typedef long long ll;

int n;
bool p[maxn];
int p1[maxn], p2[maxn];

struct H {
    int h1, h2, l;
    H(bool b = false) {
        h1 = b + K1;
        h2 = b + K2;
        l = 1;
    }

    H operator + (const H & h) const {
        H hh;
        hh.l = l + h.l;
        hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1;
        hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2;
        return hh;
    }

    bool operator == (const H & h) const {
        return l == h.l && h1 == h.h1 && h2 == h.h2;
    }

    bool operator < (const H & h) const {
        if (l != h.l) return l < h.l;
        else if (h1 != h.h1) return h1 < h.h1;
        else return h2 < h.h2;
    }
} h[maxn];

void init() {
    memset(p, 1, sizeof(p));
    p[0] = p[1] = false;
    p1[0] = p2[0] = 1;
    for (int i = 1; i <= n; ++i) {
        p1[i] = (1ll * B1 * p1[i-1]) % P1;
        p2[i] = (1ll * B2 * p2[i-1]) % P2;
        if (!p[i]) continue;
        for (int j = 2 * i; j <= n; j += i) {
            p[j] = false;
        }
    }
}

int solve() {
    for (int i = n; i; --i) {
        h[i] = H(p[i]);
        if (2 * i + 1 <= n) {
            h[i] = h[2 * i] + h[i] + h[2 * i + 1];
        } else if (2 * i <= n) {
            h[i] = h[2 * i] + h[i];
        }
    }

    cout << h[1].h1 << endl;
    sort(h + 1, h + n + 1);
    int m = unique(h + 1, h + n + 1) - (h + 1);
    return m;
}

int main() {
    cin >> n;
    init();
    cout << solve() << endl;
}

输入 $10$，输出的第一行是？（  ）

选项

• A. $83$
• B. $424$
• C. $54$
• D. $110101000$

答案

A

题解

答案是 A. \(83\)。

这里的 h1 实际上把一个 01 序列看作二进制数。分三步看：

1. 判断质数

p[i] 表示 \(i\) 是否为质数。\(1\sim10\) 中的质数是 \(2,3,5,7\)，对应 1，其他数对应 0。

1. 确定拼接顺序

把 \(i\) 看作树的节点，左右孩子分别是 \(2i\) 和 \(2i+1\)。代码 ``cpp h[i] = h[2 * i] + h[i] + h[2 * i + 1]; `` 按照“左子树 → 当前节点 → 右子树”的中序遍历顺序拼接。

当 \(n=10\) 时： ``text 节点顺序：8 4 9 2 10 5 1 6 3 7 是否质数：0 0 0 1 0 1 0 0 1 1 ``

1. 计算 h1

因为 B1 = 2、K1 = 0，拼接公式相当于把左边的二进制数左移，再接上右边的数。因此： \[ h[1].h1=(0001010011)_2=64+16+2+1=\boxed{83}. \]

solve() 内部先输出这个值，所以第一行是 83。