T3数组操作
- 有一个长度为 N 的数组，甲乙两人在上面进行一个游戏：
- 数组上有一些格子是白的，有一些是黑的。然后两人轮流进行操作。
- 每次操作选择一个白色的格子，假设它的下标为 x。
- 接着，选择一个大小在 1~n/x 之间的整数 k，然后将下标为 x、2x、...、kx的格子都进行颜色翻转。不能操作的人输。
- 给你一个数组的初始状态，判断是否先手必胜。
T3数组操作
- n=20
- 爆搜？
- 每次搜索时模拟甲乙两人的操作即可。
- 30分到手了
- 当年的那些大神似乎都拿的是这30分
T3数组操作
- 博弈论知识普及：
- mex{a[1],a[2],……}表示所有正整数中第一个没有在a[1],a[2]……中出现过的数
- 如mex{0,1,2,5}=3
- 一个状态的SG函数值等于它的所有后继状态的SG函数值的mex
- SG定理：若局面X由若干个子游戏构成：X1,X2 … XN， 则SG[X] = SG[x1] ^ SG[x2] …^ SG[XN]
T3数组操作
- 思考：
- 在这道题中每次翻转黑格子的操作都不可能直接带来胜利
- 为什么？
T3数组操作
- 官方解释：
- 任何一步选取黑格子进行的有利操作都能由对方通过再翻一次这个格子抵消掉
- 说实话，我没看懂
- 让我们从理论层面来分析一下吧
T3数组操作
- 首先，游戏要求把所有的白格翻转成黑格
- 把某个格子变成黑格看成一个子游戏
- 那么所有的子游戏都是相互独立的
- 根据SG定理，只需要判断所有白格的SG的异或和是否等于0就行了
- 那么如何求出每个格子的SG函数值呢？
T3数组操作
- 实际上
- SG[i]=mex{0，SG[i2]，SG[i2]^SG[i3]……，SG[i2]^……^SG[i*k]}
- (这里的0其实是SG[i])
T3数组操作
- 解释一下：
- 假设每个点都是白点
- 把点i翻转成黑点有k种途径：
- (1)把i翻转
- (2)把i,2i翻转
- (3)把i,2i,3i翻转
- ……
- 所以状态i的后继状态一共有k个
- 所以SG[i]就等于这k个后继状态的mex值
T3数组操作
- 回到原问题
- 我们知道白格一定被翻转了奇数次，黑格被翻转了偶数次
- 所以把这些格子异或起来后，黑格的SG值相互抵消
- 这就解释了开始提出的问题
- 选黑格进行翻转一定不优
T3数组操作
- 所以我们只需要递推出每个点的SG函数值，然后对于每个询问，算出所有白格的异或和就行了
- 这样可以得到50分
T3数组操作
- 看到1e9的数据范围我就吓傻了？
- ——分块优化
- 根据我的程序，当n=10时，每个格子的SG函数值如下：
- 4 1 2 2 2 1 1 1 1 1
- 通过狗眼观察法，我们发现区间[n/(i+1)+1,n/i]的SG函数值是相同的
- 所以我们只需要算出n/i的答案，回答询问时在块内查找即可，时间复杂度O(n)，可以拿到70分
T3数组操作
- 神tm出题人怎么这个丧病啊，我脑洞都用完了才70分
- ——玄学优化
- 我*，省选题怎么这么不靠谱啊，玄学！！
- 在预处理时，如果两个块的SG值相等，就把这两个块合并
- 由于数据比较水，所以就能AC了
- 如今的OI界真是玄学题横行啊