数学、贪心

折半是一个非常好的性质，发现有折半操作或者衰减到原来的 $\dfrac{m}{n} \ (m<n)$ 时不停执行操作直到到达问题规模下界的操作次数是对数等级的。

显然对于大于 $n$ 的偶数 $x$ 有 $a_x = a_{x+1}$，因为 $\left\lfloor \dfrac{x}{2} \right\rfloor = \left\lfloor \dfrac{x+1}{2} \right\rfloor$，考虑到异或的自反性，它们能同时给到贡献的在 $a$ 中位置更靠后的元素的值不会被它们影响。

因此得到递归式，下式中 $x$ 为偶数且满足 $n<x$，对于奇数的 $x$，直接求解 $a_{x-1}$ 即可。如果 $n$ 是偶数，那么计算 $a_{n+1}$ 的值并将其加入序列 $a$ 末尾来将 $n$ 调整为奇数。

$$a_x = \begin{cases} (\oplus_{i=1}^{\frac{x}{2} - 1} a_i) \oplus a_{\frac{x}{2}} & \frac{x}{2} \bmod 2 = 0 \\ \oplus_{i=1}^{\frac{x}{2}} a_i & \frac{x}{2} \bmod 2 = 1 \end{cases}$$

在这个式子中，一旦偶数 $i$ 满足 $i>n$ 那么 $a_i$ 和 $a_{i+1}$ 的异或和将两两抵消，可以进一步化简。

$$a_x = \begin{cases} (\oplus_{i=1}^{\min(\frac{x}{2} - 1,n)} a_i) \oplus a_{\frac{x}{2}} & \frac{x}{2} \bmod 2 = 0 \\ \oplus_{i=1}^{\min(\frac{x}{2},n)} a_i & \frac{x}{2} \bmod 2 = 1 \end{cases}$$

预处理序列前缀异或和后递归求解，总体时间复杂度 $O(n + \log V)$。

#include<bits/stdc++.h>
using namespace std;
int n,a[200'005],sum[200'005];
long long x;
int answer(long long x){
    if(x<=n) return a[x];
    if(x&1) return answer(x-1);
    x>>=1;
    if(x&1) return sum[min(x,1ll*n)];
    return sum[min(x-1,1ll*n)]^answer(x);
}
void solution(){
    cin>>n>>x>>x;
    for(int i=1;i<=n;i++) cin>>a[i];
    if(n%2==0){
        a[++n]=0;
        for(int i=1;i<=n/2;i++) a[n]^=a[i];
    }
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]^a[i];
    cout<<answer(x)<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}