代码详解：阅读程序-3

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

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

/*
  题意/目标（从代码语义反推）：
  - 用堆式下标（i 的左子为 2*i，右子为 2*i+1）表示的一棵完全二叉树，结点编号 1..n。
  - 用埃氏筛得到 p[i]（是否素数），把每个结点的“标记”设为：素数=1，非素数=0。
  - 对每个结点 i，构造其“子树的中序遍历序列”（左-根-右）的滚动哈希（双模）。
  - 把所有结点（即所有子树）的哈希块放到一起，排序去重，统计“不同中序串”的个数。
  - 程序打印两行：
      第一行：根结点 1 的“第一模哈希值 h[1].h1”（常作为调试/校验）
      第二行：不同子树中序串的个数（sort + unique 的结果个数）

  关键点：
  - H 结构体把“一段序列”的哈希（双模）和长度封装起来，重载了 + 号表示“拼接”。
  - 拼接时使用多项式滚动哈希：左段哈希乘以底数的“右段长度次幂”后加上右段哈希，顺序敏感。
*/

// 约束常量与哈希参数
const int maxn = 1000000 + 5;     // 最大可能 n 的上界（数组容量）
const int P1 = 998244353, P2 = 1000000007; // 两个互不相同的大质数模（双模降低碰撞）
const int B1 = 2, B2 = 31;        // 两个底数（多项式哈希的 base）
const int K1 = 0, K2 = 13;        // 叶子字符的偏移（把 0/1 映射到不同起点，更稳）

typedef long long ll;

int n;                 // 结点总数（也是筛素数的上界）
bool p[maxn];          // p[i] = true 表示 i 是素数（埃氏筛的结果）
int p1[maxn], p2[maxn];// p1[k] = B1^k mod P1，p2[k] = B2^k mod P2（幂数组，供拼接位移用）

/*
  H：表示“一段序列”的哈希块
  - h1, h2：此段的双模哈希值
  - l：此段的长度（字符个数）。这里“字符”就是一个结点的布尔标记（素数/非素数）
*/
struct H {
    int h1, h2, l;

    // 用一个布尔值初始化为“单字符”序列：长度=1，值=(b + K*)
    // 例如 b=1（素数）→ h1=1+K1, h2=1+K2；b=0（非素）→ h1=K1, h2=K2
    H(bool b = false) {
        h1 = b + K1;
        h2 = b + K2;
        l = 1;
    }

    /*
      拼接运算：当前块在左，参数块 h 在右（顺序敏感）
      公式（以 h1 为例）：
        (left.h1 * B1^(right.l) + right.h1) mod P1
      h2 同理，用 B2/P2。
      长度相加：新长度 = left.l + right.l

      例子（不取模，B1=2,K1=0）：
        X = H(1) 表示串 "1"，哈希=1；Y = H(0) 表示 "0"，哈希=0
        X+Y = 1*2^1 + 0 = 2   （"10"）
        Y+X = 0*2^1 + 1 = 1   （"01"）
      可见顺序改变结果也改变（不满足交换律），符合“字符串拼接”的语义。
    */
    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;
    }

    // 排序比较：先按长度，再按 h1，最后按 h2（供 sort+unique 使用）
    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]; // h[i] 存编号 i 结点“子树中序序列”的哈希块

/*
  init(): 预处理阶段
  - 初始化素数表 p[]：埃氏筛（Sieve of Eratosthenes）
  - 初始化幂数组 p1[]/p2[]：p1[k]=B1^k mod P1，p2[k]=B2^k mod P2

  复杂度：
  - 埃氏筛：O(n log log n)（本写法从 2*i 开始，常数略大；也可用 i*i 优化）
  - 幂数组：O(n)
*/
void init() {
    // 把 p 的每个字节设为 1（即 true），然后手动把 0 和 1 设置为非素
    memset(p, 1, sizeof(p));
    p[0] = p[1] = false;

    // 幂数组起点：B^0 = 1
    p1[0] = p2[0] = 1;

    for (int i = 1; i <= n; ++i) {
        // 递推得到 B^i
        p1[i] = (1ll * B1 * p1[i-1]) % P1;
        p2[i] = (1ll * B2 * p2[i-1]) % P2;

        // 埃氏筛：若 i 已知为素数，则把其倍数标记为合数
        if (!p[i]) continue;
        for (int j = 2 * i; j <= n; j += i) {
            p[j] = false;
        }
        /*
          注：更常见的优化写法是从 j = i*i 开始，且外层只需跑到 i*i<=n：
              for (int i=2; 1LL*i*i<=n; ++i) if (p[i])
                  for (long long j=1LL*i*i; j<=n; j+=i) p[j]=false;
          功能相同，常数更小。
        */
    }
}

/*
  solve():
  - 自底向上（i=n..1）计算每个结点的“子树中序串哈希块” h[i]
    规则（完全二叉树/堆式下标）：
      若同时有左右子：h[i] = h[2*i] + H(p[i]) + h[2*i+1]   // 左-根-右（中序）
      若只有左子：      h[i] = h[2*i] + H(p[i])
      若无子：          h[i] = H(p[i])                       // 叶子（构造函数里已做）
  - 打印根结点（1）的第一模哈希值 h[1].h1
  - 对所有 h[1..n] 做排序 + unique，并返回不同块的个数

  复杂度：
  - 建哈希：每个结点常数次操作，O(n)
  - 排序去重：O(n log n) + O(n)
  - 总体由排序主导：O(n log n)
*/
int solve() {
    // 自底向上：因为要先用到子结点的哈希
    for (int i = n; i; --i) {
        // 当前结点自身“单字符块”（素数=1，非素=0）
        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];
        }
        // 否则为叶子：h[i] 已在构造时设为长度=1 的单字符块
    }

    // 第一行输出：根结点子树（整棵树）的第一模哈希值（常用于校验/调试）
    cout << h[1].h1 << endl;

    // 排序 + 去除相邻重复块（需要 operator< 与 operator== 支持）
    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; // 第二行：不同子树数
    return 0;
}