P6639 「JYLOI Round 1」让为哪个？
摘要：P6639 「JYLOI Round 1」让 大意 现在有多堆石子，其中第 (k) 堆石子有 (p_k) 个，先后手轮流操作。取石子时，可以选任意一堆进行操作。若记 (i) 为在这次取之前这堆石子的个数，(j) 为这次要取的
P6639 「JYLOI Round 1」让
大意
现在有多堆石子，其中第 \(k\) 堆石子有 \(p_k\) 个，先后手轮流操作。取石子时，可以选任意一堆进行操作。若记 \(i\) 为在这次取之前这堆石子的个数，\(j\) 为这次要取的石子数，\(R\) 为给定的常数，则需满足以下条件：
\[1 \leq i + j \leq R,i \geq j \geq 1
\]
使对方无法操作者即为胜者。
思路
我们首先考虑这个玩意的 \(SG\) 函数，太坑了，你们可以手动的模一下。
我们来假设 \(R = 5\) 的情况，首先 \(SG(0) = 0\)，\(SG(1) = 1\)，\(SG(2) = 2\)，但是我们发现，当 \(i = 3\) 的时候，能取的只有 \(1, 2\)，取这两坨只会把必胜态留给对面，那这个时候的 \(SG(3) = 0\)，那再看 \(SG(4) = 1\)，然后 \(SG(5) = 0\)，当 \(i \ge R\) 的时候 \(SG(i) = 0\)，这是显然的。
我们对于这个继续看其规律，不难通过注意或者推理得知，当且仅当 \(i \le \lfloor \frac{R}{2} \rfloor\) 的时候，\(SG(i) = i\)，实际上就是简单的 Nim 博弈，但是一旦到达 \(\lfloor \frac{R}{2} \rfloor + 1\)，则 \(SG(\lfloor \frac{R}{2} \rfloor + 1) = 0\)，这是巧合吗？显然不是，但是只有这一个转折点吗？
我赛时最初的思路是 \(SG(i) = i \pmod {\lfloor \frac{R}{2} \rfloor + 1}\)，可是真的对吗？不难发现当 \(R = 100\) 时，转折点在 \(\lfloor \frac{R}{2} \rfloor + 1 = 51\)，但是当 \(i = 76\) 的时候呢？我们只能取 \(24\)，也就是只能取到 \([52, 75]\) 这个区间，而这个区间的 \(SG\) 是 \({1, 2, 3, \cdots 24}\)，所以 \(SG(76) = 0\)，所以我刚刚的结论是错误的，继续向后模拟，发现在 \(SG(89) = 0\)，不难发现，什么时候等于 \(0\) 呢，我们设 \(pos\) 表示上次的位置，那么有：
\[nxt = \lfloor \frac{pos + R}{2} \rfloor + 1
\]
这个说明了，我们的 \(SG\) 是一段一段的，最多有 \(\log\) 段，故我们可以直接向后跳，提前预处理所有段，在查询的时候直接二分所在段，\(\mathcal{O}(1)\) 处理询问即可。
代码
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define ll long long
const int MAXN = 64;
ll R, lst[MAXN], val[MAXN];
int cnt;
inline ll Xor(ll n){
switch(n % 4){
case 1:
return n - 1;
case 2:
return 1;
case 3:
return n;
default:
return 0;
}
}
void init(ll x){
cnt = 0;
lst[0] = 0;
ll now = x / 2 + 1;
val[0] = Xor(now);
while(now < x){
lst[++ cnt] = now;
ll nxt = (now + x) / 2 + 1;
val[cnt] = val[cnt - 1] ^ Xor(nxt - now);
now = nxt;
}
}
ll ask(ll p){
int idx = upper_bound(lst, lst + cnt + 1, p) - lst - 1;
return (idx ? val[idx - 1] : 0) ^ Xor(p - lst[idx] + 1);
}
int main(){
// freopen("orange.in", "r", stdin);
// freopen("orange.out", "w", stdout);
cin.tie(0) -> ios::sync_with_stdio(0);
int T; cin >> T;
while(T --){
string op; cin >> op;
if(op == "change"){
cin >> R; init(R);
}
else{
int n; cin >> n;
ll ans = 0;
while(n --){
ll l, r; cin >> l >> r;
ans ^= ask(r) ^ ask(l - 1);
}
cout << (ans ? "1" : "0");
}
}
return 0;
}