最大值

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

利用循环左移与异或可交换,把对手的每个出手时刻化成常数 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

形式化题目

给定位数 nn 和 mm 个整数 a1,a2,…,ama_1, a_2, \dots, a_m(0⩽ai<2n0 \leqslant a_i < 2^n)。 先由你先选一个整数 x∈[0,2n)x \in [0, 2^n),然后对手恰好选一个时刻出手:所谓时刻是指

  • i=0i = 0:刚选完 xx,还没有异或任何数;
  • i=1,2,…,mi = 1, 2, \dots, m:已经依次异或了 a1,…,aia_1, \dots, a_i。

在第 ii 个时刻,当前值为 vi=x⊕a1⊕⋯⊕aiv_i = x \oplus a_1 \oplus \cdots \oplus a_i(i=0i = 0 时 v0=xv_0 = x), 对手把它替换成

f(v)=(⌊2v2n⌋+2v) mod 2n.f(v) = \left(\left\lfloor \frac{2v}{2^n} \right\rfloor + 2v\right) \bmod 2^n .

之后继续异或剩下的 ai+1,…,ama_{i+1}, \dots, a_m。你要让最终值尽量大,对手要让最终值尽量小, 双方都最优。求

  1. 最终值的最大值;
  2. 取到这个最大值的初值 xx 的个数。

下文记 rol(v)\mathrm{rol}(v) 为把 vv 的 nn 位二进制表示循环左移一位(n⩽30n \leqslant 30, 题面的 ff 恰好就是这个函数,推导见下)。

正解

思路

第一步:看清对手到底做了什么。 把 nn 位二进制数写成高位在前的串 v=bn−1bn−2⋯b0v = b_{n-1} b_{n-2} \cdots b_0(bn−1b_{n-1} 是最高位)。那么

⌊2v2n⌋=bn−1,2v mod 2n=bn−2⋯b00,\left\lfloor \frac{2v}{2^n} \right\rfloor = b_{n-1}, \qquad 2v \bmod 2^n = b_{n-2} \cdots b_0 0,

两者相加正好等于把最高位搬到最低位:

f(v)=rol(v)=bn−2⋯b0bn−1.f(v) = \mathrm{rol}(v) = b_{n-2} \cdots b_0 b_{n-1} .

也就是循环左移一位。这一步是最关键的观察:题面那个带取整、取模的怪式子, 其实是一个纯粹的位重排。

第二步:位重排与异或可交换。 对任意 u,vu, v 都有 rol(u⊕v)=rol(u)⊕rol(v)\mathrm{rol}(u \oplus v) = \mathrm{rol}(u) \oplus \mathrm{rol}(v): 两次异或逐位独立,而循环左移只是把位的位置整体挪动,逐位运算的结果不受位置影响。

第三步:把"时刻"化成常数。 记前缀异或 pi=a1⊕⋯⊕aip_i = a_1 \oplus \cdots \oplus a_i(p0=0p_0 = 0)、 后缀异或 si=ai+1⊕⋯⊕ams_i = a_{i+1} \oplus \cdots \oplus a_m(sm=0s_m = 0)。 若对手在第 ii 个时刻出手,则当前值 vi=x⊕piv_i = x \oplus p_i,之后剩下的数全部异或回去, 最终值为

rol(x⊕pi)⊕si=rol(x)⊕rol(pi)⊕si=y⊕Ci,y=rol(x),Ci=rol(pi)⊕si. \mathrm{rol}(x \oplus p_i) \oplus s_i = \mathrm{rol}(x) \oplus \mathrm{rol}(p_i) \oplus s_i = y \oplus C_i, \qquad y = \mathrm{rol}(x), \quad C_i = \mathrm{rol}(p_i) \oplus s_i .

对手的 m+1m+1 个选择因此完全独立于 xx:他只能在 m+1m+1 个常数 y⊕Ciy \oplus C_i 里挑一个最小的。

第四步:问题化成经典模型。 因为 x↦rol(x)x \mapsto \mathrm{rol}(x) 是 [0,2n)[0, 2^n) 上的双射 (循环移位的逆是循环右移),对 xx 求最大值数量等价于对 yy 求最大值数量。于是只需解决:

给定 m+1m + 1 个常数 C0,…,CmC_0, \dots, C_m,选 yy 使 min⁡i(y⊕Ci)\min_{i} (y \oplus C_i) 最大, 并统计这样的 yy 的个数。

第五步:01 字典树 + 逐位 DP。 把每个 CiC_i 按高位到低位插入一棵深度为 nn 的 01 字典树,则"CiC_i 的第 kk 位是 00 还是 11"就是"从根往下第 n−1−kn-1-k 层走哪条边"。 y⊕Cy \oplus C 的第 kk 位为 11 当且仅当 yy 在该位与 CC 不同;字典树的每条边恰好对应 一个固定的 (k,Ck)(k, C_k)。

设 g(u)g(u) 表示:只考虑 uu 子树里剩下的那些 CC(它们的高位已经和 yy 定好的高位一致), yy 的剩余低位能保证的最坏结果值;w(u)w(u) 是达到 g(u)g(u) 的低位方案数。 从根(深度 00,对应最高位)往下按当前位的权重 2n−1−dep2^{n-1-\mathrm{dep}} 决策:

