题解：P16258 [DSTOI Round 0] 万分之一的光

· · 题解

题意简述

过程 n 会先把 n 加入序列，再依次执行过程 n-1 和过程 n-2。初始序列含有一个 0。

求最终序列中所有相邻两项之和的异或和。每个测试点有多组数据，且 n\le10^{18}。

解题思路

记过程 n 自身生成的序列为 P_n，不包含开头额外的 0。再记 P_n 内部所有相邻两项之和的异或和为 X_n。

由递归定义可知，P_n 的第一项为 n，最后一项始终为 1。当 n\ge3 时，序列满足：

P_n=[n]+P_{n-1}+P_{n-2}

除了两个子序列内部的贡献，还要计算两处拼接位置。n 与 P_{n-1} 的首项之和为 2n-1，P_{n-1} 的末项与 P_{n-2} 的首项之和为 n-1。因此：

X_n=X_{n-1}\mathbin{\operatorname{xor}}X_{n-2}\mathbin{\operatorname{xor}}(2n-1)\mathbin{\operatorname{xor}}(n-1)

把 X_{n-1} 的同类递推式代入，上式中的两个 X_{n-2} 会相互抵消，得到：

X_n=X_{n-3}\mathbin{\operatorname{xor}}(2n-1)\mathbin{\operatorname{xor}}(2n-3)\mathbin{\operatorname{xor}}(n-1)\mathbin{\operatorname{xor}}(n-2)

令 k=n-1，并令 l=\operatorname{lowbit}(k)。二进制中，k 与 k-1 从最低位 1 开始的后缀全部相反，所以：

k\mathbin{\operatorname{xor}}(k-1)=2l-1

同时，2k+1 与 2k-1 的最低位都是 1，去掉这一位后分别为 k 与 k-1。于是：

\begin{aligned} & (2k+1)\mathbin{\operatorname{xor}}(2k-1)\mathbin{\operatorname{xor}}k\mathbin{\operatorname{xor}}(k-1) \\ & =(4l-2)\mathbin{\operatorname{xor}}(2l-1) \\ & =2l+1 \end{aligned}

递推式因而化为：

X_n=X_{n-3}\mathbin{\operatorname{xor}}\left(2\operatorname{lowbit}(n-1)+1\right)

直接计算可得 X_1=0、X_2=3、X_3=4。将递推式按下标每次减少 3 展开，可以统一写成：

X_n=[3\mid n]\mathbin{\operatorname{xor}}\mathop{\operatorname{xor}}_{\substack{1\le k<n\\k\equiv n-1\pmod 3}}\left(2\operatorname{lowbit}(k)+1\right)

其中 [3\mid n] 在 3 整除 n 时为 1，否则为 0。开头额外的 0 与 P_n 的第一项 n 还产生一个贡献 n，所以最终答案为 n\mathbin{\operatorname{xor}}X_n。

下面快速计算式中的异或和。

令 w=n-1。对每个非负整数 i，记 r_i 为满足以下条件的 k 的数量：

r_i=\#\{k\mid 1\le k\le w, k\equiv w\pmod 3, 2^i\mid k\}

最低位恰为 2^i 的数共有 r_i-r_{i+1} 个。若只保留这些数量的奇偶性，所有最低位贡献可以整理为：

\begin{aligned} & \mathop{\operatorname{xor}}_i[(r_i-r_{i+1})\bmod2]\left(2^{i+1}+1\right) \\ & =\mathop{\operatorname{xor}}_i[r_i\bmod2]\left(2^{i+1}\mathbin{\operatorname{xor}}2^i\right) \\ & =\mathop{\operatorname{xor}}_i[r_i\bmod2]\left(3\cdot2^i\right) \end{aligned}

因此，只需分别求出每个 r_i 的奇偶性。

令 k=2^iq，并设 m=\lfloor w/2^i\rfloor。因为 2^i 在模 3 意义下的逆元随 i 的奇偶性交替为 1,2，所以 q 应满足：

q\equiv \rho_i\pmod 3

其中：

\rho_i= \begin{cases} w\bmod3 & i\text{ 为偶数} \\ 2w\bmod3 & i\text{ 为奇数} \end{cases}

区间 1\le q\le m 中符合条件的数有：

r_i= \begin{cases} \left\lfloor\frac{m}{3}\right\rfloor & \rho_i=0 \\ \left\lfloor\frac{m+3-\rho_i}{3}\right\rfloor & \rho_i>0 \end{cases}

由于 n<2^{60}，枚举 i=0,1,\dots,59 即可。若 r_i 为奇数，就把 3\cdot2^i 异或进答案。

单组数据的时间复杂度为 O(\log n)，空间复杂度为 O(1)。

参考代码

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

using ull=unsigned long long;
ull solve(ull n)
{
    ull w=n-1;
    ull ans=n;
    if(n%3==0)ans^=1;
    for(int i=0;i<60;i++)
    {
        ull m=w>>i;
        int r=w%3*(i&1?2:1)%3;
        ull cnt;
        if(r==0)cnt=m/3;
        else cnt=(m+3-r)/3;
        if(cnt&1)ans^=3ull<<i;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        ull n;
        cin>>n;
        cout<<solve(n)<<'\n';
    }
    return 0;
}