【MX-X9-T2】『GROI-R3』XOR
题目要求求区间异或和，先转化成前缀异或和。
从 \(0\) 到 \(n\) 的异或和是有规律的。
令 \(F(n)=0\oplus1\oplus\cdots\oplus n\)，则有：
\[F(n)=\begin{cases} n,&n\equiv 0\pmod4,\\ 1,&n\equiv 1\pmod4,\\ n+1,&n\equiv 2\pmod4,\\ 0,&n\equiv 3\pmod4.
\end{cases}
\]
题目要求 \(F(n)\oplus F(k-1)=x\)，可转化为 \(F(n)=x\oplus F(k-1)\)。令 \(t=x\oplus F(k-1)\)，也就是说我们要找到一个 \(n\in[l,r]\)，使得 \(F(n)=t\)。
下面我们分类讨论：
- 当 \(n\equiv 0\pmod4\) 时：\(F(n)=n \Rightarrow n=T(T\equiv 0\pmod4)\)。
- 当 \(n\equiv 1\pmod4\) 时：\(F(n)=1 \Rightarrow T=1\)。
- 当 \(n\equiv 2\pmod4\) 时：\(F(n)=n+1 \Rightarrow n=T-1(T\equiv 3\pmod4)\)。
- 当 \(n\equiv 3\pmod4\) 时：\(F(n)=0 \Rightarrow T=0\)。
因此：
- 如果 \(T=1\)，则只要在区间内存在 \(n\equiv1\pmod4\) 的数即可。我们可以选区间内最小的 \(n\equiv1\pmod4\)。
- 如果 \(T=0\)，则必须选 \(n\equiv3\pmod4\)，选区间内最小的 \(n\equiv3\pmod4\)。
- 如果 \(T\not\in\{0,1\}\)：
- 若 \(T\equiv0\pmod4\)，则必须有 \(n=T\)，检查 \(T\in[l,r]\)；
- 若 \(T\equiv3\pmod4\)，则必须有 \(n=T-1\)，检查 \(T-1\in[l,r]\)；
- 其他情况无解。
参考代码
#include<iostream>
using namespace std;
int T,l,r,k,x;
int get(int x){if(x%4==0) return x;if(x%4==1) return 1;if(x%4==2) return x+1;if(x%4==3) return 0;
}
void solve(){cin>>l>>r>>k>>x;int a=get(k-1);int t=a^x;if(t==1){for(int i=l;i<=r;i++)if(i%4==1){cout<<i<<'\n';return;} cout<<-1<<'\n';return;}if(t==0){for(int i=l;i<=r;i++)if(i%4==3){cout<<i<<'\n';return;} cout<<-1<<'\n';return;}if(t%4==0&&t>=l&&t<=r){cout<<t<<'\n';return;}if(t%4==3&&t-1>=l&&t-1<=r){cout<<t-1<<'\n';return;}cout<<"-1\n";
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cin>>T;while(T--) solve();return 0;
}
AC 记录