资讯详情

【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\)。

因此：

1. 如果 \(T=1\)，则只要在区间内存在 \(n\equiv1\pmod4\) 的数即可。我们可以选区间内最小的 \(n\equiv1\pmod4\)。
2. 如果 \(T=0\)，则必须选 \(n\equiv3\pmod4\)，选区间内最小的 \(n\equiv3\pmod4\)。
3. 如果 \(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 记录