当前结点情况 该位的结论 转移
只存在一个儿子 子树内所有 CC 的这一位相同,yy 取反位即可让它为 11 g(u)=2k+g(唯一儿子)g(u) = 2^{k} + g(\text{唯一儿子}),w(u)=w(唯一儿子)w(u) = w(\text{唯一儿子})
两个儿子都在,g(c0)≠g(c1)g(c_0) \neq g(c_1) 对手必然把这一位压成 00(总能挑到异侧子树) 取更优的那侧:g(u)=max⁡g(c)g(u) = \max g(c),w(u)w(u) 取对应侧的 ww
两个儿子都在,g(c0)=g(c1)g(c_0) = g(c_1) 同上,这一位必为 00,但两侧最坏值相同 g(u)=g(c0)g(u) = g(c_0),w(u)=w(c0)+w(c1)w(u) = w(c_0) + w(c_1)

第二个分支要解释一下:两棵子树都在时,无论 yy 的这一位取 00 还是 11,对手都能 往异侧子树里挑一个 CC,让这一位变成 00(因为异侧子树的 CC 在这一位与 yy 相反)。 所以该位对最坏值的贡献恒为 00,真正能"抢救"的只有低位——而低位由 yy 的异侧子树决定, 即 yy 选哪一侧,结果值就由另一侧子树的 gg 决定。两个选项互不影响,取 max⁡\max 即可; 两个 gg 相等时,两种 yy 的这一位相反,yy 的取值集合不相交,方案数直接相加。

叶子(深度 nn)没有剩余位,g=0g = 0、w=1w = 1;实现时按结点编号从大到小扫一遍就是自底向上 (子结点总是在父结点之后才被开出来,编号必然更大),无需递归。

样例推演。 样例 n=2,m=3n = 2, m = 3,a=(1,2,3)a = (1, 2, 3)。p=(0,1,3,0)p = (0, 1, 3, 0)、s=(0,1,3,0)s = (0, 1, 3, 0), rol\mathrm{rol} 是 2 位循环左移,算出 C0=0C_0 = 0、C1=3C_1 = 3、C2=0C_2 = 0、C3=0C_3 = 0。逐 xx 对表:

xx y=rol(x)y = \mathrm{rol}(x) 四个时刻的最终值 y⊕Ciy \oplus C_i 对手取最小值
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

最大值是 11,x=1,2x = 1, 2 都取到(正是题面样例解释里的两个初值),故输出 1 与 2。

C={0,3,0,0}C = \{0, 3, 0, 0\} 的字典树与 DP 结果:根有两个儿子(0 与 1),各自只剩一个儿子, 两个儿子的 gg 都是 11,落到"相等"分支,于是 g(根)=1g(\text{根}) = 1、w(根)=1+1=2w(\text{根}) = 1 + 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 版:

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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

  • 时间:插入 m+1m+1 个数、每个数走 nn 层,DP 每个结点算一次,总时间 O((m+1) n)O((m+1)\,n)。m⩽105m \leqslant 10^5、n⩽30n \leqslant 30,约 3×1063 \times 10^6 次操作。
  • 空间:结点数不超过 1+(m+1)n≈3×1061 + (m+1)n \approx 3 \times 10^6。C++ 用 结构体数组(每条记录 son[2] 与 dep,12 字节)加两个 int 数组,实测峰值内存约 31 MB, 在 256 MB 限制内;没有递归,栈上只放常数。
  • 与 Python 版的关系:main.py 是同一算法的 Python 实现,结点用 kids[u] = [左儿子, 右儿子] 的列表形式存储,DP 用两个整数列表自底向上扫一遍。 复杂度同阶,但 Python 建 3×1063 \times 10^6 个嵌套列表的开销远大于 C++, CPython 下最大测例可能需要数秒且内存吃紧,存在 TLE/MLE 风险,C++ 版是安全的正解。

总结

  • 先化简操作:题面里带取整与取模的式子其实只是"循环左移一位", 这一步让后面所有的位运算推理都变得可行。
  • 找交换律:循环移位与异或可交换,于是"每个时刻的最终值"能统一写成 y⊕Ciy \oplus C_i,对手的 m+1m+1 个选择彼此独立,不再需要模拟 m+1m+1 条不同的流水线。
  • 双射换元:x↦rol(x)x \mapsto \mathrm{rol}(x) 是双射,因此对 yy 统计方案数等于对 xx 统计, 不必把答案换回 xx 再数一遍。
  • 字典树上的"对手取异侧"DP:单子树时该位必然能拿到 11,双子树时该位必然被压成 00、 只能看低位——这条规则同时给出了值的最优性和方案数的计数, 计数之所以能简单相加,是因为两侧的 yy 在这一位取值相反、互不重叠。
  • 复杂度只与 m⋅nm \cdot n 成正比,m≤105m \le 10^5、n≤30n \le 30 都在掌握之中; 本题的难点全在推导,不在实现。