1 条题解

  • 0
    @ 2025-8-24 22:53:54

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar max67
    bobo

    搬运于2025-08-24 22:53:54，当前版本为作者最后更新于2024-01-07 21:12:14，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    前言

    这是我写过的题中推式子过程中最长的一题，有必要写篇题解来抚慰一下心灵。

    所以说 KH 搬题为什么不把自己的题解放上去，不过可以上 QOJ 看：链接。

    题解

    Part 0.前导

    根据 SG 函数，我们定义 g(d)g(d) 为一个长度为 rr 的序列的 sgsg 值，记 h(d)=⨁i=1dg(i)h(d)=\bigoplus_{i=1}^{d}g(i) 。那么答案相当于 h(a1)⨁h(a2)...⨁h(an)h(a_1) \bigoplus h(a_2) ...\bigoplus h(a_n)。

    那么根据定义，有 g(d)=mexi=max⁡(0,r−dk)d−1g(i)g(d)=\text{mex}_{i=\max(0,r-\sqrt{d}^k)}^{d-1}g(i)。

    若 k=1k=1，根据归纳可得 g(d)=dg(d)=d。

    因此 h(d)=⨁i=1di=⨁i=0dih(d)=\bigoplus_{i=1}^{d}i=\bigoplus_{i=0}^{d}i。注意到 $(4x)\bigoplus(4x+1)\bigoplus(4x+2)\bigoplus(4x+3)=0$，（注意到末尾两位恰从 00 取到 33，而其他位不变，因此异或和为 00。），因此 $h(d)=\bigoplus_{i=4\lfloor\frac{d}{4}{\rfloor}}^{d}i=\bigoplus_{i=0}^{d\mod 4}x-i$。

    接下来默认 k≠1k\not =1。

    Part 1.g(d)g(d) 的表示

    我们统一考虑 rk≤d<(r+1)kr^{k} \le d < (r+1)^{k} 的情况，因为此时 gg 的转移式子相同。打表可知，g(d)g(d) 在 rk≤d<rk+1r^{k}\le d < r^{k+1} 是一个循环节长度为 r+1r+1 的 00 到 r−1r-1 的排列，证明如下：

    归纳设 (r−1)k≤d<rk(r-1)^{k}\le d < r^{k} 时满足条件，考虑 d=rkd=r^{k} 时的值，由于 rk−(r−1)k≥rr^{k}-(r-1)^{k} \ge r，因此 dd 的转移恰好考虑到 00 到 r−1r-1 的排列，因此 g(rk)=rg(r^k)=r，并且 rk−rr^{k}-r 到 rkr^{k} 是一个长度为 r+1r+1 的从 00 到 rr 的排列。逐项考虑可知，g(d)=g(d−r−1),rk<d<rk+1g(d)=g(d-r-1),r^{k}<d<r^{k+1}。易知也构成排列。

    我们设 g(r,d)=g(rk+d),0≤d<rk+1−rkg(r,d)=g(r^k+d),0\le d<r^{k+1}-r^{k}。由于 g(r,d)=g(r,d−r−1)=g(r,dmod  (r+1))g(r,d)=g(r,d-r-1)=g(r,d\mod (r+1))。因此我们只需考虑 0≤d<r+10\le d <r+1 的情况。

    因此我们可以初步列出转移式子：

    $$g(r,d)=\begin{cases}r,d=0\\g(r-1,d-(r+1)+r^{k}-r^{k-1}),d\not =0\end{cases} $$

    （第二个式子是因为 0<d<r+10<d<r+1，减完后 kk 次根号的值改变。又由于 rk−rk−1≥rr^{k}-r^{k-1}\ge r，因此只会减少 11。）

    考虑 rk−(r−1)kmod  rr^{k}-(r-1)^k\mod r，有：

    $$r^{k}-(r-1)^{k} = r^{k}-\sum_{i}C_{k-1}^{i}(-1)^{k-i}r^i \pmod r $$=0−(−1)kCk0r0=(−1)k+1(modr)=0-(-1)^{k}C_{k}^{0}r^{0} = (-1)^{k+1}\pmod r

    因此 $g(r-1,d-(r+1)+r^{k}-r^{k-1}\mod r)=g(r-1,(d-1+(-1)^{k+1} \mod r)$，讨论后面一项小于 00 的情况，有：

    $$g(r,d)= \begin{cases} r,d=0\\ g(r-1,d\mod r ),2 \nmid k\\ g(r-1,r-1),2 \mid k,d=1\\ g(r-1,(d-2)\mod r), 2\mid k,d\ge 2 \end{cases} $$

    注意到当 2∤k2\nmid k 时， g(r,d)=g(r−1,dmod  r)g(r,d)=g(r-1,d\mod r)，由于 r≥dr\ge d，因此 g(r,d)=g(d,d)=g(d−1,dmod  d)=d−1g(r,d)=g(d,d)=g(d-1,d\mod d)=d-1

    当 2∣k2\mid k 时，注意到 $g(r-1,(d-2)\mod r)=g(r-\lfloor\frac{d}{2}\rfloor,d\mod 2)$，因此考虑暴力展开。注意到第二项只会是 0/10/1，那么讨论 g(r,1)g(r,1) 的情况，有：

    $$g(r,1)=g(r-1,r-1)=g(r-1-\lfloor\frac{r-1}{2}\rfloor , (r-1) \mod 2)=g(\lceil \frac{r-1}{2}\rceil , (r+1) \mod 2) $$=g(⌊r2⌋,(r+1)mod  2)=g(\lfloor\frac{r}{2}\rfloor,(r+1)\mod 2) $$=\begin{cases} \lfloor\frac{r}{2}\rfloor,2\nmid r\\ g(\lfloor\frac{r}{2}\rfloor,1),2\mid r\\ \end{cases} $$

    递归下去，记 α(r)\alpha(r) 表示 2α(r)∣r∩2α(r)+1∤r2^{\alpha(r)}|r \cap 2^{\alpha(r)+1} \nmid r，即 rr 的前导 00 个数。有：

    g(r,1)=⌊r2α(r)+1⌋,g(r,1)=\lfloor\frac{r}{2^{\alpha(r)+1}}\rfloor,

    那么带回原式，可得：

    $$g(r,d)= \begin{cases} r,d=0\\ d-1,2 \nmid k\\ \lfloor\frac{r}{2^{\alpha(r)+1}}\rfloor,2 \mid k,d=1\\ g(r-\lfloor\frac{d}{2}\rfloor,d\mod 2), 2\mid k,d\ge 2 \end{cases} $$

    Part 1.5 辅助数组计算

    定义辅助函数：$h_0(r)=\bigoplus_{i=0}^{r}i,h_1(r)=\bigoplus_{i=0}^{r}g(i,i)=\bigoplus_{i=1}^{r+1}\lfloor\frac{i}{2^{\alpha(i)+1}}\rfloor=\bigoplus_{i=0}^{r+1}\lfloor\frac{i}{2^{\alpha(i)+1}}\rfloor$。

    考虑快速求出辅助函数的值，其中 h0(x)=h(x)h_0(x)=h(x)，而对于 h1h_1，我们尝试用递归的方式计算，具体的，我们发现我们可以直接计算 ii 为奇数的值，而对于 ii 为偶数，则令他们变成 ⌊i2⌋\lfloor\frac{i}{2}\rfloor 递归计算。因此：

    $$h1(r)=\bigoplus_{i=0}^{\lfloor\frac{r+1}{2}\rfloor}\lfloor\frac{i}{2^{\alpha(i)+1}}\rfloor\bigoplus_{i=0}^{\lfloor\frac{r}{2}\rfloor}i $$$$=h1(\lfloor\frac{r-1}{2}\rfloor)h0(\lfloor\frac{r}{2}\rfloor) $$

    Part 2.s(r)s(r) 的表示

    注意到我们需要计算前缀和，因此记 $s(r,d)=\bigoplus_{i=0}^{d}g(r,i),s(r)=s(r,(r+1)^{k}-r^k-1),\sigma (r)=\bigoplus_{i=0}^{r}s(r)$，我们需要快速计算这些值。

    先考虑计算 s(r)s(r)。因为 g(r,d)g(r,d) 有长度为 r+1r+1 的循环节，根据异或的特性，显然有 s(r,d)=s(r,d−2∗(r+1))s(r,d)=s(r,d-2*(r+1))。那么我们先考虑计算 dd 的循环节数量的奇偶性。注意到 (r+1)k−(r)k=(−1)k+1(modr+1)(r+1)^{k}-(r)^{k}=(-1)^{k+1}\pmod {r+1}。这表明 s(r)s(r) 恰好是由若干个循环节再加上或减去一个数异或而成的：若 2∤k2 \nmid k，正好多了 g(r,0)g(r,0)；若 2∣k2 \mid k，正好少了 g(r,r)g(r,r)。

    接下来计算循环节数量的奇偶性。我们考虑补上或删去一个数使得整个序列恰好有很多个循环节组成。因此：

    (r+1)k−rk−(−1)k+1r+1=\frac{(r+1)^{k}-r^{k}-(-1)^{k+1}}{r+1} = $$=\frac{(r+1)^{k}-(-1)^{k+1}-\sum_{i}C_{k}^{i}(-1)^{k-i}(r+1)^{i}}{r+1} $$$$=(r+1)^{k-1} - \sum_{i>0}C_{k}^{i}(-1)^{k-i}(r+1)^{i-1} -\frac{(-1)^{k+1}+(-1)^{k}}{r+1} $$$$=(r+1)^{k-1}-\sum_{i>0}C_{k}^{i}(-1)^{k-i}(r+1)^{i-1} $$

    （考虑用二项式展开凑出 r+1r+1 的因子化简）

    注意我们要计算奇偶性，那么考虑原式子模 22 的值。注意到若 k>0k>0，有 xk=x(mod2)x^{k} =x \pmod 2，并且 a+b=a−b(mod2)a+b=a-b \pmod 2，因此，式子等于：

    $$=(r+1) +\sum_{i>1}C_{k}^{i}(r+1)+C_{k}^{1} \pmod 2 $$

    注意到 Lucas 定理的特例，Cnm=[m⊂n](mod2)C_{n}^{m}= [m\subset n] \pmod 2，因此：

    $$=(r+1) +\sum_{i>1}[i\subset k](r+1)+C_{k}^{1} \pmod 2 $$$$=r+k+1+(2^{\text{popcount}(k)}-2)(r+1)=r+k+1 \pmod 2 $$

    （其中 popcount(x)\text{popcount}(x) 表示 xx 的 11 的个数，由于 k>1k>1，因此此项一定为偶数）

    分类讨论，可知 r+k+1=rk(mod2)r+k+1 = rk \pmod 2。因此：

    $$s(r)=\begin{cases} g(r,r),2\mid k\\ g(r,0),2\nmid k,2\mid r\\ g(r,0)\bigoplus h_0(r),2\nmid k,2\nmid r \end{cases} $$

    因为第三项转移保证 2∤r2 \nmid r，因此式子可以写成：

    $$s(r)=\begin{cases} g(r,r),2\mid k\\ r,2\nmid k,2\mid r\\ r\bigoplus [r\mod 4 =1],2\nmid k,2\nmid r \end{cases} $$

    Part 2.5 σ(r)\sigma(r) 的表示

    若 2∣k2 \mid k，则有：

    $$\sigma(r)=\bigoplus_{i=0}^{r}s(i)=\bigoplus_{i=0}^{r}g(i,i)=h1(r),2\mid k $$

    若 2∤k2 \nmid k，则有：

    $$\sigma(r)=\bigoplus_{i=0}^{r}s(i)=\bigoplus_{i=0}^{r}g(i,0)\bigoplus_{i=0}^{\lfloor\frac{r-1}{2}\rfloor}[2i+1\mod 4 =1] $$

    注意到只有 1,5,9...4k+11,5,9...4k+1 才会对 [2i+1mod  4=1][2i+1\mod 4=1] 产生贡献，那么此时后面式子的异或和形成了长度为 88 的循环节，并且只有落在 1,51,5 中间时异或值才为 11，有：

    =h0(r)⨁[1≤rmod  8≤4]=h0(r)\bigoplus [1\le r\mod 8 \le 4]

    Part 3. s(r,d)s(r,d) 的表示

    由于:

    $$g(r,d)= \begin{cases} r,d=0\\ d-1,2 \nmid k\\ \lfloor\frac{r}{2^{\alpha(r)+1}}\rfloor,2 \mid k,d=1\\ g(r-\lfloor\frac{d}{2}\rfloor,d\mod 2), 2\mid k,d\ge 2 \end{cases} $$

    那么考虑暴力展开后递归：（2∣k2\mid k）

    s(r,d)=⨁i=0dg(r,d),0≤d≤rs(r,d) = \bigoplus_{i=0}^{d}g(r,d), 0\le d \le r $$=\bigoplus_{i=0}^{d}g(r-\lfloor\frac{d}{2}\rfloor,d\mod 2) $$$$=\bigoplus_{i=0}^{\lfloor\frac{d}{2}\rfloor}g(r-\lfloor\frac{d}{2}\rfloor,0)\bigoplus_{i=0}^{\lfloor\frac{d}{2}\rfloor-[2\mid d]}g(r-\lfloor\frac{d}{2}\rfloor-1,r-\lfloor\frac{d}{2}\rfloor-1) $$$$=h0(r)\bigoplus h0(r-\lfloor\frac{d}{2}\rfloor-1)\bigoplus h1(r-1)\bigoplus h1(r-\lfloor\frac{d-1}{2}\rfloor-2) $$$$=h0(r)\bigoplus h0(r-\lfloor\frac{d}{2}\rfloor-1)\bigoplus h1(r-1)\bigoplus h1(r-\lfloor\frac{d+1}{2}\rfloor-1) $$

    若 2∤k2\nmid k，因为 g(r,d)=d−1g(r,d)=d-1（d>0d>0），显然有 $s(r,d)=g(r,0)\bigoplus g(r,1..d)= r\bigoplus h0(d-1),2\nmid k,d=1$。因此结合起来，有：

    $$s(r,d)=\begin{cases} h0(r)\bigoplus h0(r-\lfloor\frac{d}{2}\rfloor-1)\bigoplus h1(r-1)\bigoplus h1(r-\lfloor\frac{d+1}{2}\rfloor-1),2\mid k\\ d,2\nmid k,d=0\\ r\bigoplus h0(d-1),2\nmid k,d=1\\ \end{cases} $$

    那么，我们能以 O(log⁡V)O(\log V) 的时间算出 h1h_1，那么总的时间复杂度为 O((s+log⁡V)Tn)O((s+\log V)Tn)。

    Part 4.实现

    #include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=5e5+100;
int k;
int a[N];
int power(int x,int y){int t=1;for(;y;y>>=1,x=x*x)if(y&1)t=t*x;return t;}
int h0(int x){int res=0;for(int i=0;i<=x%4;i++)res^=x-i;return res;}
int h1(int x){if(x<=1)return 0;return h1((x-1)/2)^h0(x/2);}
int s(int r,int d)
{
	if(d>2*r+2)d%=2*r+2;
	if(d>r)return h0(r)^s(r,d-r-1);
	if(k%2==0)return h0(r)^h0(r-(d/2)-1)^h1(r-1)^h1(r-(d+1)/2-1);
	if(d==0)return r;
	return r^h0(d-1);
}
int sigma(int x){if(!x)return 0;if(k%2==0)return h1(x);return h0(x)^(1<=x%8&&x%8<=4?1:0);}
int solve(int x)
{
	if(k==1)return h0(x);
	int r=pow(x,1.0/k);
	while(power(r,k)>x)r--;while(power(r+1,k)<=x)r++;
	return sigma(r-1)^s(r,x-power(r,k));
}
signed main()
{
	int _;scanf("%lld%lld",&_,&k);
	while(_--)
	{
		int t,res=0,x;scanf("%lld",&t);
		while(t--)scanf("%lld",&x),res^=solve(x);
		puts(res?"Lily":"Kaguya");
	}
	return 0;
}

    后记

    赛场上还是有不少巨佬过这题的，我觉得他们可能是能打表出 σ(r)\sigma(r) 的规律（形式简洁），对于 2∤k2\nmid k 的情况，打表发现 g(r,d)g(r,d) 呈现 log⁡\log 段公差为 11 的等差数列，再暴力计算。

    • 1

    [集训队互测 2023] 茧

    信息

    ID
    9617
    时间
    1000ms
    内存
    512MiB
    难度
    7
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 42ms