魔数 - 题目列表

魔数

GitHub跳转原题关系图 Canvas 关系图返回列表

枚举五个模乘常数的 32 个闭包状态，用线段树维护状态置换后的区间和。

OJ: shumeng

题目 ID: CSP201912E

难度:提高+/省选-

标签:线段树懒标记群论区间修改

日期: 2026-07-31 16:21

形式化题目

初始序列 $A_i = i$ 。每次给出区间 $[l,r]$ ，先输出

s=\sum_{i=l}^{r} f(A_i),\qquad f(x)=(x\bmod P)\bmod 2019,

再令区间内全部元素乘给定的 $U_{s\bmod 5}$ ，乘法在模 $P = 2009731336725594113$ 下进行。需要在线处理所有查询， $n$ 最大 $10^6$ 、 $q$ 最大 $10^5$ 。

思路

朴素做法

小数据暴力解逐项保存模 $P$ 后的数，按定义求和和相乘，用于对拍。

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:41
 */
// brute.cpp：小数据直接维护每个数，逐项求和并逐项乘法更新。
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 2009731336725594113LL; // 第一层模数
const int MOD_SMALL = 2019;                  // 第二层模数

// 五个魔数 U[0..4]
long long unit[5] = {
    314882150829468584LL,
    427197303358170108LL,
    1022292690726729920LL,
    1698479428772363217LL,
    2006101093849356424LL,
};

long long multiply_mod(long long left, long long right) {
    return (long long)((__int128)left * right % MOD);
}

// 第二层取模：f(x) = (x mod P) mod 2019。
int get_value(long long number) {
    return (int)(number % MOD_SMALL);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, query_count;
    cin >> n >> query_count;
    vector<long long> value(n + 1);
    for (int i = 1; i <= n; i++) value[i] = i;
    while (query_count--) {
        int left, right;
        cin >> left >> right;
        int answer = 0;
        for (int i = left; i <= right; i++) answer += get_value(value[i]);
        cout << answer << '\n';
        int type = answer % 5;
        for (int i = left; i <= right; i++) value[i] = multiply_mod(value[i], unit[type]);
    }

    return 0;
}

五个乘数生成的 32 状态闭包

直接维护 $A_i$ 没有意义，因为一次区间乘法会改动很多位置。关键在五个给定的乘数：从模 $P$ 下的单位元 $1$ 出发，不断乘任意一个 $U_0\dots U_4$ 并去重，闭包恰好只有 32 个元素。把它们编号为 $G_0\dots G_{31}$ ，其中 $G_0=1$ 。

因此任意时刻的值都能写成 $A_i = i \cdot G_p$ 。在线段树的每个节点保存 32 个和：

sum[j]=\sum_{i\text{ 在该节点区间}} f(A_i\cdot G_j).

真正要输出的值是 $sum[0]$ 。若这个节点被乘上 $U_t$ ，新的第 $j$ 项为

f((A_i\cdot U_t)\cdot G_j)=f(A_i\cdot(U_t\cdot G_j)).

所以 $sum[j]$ 只是原数组中状态 $U_t\cdot G_j$ 对应项的值，即一次长度为 32 的置换。把这个置换写入懒标记即可延后传给子节点。

样例推演

样例的每一步如下。最后一列只展示第二层取模后的值；它说明区间和先决定乘数类型，再改变后续查询结果。

查询	区间	输出和 $s$	乘数类型 $s \bmod 5$	更新后的 $f(A_1..A_4)$
`1`	`[1,3]`	`6`	`1`	`1713, 1407, 1101, 4`
`2`	`[3,4]`	`1105`	`0`	`1713, 1407, 1735, 128`
`3`	`[3,3]`	`1735`	`0`	`1713, 1407, 1624, 128`
`4`	`[1,3]`	`4744`	`4`	`1550, 1081, 1065, 128`

正确性

初始时 $A_i=i=i\cdot G_0$ 。每次更新都只乘一个闭包中的元素，两个闭包元素相乘仍在闭包内，因此所有可能的 $A_i$ 都被 32 个状态覆盖。叶子节点按定义保存 32 种附加乘数后的值，父节点逐项相加，故任意节点的 $sum[j]$ 都满足定义。乘 $U_t$ 时的状态置换公式恰好给出更新后的 32 个定义值，懒标记只推迟、不改变置换。于是查询得到的 $sum[0]$ 正是更新前的区间和，之后按其模 5 进行区间置换也和题意完全一致。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:41
 */
#include <bits/stdc++.h>
using namespace std;

const int BASE = 1 << 20;        // 不小于 n 的二次幂
const int NODE_COUNT = BASE << 1; // 线段树节点数
const int MAX_STATE = 32;         // 五个乘数在模 P 下生成的乘法闭包大小
const long long MOD = 2009731336725594113LL; // 第一层模数
const int MOD_SMALL = 2019;       // 第二层模数

