自动搬运

查看原文

来自洛谷，原作者为

	qczrz6v4nhp6u Tell me, what scares you.

搬运于2025-08-24 22:24:17，当前版本为作者最后更新于2024-12-10 10:49:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

好玩的题目。

Solution

考虑判定一个局面是先手必胜还是后手必胜。一眼丁真每个棋子都是独立的，所以直接启动 ${\rm SG}$。

然后发现每个状态的后继都是一个链状的结构，这跟 Nim 游戏是一样的，所以我们知道 ${\rm SG}(i)=\lfloor\log_2\frac ni\rfloor$。于是一个局面的 ${\rm SG}$ 值 ${\rm SG}(1\sim n)=\bigoplus_{1\le i\le n}\lfloor\log_2 \frac ni\rfloor$。

枚举每一个值并统计它出现了多少次，推式子：

$${\rm SG}(1\sim n)=\bigoplus_{k}\Big(\big(\lfloor\frac{n}{2^k}\rfloor-\lfloor\frac n{2^{k+1}}\rfloor\big)\bmod 2\Big)\times k $$

其中 $\big(\lfloor\frac{n}{2^k}\rfloor-\lfloor\frac n{2^{k+1}}\rfloor\big)$ 就是满足 $\frac{n}{i}\in [2^k,2^{k+1})$ 的 $i$ 的个数。观察一下，发现 $\Big(\big(\lfloor\frac{n}{2^k}\rfloor-\lfloor\frac n{2^{k+1}}\rfloor\big)\bmod 2\Big)$ 就是 $n$ 的第 $k$ 位与第 $k+1$ 位是否相同。

接下来考虑拆位，即统计 $n$ 的每一位贡献到 ${\rm SG}$ 值的系数。打表 code：

#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
ull f[6];
void init(){
	for(int i=0;i<64;i++)
		for(int j=0;j<6;j++)
			if(i>>j&1)
				f[j]^=3ull<<i;
}
int n;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	init();
	for(int i=0;i<6;i++)
		for(int j=0;j<64;j++)
			cerr<<(f[i]>>j&1)<<" \n"[j==63];
	return 0;
}

打出来的表长这样：

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

不难发现规律：第 $0$ 列的系数均为 $0$；设 $j=\log_2{\rm lowbit}(i)$，则 $[0,j]$ 行内第 $i$ 列的贡献系数都是 $1$，$(j,+\infty)$ 行内第 $i$ 列的贡献系数都是 $0$。

对它消元，使得每列仅出现一个 $1$。那么此时的后手必胜要求就是对于每一种 $j$，所有满足 ${\rm lowbit}(i)=j$ 的数位 $i$ 异或起来是 $0$。

现在我们有相当好的办法刻画 ${\rm SG}$ 值，直接从高到低确定每一位即可。时间复杂度 $O(\log n)$。

Code

#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
ui n;bool val[64];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;n++;
	ull ans=0,cnt=1ull<<29;
	for(int i=35;i>=1;i--){
		if(!(i&(i-1)))ans|=(ull)val[i]<<i;
		else{
			if(n>cnt)
				n-=cnt,ans|=1ull<<i,val[i&-i]^=1;
			cnt>>=1;
		}
	}
	cout<<(ans+(n>1))<<'\n';
	return 0;
}