异或 - 题目列表

异或

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

利用 f(n) 的逐位公式，把区间数位平移转化为线段树上的模 k 线性维护。

OJ: shumeng

题目 ID: CSP202603D

难度:提高+/省选-

标签:线段树数位数学

日期: 2026-07-31 16:22

形式化题目

给定 $n,m,k$ （ $k$ 为奇数），定义 $a\oplus_k b$ 为 $k$ 进制下逐位相加且不进位的运算，并递归定义

f(0)=0,\qquad f(n)=n\oplus_k f(n-1).

维护一个长度为 $n$ 的序列 $a_1,\dots,a_n$ ，支持两种操作：

1 l r v：把 $[l,r]$ 内的每个 $a_i$ 改为 $a_i\oplus_k v$ ；
2 l r：查询 $f(a_l)\oplus_k f(a_{l+1})\oplus_k\cdots\oplus_k f(a_r)$ 。

思路

把递推函数化成数位公式

设 $n$ 的 $k$ 进制最低位为 $d_0$ ，第 $p$ 位为 $d_p$ 。把递推式逐位展开可得：

f(n)_0=\frac{d_0(d_0+1)}2\pmod k,\qquad f(n)_p=d_p(d_0+1)\pmod k\quad(p\ge 1).

这里除以 $2$ 使用逆元 $(k+1)/2$ ，因为 $k$ 为奇数时 $2$ 在模 $k$ 下有逆元。

朴素实现

按上面的公式逐元素计算即可验证结论，只适合小数据：

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/**
 * 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:22
 * update_at: 2026-08-17 22:40
 */
// brute.cpp：小数据暴力解，直接逐元素计算，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

long long k; // k 进制基数，全局给定且为奇数

// 计算 a 与 b 在 k 进制下逐位相加、不进位的结果。
long long digit_xor(long long a, long long b) {
    long long result = 0;
    long long power = 1;
    while (a > 0 || b > 0) {
        long long digit = (a % k + b % k) % k; // 这一位的和对 k 取模
        result += digit * power;
        power *= k;
        a /= k;
        b /= k;
    }
    return result;
}

// 用数位公式直接计算 f(n)。
// 设最低位为 d0、第 p 位为 dp，则 f(n) 最低位是 d0(d0+1)/2，第 p 位是 dp(d0+1)。
long long f_value(long long n) {
    long long d0 = n % k;
    long long result = d0 * (d0 + 1) / 2 % k;
    long long power = k;
    n /= k;
    long long factor = d0 + 1;
    while (n > 0) {
        result += (n % k * factor % k) * power;
        power *= k;
        n /= k;
    }
    return result;
}

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

    int n, m;
    cin >> n >> m >> k;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    // 每次操作都按定义逐项模拟，复杂度高，只适合小数据。
    for (int op = 0; op < m; op++) {
        int type, l, r;
        cin >> type >> l >> r;
        if (type == 1) {
            long long v;
            cin >> v;
            for (int i = l; i <= r; i++) {
                a[i] = digit_xor(a[i], v);
            }
        } else {
            // 查询：逐项计算 f(a_i)，再按位累加得到异或和
            vector<long long> digit_sum(32, 0);
            for (int i = l; i <= r; i++) {
                long long current = f_value(a[i]);
                int digit = 0;
                while (current > 0) {
                    digit_sum[digit] = (digit_sum[digit] + current % k) % k;
                    current /= k;
                    digit++;
                }
            }
            long long answer = 0;
            long long power = 1;
            for (int digit = 0; digit < (int)digit_sum.size(); digit++) {
                answer += digit_sum[digit] * power;
                power *= k;
            }
            cout << answer << '\n';
        }
    }
    return 0;
}

线段树维护统计量

查询需要 $f$ 的按位和，而 $f$ 只依赖 $d_0$ 和 $d_p$ ，因此每个节点只需维护下面这些模 $k$ 的量：

$S_0=\sum d_0$ ， $S_{00}=\sum d_0^2$ ；
对每个高位 $p$ ： $S_p=\sum d_p$ ， $S_{p0}=\sum d_p d_0$ 。

