P10014 [集训队互测 2023] 茧 题解

max67 · 2024-01-07 21:12:14 · 题解

前言

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

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

题解

Part 0.前导

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

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

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

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

接下来默认 k\not =1。

Part 1.g(d) 的表示

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

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

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

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

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

考虑 r^{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)^{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)，讨论后面一项小于 0 的情况，有：

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

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

递归下去，记 \alpha(r) 表示 2^{\alpha(r)}|r \cap 2^{\alpha(r)+1} \nmid r，即 r 的前导 0 个数。有：

那么带回原式，可得：

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。

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

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

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

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

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

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

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

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

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

Part 2.5 \sigma(r) 的表示

若 2 \mid k，则有：

若 2 \nmid k，则有：

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

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

由于:

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

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

那么，我们能以 O(\log V) 的时间算出 h_1，那么总的时间复杂度为 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;
}

后记

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