// 五个魔数 U[0..4]
long long unit[5] = {
    314882150829468584LL,
    427197303358170108LL,
    1022292690726729920LL,
    1698479428772363217LL,
    2006101093849356424LL,
};

int n, query_count, state_count;
int segment[NODE_COUNT][MAX_STATE]; // segment[node][j]：该节点区间内各元素乘上附加状态 G[j] 后 f 值之和
unsigned char lazy_tag[NODE_COUNT]; // 懒标记：节点待应用的乘数状态
int multiply_state[MAX_STATE][MAX_STATE]; // multiply_state[a][b] = G[a]*G[b] 对应的状态编号
int unit_state[5];                // 五个 U 对应的状态编号
vector<long long> state_multiplier; // G[0..31]，G[0]=1 是所有可达乘数的闭包

// 模 P 下的乘法（用 __int128 避免中间溢出）。
long long multiply_mod(long long left, long long right) {
    return (long long)((__int128)left * right % MOD);
}

// 查找某个乘数值对应的状态编号。
int find_state(long long value) {
    for (int i = 0; i < (int)state_multiplier.size(); i++) {
        if (state_multiplier[i] == value) return i;
    }
    return -1;
}

// 从 1 出发不断乘任意一个 U，BFS 生成全部可达乘数的闭包 G。
void build_states() {
    state_multiplier.push_back(1);
    for (int position = 0; position < (int)state_multiplier.size(); position++) {
        for (int i = 0; i < 5; i++) {
            long long next = multiply_mod(state_multiplier[position], unit[i]);
            if (find_state(next) == -1) state_multiplier.push_back(next);
        }
    }
    state_count = (int)state_multiplier.size();
    for (int i = 0; i < 5; i++) unit_state[i] = find_state(unit[i]);
    for (int i = 0; i < state_count; i++) {
        for (int j = 0; j < state_count; j++) {
            multiply_state[i][j] = find_state(multiply_mod(state_multiplier[i], state_multiplier[j]));
        }
    }
}

// 把节点整体乘上状态 state：32 项按乘法表重排，并合并进懒标记。
void apply_state(int node, int state) {
    if (state == 0) return;
    int old_sum[MAX_STATE];
    for (int i = 0; i < state_count; i++) old_sum[i] = segment[node][i];
    for (int i = 0; i < state_count; i++) {
        segment[node][i] = old_sum[multiply_state[state][i]];
    }
    lazy_tag[node] = (unsigned char)multiply_state[lazy_tag[node]][state];
}

// 下传懒标记到两个子节点。
void push_down(int node) {
    if (lazy_tag[node] == 0) return;
    apply_state(node << 1, lazy_tag[node]);
    apply_state(node << 1 | 1, lazy_tag[node]);
    lazy_tag[node] = 0;
}

// 用两个子节点的 32 项和更新父节点。
void pull_up(int node) {
    for (int i = 0; i < state_count; i++) {
        segment[node][i] = segment[node << 1][i] + segment[node << 1 | 1][i];
    }
}

void update(int node, int left, int right, int query_left, int query_right, int state) {
    if (query_left <= left && right <= query_right) {
        apply_state(node, state);
        return;
    }
    push_down(node);
    int middle = (left + right) >> 1;
    if (query_left <= middle) update(node << 1, left, middle, query_left, query_right, state);
    if (query_right > middle) update(node << 1 | 1, middle + 1, right, query_left, query_right, state);
    pull_up(node);
}

int query(int node, int left, int right, int query_left, int query_right) {
    if (query_left <= left && right <= query_right) return segment[node][0];
    push_down(node);
    int middle = (left + right) >> 1;
    int answer = 0;
    if (query_left <= middle) answer += query(node << 1, left, middle, query_left, query_right);
    if (query_right > middle) answer += query(node << 1 | 1, middle + 1, right, query_left, query_right);
    return answer;
}

// 建树：叶子 i 存 i 乘上每个附加状态 G[j] 后 f 值的前缀和。
void build_segment_tree() {
    long long remainder[MAX_STATE] = {};
    for (int i = 1; i <= n; i++) {
        int node = BASE + i - 1;
        for (int j = 0; j < state_count; j++) {
            remainder[j] += state_multiplier[j];
            if (remainder[j] >= MOD) remainder[j] -= MOD;
            segment[node][j] = (int)(remainder[j] % MOD_SMALL);
        }
    }
    for (int node = BASE - 1; node >= 1; node--) pull_up(node);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> query_count;
    build_states();
    build_segment_tree();
    while (query_count--) {
        int left, right;
        cin >> left >> right;
        // 单位元状态 sum[0] 就是当前区间和，再按 s mod 5 选择乘数做区间更新。
        int answer = query(1, 1, BASE, left, right);
        cout << answer << '\n';
        update(1, 1, BASE, left, right, unit_state[answer % 5]);
    }

    return 0;
}