于是查询答案的第 $0$ 位是 $(S_{00}+S_0)/2$ ，第 $p$ 位是 $S_{p0}+S_p$ 。

区间加如何更新

区间加上 $v$ 后，设 $v$ 的第 $0$ 位和第 $p$ 位分别为 $c_0,c_p$ ，则每个数变为 $d_0'=d_0+c_0,\ d_p'=d_p+c_p$ （模 $k$ ）。代入上面两个公式展开，得到逐项的线性更新：

维护量	更新后
$S_0$	$S_0+\text{len}\cdot c_0$
$S_{00}$	$S_{00}+2c_0S_0+\text{len}\cdot c_0^2$
$S_p$	$S_p+\text{len}\cdot c_p$
$S_{p0}$	$S_{p0}+c_0S_p+c_pS_0+\text{len}\cdot c_pc_0$

所有公式都在模 $k$ 的环上成立。区间操作用懒标记保存每个数位的平移量，push_down 时对整段节点做同样的线性更新即可。

代码

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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284/**
 * 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:22
 * update_at: 2026-08-17 22:40
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500000;
const int MAXM = 10000;
const int MAXD = 20;        // k 进制位数上限
const int MAXNODE = MAXN * 4 + 5;

// 一条操作：type=1 区间加，type=2 区间查询
struct Operation {
    int type;
    int l;
    int r;
    long long v;
};

// 一次区间查询聚合出来的统计量，各量都按模 k 保存
struct Info {
    int s0;          // 第 0 位 d0 之和
    int s00;         // d0^2 之和
    int sp[MAXD];    // sp[p] 为第 p 位 dp 之和
    int sp0[MAXD];   // sp0[p] 为 dp*d0 之和
};

int n, m;
long long base_k;      // k 进制基数
int digits;            // 当前有效位数
vector<long long> value_array; // 原始序列，1 下标
vector<Operation> operations;  // 全部操作

// 线段树全局数组：sum0/sum00 存第 0 位统计，sum_p/sum_p0 存高位统计
int sum0[MAXNODE];
int sum00[MAXNODE];
int sum_p[MAXD][MAXNODE];
int sum_p0[MAXD][MAXNODE];
int lazy_shift[MAXD][MAXNODE]; // 懒标记：每个数位当前的平移量

// 把 x 拆成 k 进制各位，结果写入 result[0..digits-1]。
void split_digits(long long x, int result[MAXD]) {
    for (int i = 0; i < MAXD; i++) {
        result[i] = 0;
    }
    for (int i = 0; i < digits; i++) {
        result[i] = (int)(x % base_k);
        x /= base_k;
    }
}

// 给节点 p 的整体加 shift：所有位各自平移，length 是节点覆盖的区间长度。
// 核心是利用完全平方公式：(d+c)^2 = d^2 + 2cd + c^2 逐项更新各统计量。
void apply_shift(int p, int length, int shift[MAXD]) {
    int old_s0 = sum0[p];
    int old_s00 = sum00[p];
    int s0_shift = shift[0];
    long long len_mod = length % base_k;

    sum0[p] = (int)((old_s0 + len_mod * s0_shift) % base_k);
    sum00[p] = (int)((old_s00 + 2LL * s0_shift * old_s0
                      + len_mod * s0_shift % base_k * s0_shift) % base_k);

    for (int digit = 1; digit < digits; digit++) {
        int old_sp = sum_p[digit][p];
        int old_sp0 = sum_p0[digit][p];
        int digit_shift = shift[digit];
        // (d+c)*(d0+c0) = d*d0 + c*d0 + d*c0 + c*c0
        long long next_sp0 = old_sp0;
        next_sp0 += 1LL * s0_shift * old_sp;
        next_sp0 += 1LL * digit_shift * old_s0;
        next_sp0 += len_mod * digit_shift % base_k * s0_shift;
        sum_p[digit][p] = (int)((old_sp + len_mod * digit_shift) % base_k);
        sum_p0[digit][p] = (int)(next_sp0 % base_k);
    }

    for (int digit = 0; digit < digits; digit++) {
        lazy_shift[digit][p] = (int)((lazy_shift[digit][p] + shift[digit]) % base_k);
    }
}

// 用左右孩子合并当前节点的统计量。
void pull(int p) {
    int left = p * 2;
    int right = left + 1;
    sum0[p] = (int)((sum0[left] + (long long)sum0[right]) % base_k);
    sum00[p] = (int)((sum00[left] + (long long)sum00[right]) % base_k);
    for (int digit = 1; digit < digits; digit++) {
        sum_p[digit][p] = (int)((sum_p[digit][left]
                                 + (long long)sum_p[digit][right]) % base_k);
        sum_p0[digit][p] = (int)((sum_p0[digit][left]
                                  + (long long)sum_p0[digit][right]) % base_k);
    }
}

// 建树：叶子节点直接保存原数的各位统计量。
void build(int p, int l, int r) {
    if (l == r) {
        int digit_value[MAXD];
        split_digits(value_array[l], digit_value);
        sum0[p] = digit_value[0] % base_k;
        sum00[p] = (int)(1LL * digit_value[0] * digit_value[0] % base_k);
        for (int digit = 1; digit < digits; digit++) {
            sum_p[digit][p] = digit_value[digit] % base_k;
            sum_p0[digit][p] = (int)(1LL * digit_value[digit]
                                      * digit_value[0] % base_k);
        }
        return;
    }
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    pull(p);
}

// 把节点 p 的懒标记下传给两个孩子。
void push_down(int p, int l, int r) {
    bool has_lazy = false;
    int shift[MAXD];
    for (int digit = 0; digit < digits; digit++) {
        shift[digit] = lazy_shift[digit][p];
        if (shift[digit] != 0) {
            has_lazy = true;
        }
    }
    if (!has_lazy || l == r) {
        return;
    }
    int mid = (l + r) / 2;
    apply_shift(p * 2, mid - l + 1, shift);
    apply_shift(p * 2 + 1, r - mid, shift);
    for (int digit = 0; digit < digits; digit++) {
        lazy_shift[digit][p] = 0;
    }
}

// 区间加：给 [ql, qr] 上的每个数整体平移 shift。
void update(int p, int l, int r, int ql, int qr, int shift[MAXD]) {
    if (ql <= l && r <= qr) {
        apply_shift(p, r - l + 1, shift);
        return;
    }
    push_down(p, l, r);
    int mid = (l + r) / 2;
    if (ql <= mid) {
        update(p * 2, l, mid, ql, qr, shift);
    }
    if (qr > mid) {
        update(p * 2 + 1, mid + 1, r, ql, qr, shift);
    }
    pull(p);
}

// 取出节点 p 的统计量，拼成 Info 结构。
Info node_info(int p) {
    Info result;
    result.s0 = sum0[p];
    result.s00 = sum00[p];
    for (int digit = 0; digit < MAXD; digit++) {
        result.sp[digit] = 0;
        result.sp0[digit] = 0;
    }
    for (int digit = 1; digit < digits; digit++) {
        result.sp[digit] = sum_p[digit][p];
        result.sp0[digit] = sum_p0[digit][p];
    }
    return result;
}

// 合并两个区间的统计量，用于查询拼接。
Info merge_info(const Info &left, const Info &right) {
    Info result;
    result.s0 = (int)((left.s0 + (long long)right.s0) % base_k);
    result.s00 = (int)((left.s00 + (long long)right.s00) % base_k);
    for (int digit = 0; digit < MAXD; digit++) {
        result.sp[digit] = 0;
        result.sp0[digit] = 0;
    }
    for (int digit = 1; digit < digits; digit++) {
        result.sp[digit] = (int)((left.sp[digit]
                                  + (long long)right.sp[digit]) % base_k);
        result.sp0[digit] = (int)((left.sp0[digit]
                                   + (long long)right.sp0[digit]) % base_k);
    }
    return result;
}

// 区间查询：返回 [ql, qr] 聚合出的统计量。
Info query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return node_info(p);
    }
    push_down(p, l, r);
    int mid = (l + r) / 2;
    if (qr <= mid) {
        return query(p * 2, l, mid, ql, qr);
    }
    if (ql > mid) {
        return query(p * 2 + 1, mid + 1, r, ql, qr);
    }
    Info left = query(p * 2, l, mid, ql, qr);
    Info right = query(p * 2 + 1, mid + 1, r, ql, qr);
    return merge_info(left, right);
}

// 打印 __int128，因为 k 的幂可能超出 long long 范围。
void print_int128(__int128 value) {
    if (value == 0) {
        cout << 0 << '\n';
        return;
    }
    string result;
    while (value > 0) {
        result.push_back((char)('0' + value % 10));
        value /= 10;
    }
    reverse(result.begin(), result.end());
    cout << result << '\n';
}

// 由聚合统计量还原答案：第 0 位是 (S00+S0)/2，第 p 位是 Sp0+Sp。
void answer_query(const Info &info) {
    long long inverse_two = (base_k + 1) / 2; // k 为奇数，2 的逆元
    int low = (int)((info.s00 + (long long)info.s0) % base_k);
    low = (int)(low * inverse_two % base_k);

    __int128 answer = low;
    __int128 power = base_k;
    for (int digit = 1; digit < digits; digit++) {
        int current = (info.sp0[digit] + (long long)info.sp[digit]) % base_k;
        answer += power * current;
        power *= base_k;
    }
    print_int128(answer);
}

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

    cin >> n >> m >> base_k;
    value_array.assign(n + 1, 0);
    long long max_value = 0;
    for (int i = 1; i <= n; i++) {
        cin >> value_array[i];
        max_value = max(max_value, value_array[i]);
    }

    // 先读入全部操作，统计出现过的最大值，确定需要的 k 进制位数
    operations.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> operations[i].type;
        if (operations[i].type == 1) {
            cin >> operations[i].l >> operations[i].r >> operations[i].v;
            max_value = max(max_value, operations[i].v);
        } else {
            cin >> operations[i].l >> operations[i].r;
            operations[i].v = 0;
        }
    }

    digits = 1;
    while (max_value >= base_k && digits < MAXD) {
        max_value /= base_k;
        digits++;
    }

    build(1, 1, n);
    for (int i = 0; i < m; i++) {
        if (operations[i].type == 1) {
            int shift[MAXD];
            split_digits(operations[i].v, shift);
            update(1, 1, n, operations[i].l, operations[i].r, shift);
        } else {
            Info result = query(1, 1, n, operations[i].l, operations[i].r);
            answer_query(result);
        }
    }
    return 0;
}

复杂度

设 $D$ 为需要的 $k$ 进制位数（由出现过的最大值决定）。

时间：每次区间操作或查询为 $O(D\log n)$ ，总时间复杂度 $O(mD\log n)$ 。
空间：每个节点保存 $O(D)$ 个统计量，空间复杂度 $O(Dn)$ 。

总结

先把递推函数化成数位公式，再维护公式中真正需要的低阶统计量，就能把看似逐个数位处理的区间操作转化为线段树上的线性更新。关键在于发现 $f(n)$ 每位的值只依赖最低位 $d_0$ ，因此不需要维护整个数值。

题目来自第 41 次 CSP 认证 T4，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 6.0 秒

空间限制： 1024 MB

题目描述

类似二进制下的异或操作，小 C 定义了一种 $k$ 进制下的异或运算 $\oplus_k$ 。

对于任意非负整数 $a,b$ 定义 $a$ 和 $b$ 进行 $k$ 进制下的不进位加法的结果为 $a\oplus_k b$ 。

形式化地，如果 $a=\sum\limits_{i=0}^n(a_i\cdot k^i),b=\sum\limits_{i=0}^n(b_i\cdot k^i)$ ，其中 $a_i,b_i$ 是小于 $k$ 的非负整数，则 $a\oplus_k b=\sum\limits_{i=0}^n(((a_i+b_i)\bmod k)\cdot k^i)$ 。

如计算 $11\oplus_3 7$ 的过程如下： $11$ 可表示为 $2\times 3^0+0\times 3^1+1\times 3^2$ ， $7$ 可表示为 $1\times 3^0+2\times 3^1+0\times 3^2$ ，则 $11\oplus_3 7=((2+1)\bmod 3)\times 3^0+((2+0)\bmod 3)\times 3^1+((0+1)\bmod 3)\times 3^2=0\times 3^0+2\times 3^1+1\times 3^2=15$ 。

之后小 C 在此运算基础上对任意非负整数 $n$ 定义了一个函数 $f$ ，具体如下：

f(n)= \begin{cases} 0 & (n=0)\\ n\oplus_k f(n-1) & (n> 0) \end{cases}

现在小 C 有一个非负整数序列 $a_1,a_2,\cdots,a_n$ 和全局给定的奇数 $k$ 。小 C 希望对这个序列进行 $m$ 次操作：

操作 1 给出三个参数 $l,r,v$ ，表示将下标在区间 $[l,r]$ 内的 $a_i$ 修改为 $a_i \oplus_k v$ 。
操作 2 给出两个参数 $l,r$ ，表示查询 $f(a_l)\oplus_k f(a_{l+1})\oplus_k \cdots \oplus_k f(a_r)$ 。

输入格式

从标准输入读入数据。

第一行给出三个正整数 $n,m,k$ 。

接下来一行给出 $n$ 个非负整数，表示序列 $a$ 。

接下来 $m$ 行每行给出三个或者四个非负整数，表示 $m$ 次操作。

每行第一个数字为操作的类型 $t$ 。

如果 $t$ 为 $1$ ，则该操作为操作 1，接下来给出三个非负整数 $l,r,v$ 作为该操作的参数。
如果 $t$ 为 $2$ ，则该操作为操作 2，接下来给出两个正整数 $l,r$ 作为该操作的参数。

输出格式

输出到标准输出。

对于每个操作 2，输出单独的一行，包含一个非负整数，为该操作的答案。

input1

1
2
3
4
5
65 4 11
13 17 14 19 15
1 1 3 9
2 1 2
1 3 5 6
2 4 5

output1

1
276
50

样例 1 解释

第 1 个操作结束之后，序列 $a$ 为： $[{\color{red}11},{\color{red}15},{\color{red}12},19,15]$ 。
第 2 个操作的答案为 $f(a_1)\oplus_{11}f(a_2)=11\oplus_{11} 65=76$ 。
第 3 个操作结束之后，序列 $a$ 为： $[11,15,{\color{red}18},{\color{red}14},{\color{red}21}]$ 。
第 4 个操作的答案为 $f(a_4)\oplus_{11}f(a_5)=50\oplus_{11} 0=50$ 。

样例 2

见题目文件区的 2.in 和 2.ans。

样例 2 解释

该样例满足子任务 1 的限制。

样例 3

见题目文件区的 3.in 和 3.ans。

样例 3 解释

该样例满足子任务 2 的限制。

样例 4

见题目文件区的 4.in 和 4.ans。

样例 4 解释

该样例满足子任务 3 的限制。

样例 5

见题目文件区的 5.in 和 5.ans。

样例 5 解释

该样例满足子任务 4 的限制。

子任务

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

对于所有数据满足： $1\le n\le 5 \times 10^{5},\ 1\le m \le 10^{4},\ 11\le k \le 10^{9}$ 且 $k$ 为奇数。对于每个操作保证 $t\in\{1,2\},1\le l\le r\le n$ 。对于任意时刻，保证 $a_i$ 非负。对于所有操作 1，保证参数 $v$ 非负。记所有时刻序列中的元素 $a_i$ 和所有操作一中的参数 $v$ 的最大值为 $R$ ，则保证 $R\le10^{12}$ 。

子任务编号	分值	$n\le$	$m\le$	特殊性质
1	20	$10^3$	$10^3$	$R\le 10^6$
2	30	$10^3$	$10^3$	无
3	20	$5\times 10^5$	$10^4$	$a_i$ 和操作 1 的参数 $v$ 均是 $k$ 的倍数
4	30	$5\times 10^5$	$10^4$	无

提示

子任务 3 可能有助于你更好地探索函数 $f$ 的相关性质。

异或

目录

形式化题目

思路

把递推函数化成数位公式

朴素实现

线段树维护统计量

区间加如何更新

代码

复杂度

总结