题解：P11278 绝世丑角

一篇注重证明的题解。

Nimber 积科普题。首先，不难看出这是一道线段树题。我们在此列出作为一个线段树能维护的代数结构：

两个幺半群 M_1, M_2，附加幺半群同态 M_1 \to \mathrm{End}_{\sf Mon}(M_2)。此时，M_1 被称为 lazytag 类型，M_2 被称为节点类型。

换句话说：你的节点类型存在一种拼接组合的方式，它满足结合律，且存在一个 identity tag e 使得 f \cdot e = e \cdot f = f；你的 lazytag 类型 f \in M_1 应该满足结合律、且存在一个不进行作用的 tag（幺元），并且可以将其作用在一个节点 m \in M_2 上，得到 f(m)。这样的节点是可以分裂的，也就是说如果 m = m_1 \cdot m_2，则 f(m) = f(m_1) \cdot f(m_2)。

后文，记 *_n 为某个 < n 的自然数，例如异或的定义可以写为：

n \oplus m = \mathrm{mex}\{n \oplus *_m, m \oplus *_n\},

同时 \{0, 1, \dots, n - 1\} 可以写为 \{ *_n \}。

观察 Nimber 积的定义发现，如果我们按照 von Neumann 的自然数构造，认为 n = \{*_n\} 的话，则我们实际上可以把 Nimber 积推广到任意的集合上：

\begin{aligned} S \oplus T = \{\sigma \oplus T, S \oplus \tau \mid \sigma \in S, \tau \in T\}; \\ S \otimes T = \{\sigma \otimes T \oplus S \otimes \tau \oplus \sigma \otimes \tau \mid \sigma \in S, \tau \in T\}. \end{aligned}

考虑 Nimber 积

n \otimes m = \mathrm{mex}\{ n \otimes *_m \oplus *_n \otimes m \oplus *_n \oplus *_m \}

的代数性质：

• 如果 \mathrm{mex}(S) = n, \mathrm{mex}(T) = m，则 \mathrm{mex}(S \oplus T) = n \oplus m, \mathrm{mex}(S \otimes T) = n \otimes m。
• 若 x, y \ne 0，则 x \otimes y \ne 0。

（证明均为展开定义。）另外，我们暂且承认若 x, y < 2^{2^N}，则 x \otimes y < 2^{2^N}。这些点告诉我们：

定理. 设 1 \le x < 2^{2^N}，则存在 y，使得 x \otimes y = 1。换句话说，\{*_{2^{2^N}}\} 是域（本文很少会用到抽象代数知识，放心阅读）。

证明. 设 S = [1, 2^{2^N}) \cap \mathbb Z，固定 x \in S，则考虑映射 f_x : S \to S：a \mapsto x \otimes a。我们发现：f_x 是单射，这是因为 x \otimes a=x \otimes b \implies x \otimes (a \oplus b) = 0 \implies x = 0 或 a \oplus b = 0，而 x \ne 0 导出 a = b。根据小学奥数中的鸽巢原理，f_x 是双射。取 y = f_x^{-1}(1) 即可。

定理. \{*_{2^{2^N}}\} 存在原根。换句话说，存在一个 g，使得 \{1, g, g^2, \dots, g^{2^{2^N}-2}\} = [1, 2^{2^n})，其中 g^k 指的是

\underset{k}{\underbrace{g \otimes \dots \otimes g}}.

证明. 引入概念：称 \omega \in \mathbb C 是 n 次本原单位根，若 \min\{k \in \mathbb Z_{> 0} : \omega^k = 1\} = n。定义分圆多项式为

\Phi_n(z) = \prod_{\omega : n~\text{次本原单位根}} (z-\omega).

于是断言：\Phi_n 的每一个多项式系数均为整数。

证明：根据 Möbius 反演的乘性版本，有

\Phi_n(z) = \prod_{d \mid n} (z^d - 1)^{\mu(n / d)},

所以 \Phi_n 的每一个多项式系数均为有理数。

引入符号 \gcd(f) 代表 f 的多项式系数的最大公约数（最大公约数一个概念可以平凡地延拓到有理数上），则我们有 Gauß 引理：\gcd(fg) = \gcd(f) \cdot \gcd(g)（证明：不妨设 \gcd(f) = \gcd(g) = 1，则 f, g 均是整系数多项式，所以 \gcd(fg) 是整数；而若素数 p \mid \gcd(fg)，则 (fg) \bmod p = 0，而 f \bmod p 和 g \bmod p 均不等于 0，导出矛盾。）

现在我们证明更强的命题：\gcd(\Phi_n) = 1。进行归纳，则 n = 1 \implies \Phi_1(z) = z - 1，因此命题成立；根据分圆多项式的定义，有

z^n - 1 = \Phi_n(z) \cdot \prod_{d < n} \Phi_d(z) = \Phi_n(z) \cdot R(z),

根据 Gauß 引理，\gcd(R) = 1，因此 \gcd(\Phi_n) = 1。完成归纳。

现在，我们设 \Psi_n = \Phi_n \bmod 2。这样，我们有

\prod_{d \mid n} \Psi_d(X) \equiv X^n - 1 \pmod 2,

所以，如果我们设 Nimber 上的 \oplus 为加法，\otimes 为乘法，则 \Psi_n(m) = 1 当且仅当 m 是 Nimber 中的 n 次本原单位根。对 \Psi_n 在 Nimber 中因式分解得 n 次本原单位根至多有 \varphi(n) 个，设这个个数为 c_n。因此，我们有

