利用循环左移与异或可交换,把对手的每个出手时刻化成常数 C_i,问题变为选 y 使 min_i(y^C_i) 最大,用 01 字典树自底向上 DP 求值与方案数。
OJ: roj
题目 ID: 1701
难度:提高+/省选-
标签:字典树位运算贪心python
创建: 2026-10-07 16:04
更新: 2026-10-07 16:04
形式化题目
给定位数
:刚选完 ,还没有异或任何数; :已经依次异或了 。
在第
之后继续异或剩下的
- 最终值的最大值;
- 取到这个最大值的初值
的个数。
下文记
正解
思路
第一步:看清对手到底做了什么。 把
两者相加正好等于把最高位搬到最低位:
也就是循环左移一位。这一步是最关键的观察:题面那个带取整、取模的怪式子, 其实是一个纯粹的位重排。
第二步:位重排与异或可交换。 对任意
第三步:把"时刻"化成常数。 记前缀异或
对手的
第四步:问题化成经典模型。 因为
给定
个常数 ,选 使 最大, 并统计这样的 的个数。
第五步:01 字典树 + 逐位 DP。 把每个
设
| 当前结点情况 | 该位的结论 | 转移 |
|---|---|---|
| 只存在一个儿子 | 子树内所有 |
|
| 两个儿子都在, |
对手必然把这一位压成 |
取更优的那侧: |
| 两个儿子都在, |
同上,这一位必为 |
第二个分支要解释一下:两棵子树都在时,无论
叶子(深度
样例推演。 样例
| 四个时刻的最终值 |
对手取最小值 | ||
|---|---|---|---|
| 0 | 0 | 0, 3, 0, 0 | 0 |
| 1 | 2 | 2, 1, 2, 2 | 1 |
| 2 | 1 | 1, 2, 1, 1 | 1 |
| 3 | 3 | 3, 0, 3, 3 | 0 |
最大值是 1 与 2。
flowchart TD R["root 高位"] -->|"bit1 = 0"| A["所有 C 的 bit1 = 0"] R -->|"bit1 = 1"| B["只剩 C=3"] A -->|"bit0 = 0"| L0["C=0,0,0 叶子 g=0"] B -->|"bit0 = 1"| L1["C=3 叶子 g=0"]
代码
Python 版:
#!/usr/bin/env python3
# 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-10-07 15:58
# update_at: 2026-10-07 16:04
import sys
NO_CHILD = -1 # 01 字典树的空边标记:kids[u][b] 为它表示结点 u 没有走边 b 的儿子
def prefix_xors(a: list[int]) -> list[int]:
"""返回前缀异或表 p,p[i] = a[0] ^ ... ^ a[i-1],p[0] = 0。"""
p = [0]
for v in a:
p.append(p[-1] ^ v)
return p
def moment_consts(p: list[int], n: int) -> list[int]:
"""返回对手每个时刻对应的常数 C_i = rol(p[i]) ^ (p[m] ^ p[i]),i 从 0 到 m。
对手在第 i 个时刻出手时最终值恰好是 rol(x) ^ C_i;rol 是 n 位循环左移。
"""
full = (1 << n) - 1 # n 位全 1 掩码,把循环左移截回 n 位
return [
((p[i] << 1 & full) | p[i] >> (n - 1)) ^ (p[-1] ^ p[i])
for i in range(len(p))
]
def worst_case(cs: list[int], n: int) -> tuple[int, int]:
"""把 cs 建成 01 字典树后自底向上求:y 能保证的最坏结果值,以及取到它的方案数。"""
kids = [[NO_CHILD, NO_CHILD]] # 结点 0 是根,结点编号大的都是后开出来的
depth = [0] # depth[u] = 走到 u 已确定的位数,即 u 所在的层
for c in cs:
u = 0
for k in reversed(range(n)): # 高位到低位
b = c >> k & 1
v = kids[u][b]
if v == NO_CHILD: # 这条边还没有,开一个新结点挂上去
v = len(kids)
kids[u][b] = v
kids.append([NO_CHILD, NO_CHILD])
depth.append(depth[u] + 1)
u = v
val = [0] * len(kids) # val[u]:只看 u 的剩余位,y 能保证的最坏结果值
cnt = [1] * len(kids) # cnt[u]:达到 val[u] 的 y 低位方案数,叶子层只剩 1 种
for u in reversed(range(len(kids))): # 子结点编号必大于父结点,逆序即自底向上
if depth[u] == n: # 叶子:C 的 n 位已定格,没有剩余位
continue
bit = 1 << n - 1 - depth[u] # 这一位在结果数值里的权重
lo, hi = kids[u]
if lo == NO_CHILD or hi == NO_CHILD:
# 只剩一棵子树:全部 C 这一位相同,y 取反位就让这一位变 1,低位在该子树里继续
only = hi if lo == NO_CHILD else lo
val[u], cnt[u] = bit + val[only], cnt[only]
elif val[lo] == val[hi]:
# 两棵子树都在:对手能把这一位压成 0;两侧最优值相同,方案数相加
val[u], cnt[u] = val[lo], cnt[lo] + cnt[hi]
else:
best = lo if val[lo] > val[hi] else hi # 这一位取更优的 y 选侧
val[u], cnt[u] = val[best], cnt[best]
return val[0], cnt[0]
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m = next(data), next(data)
a = [next(data) for _ in range(m)]
# 记 y = rol(x),则 rol 是双射,问题变成「选 y 使 min_i (y ^ C_i) 最大」,
# 求值与计数都可以在 y 上进行,不必换回 x。
value, count = worst_case(moment_consts(prefix_xors(a), n), n)
print(value)
print(count)
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* 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-10-07 15:58
* update_at: 2026-10-07 16:04
*/
// main.cpp:最大值。对手把当前值 v 变成 rol(v)(n 位循环左移一位),
// 而 rol 与异或可交换,于是每个时刻的最终值都写成 rol(x) ^ C_i;
// 问题化为「选 y 使 min_i (y ^ C_i) 最大」,用 01 字典树自底向上 DP 求解。
// 与 main.py 同一算法,结点数 O((m+1)n)、时间 O((m+1)n)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXNODE = 3000035; // 结点数上界:1 + (m+1)*n,m ≤ 100000、n ≤ 30
// 01 字典树用「动态化静态」存储:静态大数组 + node_cnt 当分配指针。
// 每个结点同时带着子树 DP 的结果,避免用多个下标平行的数组。
struct Node {
int son[2]; // 两个二进制儿子;0 表示这条边不存在(结点 0 只当空标记用)
int dep; // 深度 = 从根走到它已经确定的位数,根是 0
int val; // 只看它子树里剩下的位时,y 能保证的最坏结果值
int cnt; // 在它子树里取到 val 的 y 低位方案数
};
Node node[MAXNODE]; // node[u] 就是结点 u,按高位到低位逐层建树
int node_cnt; // 已开出的结点个数,真实结点编号是 1..node_cnt,根固定为 1
int n, m; // n 是位数,m 是异或的操作个数
int a[100005]; // 读入的 a_1..a_m,下标从 1 开始和题面对应
// 把一个数按二进制高位到低位插进 01 字典树
void insert_num(int v) {
int u = 1;
for (int k = n - 1; k >= 0; k--) {
int b = (v >> k) & 1;
if (node[u].son[b] == 0) { // 这条边还没有,就开一个新结点挂上去
node_cnt++;
node[node_cnt].son[0] = 0;
node[node_cnt].son[1] = 0;
node[node_cnt].dep = node[u].dep + 1;
node[u].son[b] = node_cnt;
}
u = node[u].son[b];
}
}
// 返回对手第 i 个时刻对应的常数 C_i = rol(pre[i]) ^ suf[i+1],
// 其中 pre 是前缀异或、suf 是后缀异或。
int moment_const(int prefix, int suffix, int full) {
int rot = ((prefix << 1) & full) | (prefix >> (n - 1)); // rol(prefix)
return rot ^ suffix;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d", &a[i]);
}
int full = (1 << n) - 1; // n 位全 1 掩码,用来把循环左移截到 n 位
// pre[i] = a_1 ^ .. ^ a_i(pre[0] = 0),suf[i] = a_i ^ .. ^ a_m(suf[m+1] = 0),
// 于是 suf[i+1] 就是第 i 个时刻之后所有数的异或。
// 对手在第 i 个时刻出手(i=0 是刚选完 x,i=m 是最后一次异或后)时,
// 最终值 = rol(x ^ pre[i]) ^ suf[i+1] = rol(x) ^ (rol(pre[i]) ^ suf[i+1]),
// 所以插入的常数就是 C_i = rol(pre[i]) ^ suf[i+1]。
vector<int> pre(m + 1, 0), suf(m + 2, 0);
for (int i = 1; i <= m; i++) {
pre[i] = pre[i - 1] ^ a[i];
}
for (int i = m; i >= 1; i--) {
suf[i] = suf[i + 1] ^ a[i];
}
node_cnt = 1;
node[1].son[0] = 0;
node[1].son[1] = 0;
node[1].dep = 0;
for (int i = 0; i <= m; i++) {
insert_num(moment_const(pre[i], suf[i + 1], full));
}
// 子结点编号一定大于父结点,所以按编号从大到小扫就是自底向上。
for (int u = node_cnt; u >= 1; u--) {
if (node[u].dep == n) { // 叶子:C 的 n 位已全部确定,没有剩余位可选
node[u].val = 0;
node[u].cnt = 1;
continue;
}
int c0 = node[u].son[0], c1 = node[u].son[1];
int bit = 1 << (n - 1 - node[u].dep); // 当前这一位在结果数值里的权重
if (c0 == 0 || c1 == 0) {
// 子树只有一个:全部 C 在这一位都相同,y 取反位就能让这一位是 1;
// 之后所有 C 都还在这个子树里,低位继续在它里面决策。
int only = c0 ? c0 : c1;
node[u].val = bit + node[only].val;
node[u].cnt = node[only].cnt;
} else if (node[c0].val == node[c1].val) {
// 两个子树:对手总能把这一位压成 0。y 选哪一侧就由异侧的子树决定低位,
// 两侧的最坏值相等,且两种 y 的这一位相反、互不重复,方案数相加。
node[u].val = node[c0].val;
node[u].cnt = node[c0].cnt + node[c1].cnt;
} else {
int best = node[c0].val > node[c1].val ? c0 : c1; // 取更优的那一侧
node[u].val = node[best].val;
node[u].cnt = node[best].cnt;
}
}
printf("%d\n%d\n", node[1].val, node[1].cnt); // rol 是双射,y 的个数就是初值 x 的个数
return 0;
}复杂度
- 时间:插入
个数、每个数走 层,DP 每个结点算一次,总时间 。 、 ,约 次操作。 - 空间:结点数不超过
。C++ 用 结构体数组(每条记录 son[2]与dep,12 字节)加两个int数组,实测峰值内存约 31 MB, 在 256 MB 限制内;没有递归,栈上只放常数。 - 与 Python 版的关系:
main.py是同一算法的 Python 实现,结点用kids[u] = [左儿子, 右儿子]的列表形式存储,DP 用两个整数列表自底向上扫一遍。 复杂度同阶,但 Python 建个嵌套列表的开销远大于 C++, CPython 下最大测例可能需要数秒且内存吃紧,存在 TLE/MLE 风险,C++ 版是安全的正解。
总结
- 先化简操作:题面里带取整与取模的式子其实只是"循环左移一位", 这一步让后面所有的位运算推理都变得可行。
- 找交换律:循环移位与异或可交换,于是"每个时刻的最终值"能统一写成
,对手的 个选择彼此独立,不再需要模拟 条不同的流水线。 - 双射换元:
是双射,因此对 统计方案数等于对 统计, 不必把答案换回 再数一遍。 - 字典树上的"对手取异侧"DP:单子树时该位必然能拿到
,双子树时该位必然被压成 、 只能看低位——这条规则同时给出了值的最优性和方案数的计数, 计数之所以能简单相加,是因为两侧的 在这一位取值相反、互不重叠。 - 复杂度只与
成正比, 、 都在掌握之中; 本题的难点全在推导,不在实现。