复杂度

状态数固定为 32。令 $BASE=2^{20}$ ，它是不小于 $10^6$ 的最小二次幂。建树时间为 $O(32 \cdot BASE)$ ，每次区间查询和区间更新均为 $O(32\log n)$ 。树数组有 $2 \cdot BASE$ 个节点，每项使用 int，约 256 MiB；加上懒标记后总空间为 $O(32 \cdot BASE)$ 。

总结

看似任意的大整数区间乘法，被五个特殊常数限制在一个 32 元的有限乘法状态集合中。把“元素当前乘数”转成“节点在所有附加状态下的答案”，区间乘法就从逐点修改变成了固定置换。

图示解析

这张图展示从魔数闭包到线段树操作的主线：

text

1
2
3
4
5五个 U 的模 P 乘法闭包（32 个状态）
`- 每个 A[i] = i * G[p]
   `- 节点保存每个附加 G[j] 的 f 值和
      |- 查询：读取单位元状态 sum[0]
      `- 更新：按 U[t] * G[j] 重排 32 项并记录懒标记

32 个状态不是额外的近似，而是给定五个常数在模 $P$ 下所有可达乘数的完整集合。线段树始终同时维护这些状态下的答案，因此一次更新只需替换状态下标，不需要逐项重新计算 $f$ 。

由于原题 1 秒的时限过于卡常，本评测时限改为 2 秒。但是我们的 std 可以保证在 1 秒内通过官方和民间数据。

时间限制： ~~1.0 秒~~ 2.0 秒

空间限制： 1024 MB

题目背景

“魔数”是指代码中出现但没有解释的数字常量。即使代码是你亲手写下的，很可能在几个月以后你也不记得这些魔数的意义了。而这道题中魔数的含义，就需要你自己探索了……

在本题中，我们定义：

$U_0 = 314882150829468584$
$U_1 = 427197303358170108$
$U_2 = 1022292690726729920$
$U_3 = 1698479428772363217$
$U_4 = 2006101093849356424$
$f(x)=( x \bmod 2009731336725594113 ) \bmod 2019$

题目描述

有一个长度为 $n$ 的序列 $A$ 。初始时所有元素依次为从 $1$ 到 $n$ 的正整数，即 $A_i = i\ (1 \leq i \leq n)$ 。

有 $q$ 次查询，每次查询输入两个整数 $l,r\ (1 \leq l \leq r \leq n)$ ，你需要依次进行以下操作：

设 $s = f(A_l) + f(A_{l + 1}) + \cdots + f(A_r)$ ；
输出 $s$ ；
设 $t=s \bmod 5$ ；
令 $A_l, A_{l+1}, \dots, A_r$ 的每个数都乘以 $U_t$ 。

请你依次输出每一次查询的答案。

输入格式

从标准输入读入数据。

第一行包含两个正整数 $n, q$ 。

接下来 $q$ 行，每行输入两个正整数 $l, r$ 。

输出格式

输出到标准输出。

输出 $q$ 行，每一行依次表示每一次查询的答案。

input1

output1

input2

output2

子任务

测试点编号	$n=$	$q=$
$1$	$1$	$1$
$2$	$10$	$1$
$3$	$100$	$10$
$4$	$1000$	$100$
$5$	$10^4$	$1000$
$6$	$10^5$	$10^4$
$7$	$1.2\times 10^5$	$1.2\times 10^4$
$8$	$1.4\times 10^5$	$1.4\times 10^4$
$9$	$1.6\times 10^5$	$1.6\times 10^4$
$10$	$1.9\times 10^5$	$1.9\times 10^4$
$11$	$2.3\times 10^5$	$2.3\times 10^4$
$12$	$2.7\times 10^5$	$2.7\times 10^4$
$13$	$3.2\times 10^5$	$3.2\times 10^4$
$14$	$3.7\times 10^5$	$3.7\times 10^4$
$15$	$4.4\times 10^5$	$4.4\times 10^4$
$16$	$5.2\times 10^5$	$5.2\times 10^4$
$17$	$6.1\times 10^5$	$6.1\times 10^4$
$18$	$7.2\times 10^5$	$7.2\times 10^4$
$19$	$8.5\times 10^5$	$8.5\times 10^4$
$20$	$10^6$	$10^5$

所有最终测试数据的生成方式为：

按照上表指定 $n, q$ ；
对于每次查询， $l, r$ 均在合法范围内独立均匀随机确定。

魔数

目录

形式化题目

思路

朴素做法

五个乘数生成的 32 状态闭包

样例推演

正确性

代码

复杂度

总结

图示解析