2^{2^N}-1 = \sum_{d \mid (2^{2^N} - 1)} c_d \le \sum_{d \mid (2^{2^N} - 1)} \varphi(d) = 2^{2^N}-1,

由于两边相等，所以不等号取等，所以 c_d = \varphi(d)，进而，c_{2^{2^N}-1} \ne 0。

注：N = 4 时，一个可能的原根取值为 2\ 024。

推论 (Fermat 小定理). 设 n < 2^{2^N}，则 n^{2^{2^N}} = n。

现在，回归题目。在题目中，我们每次操作进行一次平方。这样，平方 2^N 次后我们将回归原状。考虑维护的节点类型为 2 \times 2^N 个数 (\Sigma_k, O_k)，其中 \Sigma_k 代表对这个区间进行平方操作 k 次的和，而 O_k 代表对这个区间进行平方操作 k 次的异或（i.e. Nim 和）。这样，lazytag 就无非是操作次数（属于 [0, 31)）。

于是，我们得到了一个问题：如何切实地计算 Nimber 平方？解法是：观察到平方是线性的，也就是说

(a \oplus b) \otimes (a \oplus b) = a \otimes a \oplus b \otimes b.

这样我们只需要预处理出 2^k 的 Nimber 平方即可。于是我们就成功地，做完了。

补充证明. 我们还没有证明若 x, y < 2^{2^N}，则 x \otimes y < 2^{2^N} 啊喂！首先，我们引入一个映射 \wp : x \mapsto x^2+x，它是线性的。我们尝试利用这个映射，从 \{*_2\} 这个最小的域开始慢慢搭建更大的域。

设我们已知 \mathbb F = \{*_m\} 是域，我们想要证明 \{*_{m^2}\} 是域。我们现在可以证明，n < m，则 n \otimes m = n \cdot m，其中等号右面是通常意义的积（*_n \otimes m 是归纳假设，(n \oplus *_n) \otimes *_m 是一个求逆的问题）。我们说明 \wp(m) 恰好是 \mathrm{mex}\{\wp(\mathbb F)\}：这是因为我们可以用归纳法证明 \wp(\mathbb F) 是一个区间，而这个归纳法恰在 m 处失效。这样我们就证完了。

这一定理被称为扩张定理。

代码环节：

#include <bits/stdc++.h>
using namespace std;

/* code of lazy_segtree copied from Atcoder Library. */

namespace Nimber {
using nim = unsigned int;

array<nim, 32> square_table = {
    1u,          3u,         6u,         13u,        24u,        52u,
    103u,        222u,       384u,       832u,       1648u,      3552u,
    6237u,       13563u,     26511u,     56906u,     98304u,     212992u,
    421888u,     909312u,    1596672u,   3472128u,   6786816u,   14567936u,
    25190110u,   54589881u,  108036850u, 232800673u, 408783316u, 888883132u,
    1737454078u, 3729449897u};

nim square(nim x) {
    nim ret = 0;
    for (int i = 0; i < 32; i++)
        if (x & (1u << i)) ret ^= square_table[i];
    return ret;
}

}  // namespace Nimber

namespace Used_for_lazyseg {
const size_t Repetition = 32;

struct Node {
    array<int64_t, Repetition> sum;
    array<Nimber::nim, Repetition> nim_sum;
};

Node merge(Node a, Node b) {
    Node ret;
    transform(a.sum.begin(), a.sum.end(), b.sum.begin(), ret.sum.begin(),
              plus<>());
    transform(a.nim_sum.begin(), a.nim_sum.end(), b.nim_sum.begin(),
              ret.nim_sum.begin(), bit_xor<>());
    return ret;
}

Node identity_nd() { return {{}, {}}; }

using Lazy = size_t;

Lazy composite(Lazy a, Lazy b) { return (a + b) % Repetition; }

Lazy identity_lz() { return 0; }

Node apply(Lazy a, Node b) {
    rotate(b.sum.begin(), b.sum.begin() + a, b.sum.end());
    rotate(b.nim_sum.begin(), b.nim_sum.begin() + a, b.nim_sum.end());
    return b;
}

Node get(Nimber::nim x) {
    array<int64_t, Repetition> sum;
    array<Nimber::nim, Repetition> nim_sum;
    sum[0] = nim_sum[0] = x;
    for (int i = 1; i < Repetition; i++)
        sum[i] = nim_sum[i] = Nimber::square(sum[i - 1]);
    return {sum, nim_sum};
}

using Seg =
    lazy_segtree<Node, merge, identity_nd, Lazy, apply, composite, identity_lz>;

}  // namespace Used_for_lazyseg

int main() {
    int n, q;
    cin >> n >> q;
    vector<Nimber::nim> a(n);
    for (auto& i : a) cin >> i;
    Used_for_lazyseg::Seg seg(n);
    for (int i = 0; i < n; i++) seg.set(i, Used_for_lazyseg::get(a[i]));
    while (q--) {
        int op, x, y;
        cin >> op >> x >> y;
        x--;
        if (op == 1)
            seg.apply(x, y, 1);
        else if (op == 2)
            cout << seg.prod(x, y).nim_sum[0] << endl;
        else
            cout << seg.prod(x, y).sum[0] << endl;
    }
}