[DSTOI Round 0 F] 万分之一的光 题解
MoLing_qwq
·
·
题解
题意
有一个序列 a。递归地，定义「过程 \bold{n}」（其中 n 为正整数）为依次执行如下操作：
- 向序列 a 的末尾添加一个 n。
- 如果 n>1，执行「过程 \bold{n-1}」。
- 如果 n>2，执行「过程 \bold{n-2}」。
给定正整数 n。初始 a=[0]。执行「过程 \bold{n}」后，设得到的 a=[a_1,a_2,\dots,a_m]。
对于 i=2,3,\dots,m，定义 b_i=a_{i-1}+a_i，求 b_2,b_3,\dots,b_m 的异或和 S。
多测，T\le 10^3，n\le 10^{18}。
题解
我们先忽略序列 a 开头的 0。 记 n=k 时的答案为 S_k，序列 a 去掉首项为 a_{(k)}。递归的过程启示我们进行 DP。
推式子
以下默认 k 为较大的正整数，即暂不考虑边界。由题 a_{(k)} 是 [k]+a_{(k-1)}+a_{(k-2)}，加号表示序列的拼接。设 S(a) 为 a_{i-1}+a_i（i=2,3,\dots,|a|）的异或和，则：
$$
S(a_{(k)})=(k+k-1)\operatorname{xor}S(a_{(k-1)})\operatorname{xor}(1+k-2)\operatorname{xor}S(a_{(k-2)})
$$
异或有性质 $a\operatorname{xor}a=0$，这将不断帮我们化简式子。
代入 $S_k=S(a_{(k)})\operatorname{xor}k$：
$$
(S_k\operatorname{xor}k)=(2k-1)\operatorname{xor}(S_{k-1}\operatorname{xor}(k-1))\operatorname{xor}(k-1)\operatorname{xor}(S_{k-2}\operatorname{xor}(k-2))
$$
整理一下：
$$
S_k=S_{k-1}\operatorname{xor}S_{k-2}\operatorname{xor}k\operatorname{xor}(k-2)\operatorname{xor}(2k-1)
$$
直接递推是 $O(n)$，然而不能通过。
考虑迭代一次：在 $S_k$ 的式子中代入 $S_{k-1}$。
$$
S_{k-1}=S_{k-2}\operatorname{xor}S_{k-3}\operatorname{xor}(k-1)\operatorname{xor}(k-3)\operatorname{xor}(2k-3)
$$
$$
S_k=(S_{k-2}\operatorname{xor}S_{k-3}\operatorname{xor}(k-1)\operatorname{xor}(k-3)\operatorname{xor}(2k-3))\operatorname{xor}S_{k-2}\operatorname{xor}k\operatorname{xor}(k-2)\operatorname{xor}(2k-1)
$$
$$
S_k=S_{k-3}\operatorname{xor}k\operatorname{xor}(k-1)\operatorname{xor}(k-2)\operatorname{xor}(k-3)\operatorname{xor}(2k-1)\operatorname{xor}(2k-3)
$$
发现 $S_{k-2}$ 也被消去了，递归从二叉式变成链式，很好。直接递归地展开式子，可以看到出现了一堆公差为 $3/6$ 的等差数列的异或和。
于是要解决的核心问题转化为：对于一个 $x$，求
$$
f(x)=\operatorname{xor}_{n\ge 0,x-3n>0}(x-3n)
$$
### DP
考虑数位 DP。设 $dp_{i,k}$ 为所有 $<2^i$ 且模 $3$ 余 $k$ 的自然数的异或和。转移就是把 $[0,2^i)$ 拆成 $[0,2^{i-1})$ 和 $[2^{i-1},2^i)$，后半段去掉最高位，那么两段都是子问题。
求 $f(x)$ 时，可以把 $[0,x)$ 拆成 $O(\log x)$ 段形如 $[2^{s+1}t,2^{s+1}(t+1))$ 的区间，即固定最高的几个二进制位，求出这些区间中与 $x$ 模 $3$ 同余的数的异或和。这是容易的：拆成固定的最高的几位，与其余的低位，利用 $dp$ 数组计算即可。
实现时注意两点：
第一，对于
$$
(2k-1)\operatorname{xor}(2(k-3)-1)\operatorname{xor}(2(k-6)-1)\operatorname{xor}\dots
$$
这样的式子，可以先把最低位的贡献算掉（如果有奇数项则造成异或 $1$ 的贡献），然后式子化成
$$
2(k-1)\operatorname{xor}2(k-4)\operatorname{xor}2(k-7)\operatorname{xor}\dots
$$
$$
2((k-1)\operatorname{xor}(k-4)\operatorname{xor}(k-7)\operatorname{xor}\dots)
$$
就可以计算了。
第二，**递推需要特别注意边界**。尤其是，每次计算
$$
k\operatorname{xor}(k-3)\operatorname{xor}(k-6)\operatorname{xor}\dots
$$
时，仔细检查是异或到哪个数结束。
$$
f(x)=\operatorname{xor}_{n\ge 0,x-3n>\color{red}{0}}(x-3n)
$$
有时直接用 $f(x)$ 会多算，记得减掉多余的贡献。
时间复杂度 $O(T\log n)$。
::::info[Code std]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int T;ll n,dp[64][3],ans;
ll calc(ll n){
ll d=n%3,s=0,res=0;
for(int i=60;i>=0;--i)if((n>>i)&1){
res^=dp[i][d];
if((((1ll<<i)+2-d)/3)&1)res^=s;
d=(d-(1ll<<i)%3+3)%3;
s=s+(1ll<<i);
}
return res^n;
}
int main(){
for(int i=1;i<=60;++i)for(int j=0;j<3;++j){
dp[i][j]=dp[i-1][j]^dp[i-1][(j-(1ll<<(i-1))%3+3)%3];
if((((1ll<<i)+2-j)/3-((1ll<<(i-1))+2-j)/3)&1)dp[i][j]^=(1ll<<(i-1));
}
scanf("%d",&T);
while(T--){
scanf("%lld",&n);
if(n<=3){puts(n==3?"7":"1");continue;}
ans=n^calc(n-1)^calc(n-2)^(calc(n-1)<<1)^(calc(n-2)<<1)^1;
if(n%3)ans^=1;
printf("%lld\n",ans);
}
return 0;
}
```
::::
## 题目定位
本题预估难度 **提高+/省选-**，要求选手从递归的结构想到动态规划，熟练使用数位 DP 解决问题；要求选手有一定数列处理的能力；还需要一点细心。