Skip to content

【SG 函数 | 异或技巧】CF2217F Interval Game 笔记 ​

SG 函数 ​

  • 若 SG(i)=0,则状态 i 下当前手必败;若 >0,则状态 i 下当前手有必胜策略。
  • 对于状态 i 的 n 个后继状态 a1…n,SG(i)=mexj=1n(SG(aj))。
  • 对于多个独立的游戏,总的 SG 值为各个游戏的异或和。

题目思路 ​

遇到博弈论题像模型转换,才能够套用套路。

这题相当于有 4 堆石子,个数分别为 l1−1,x1−r1,l2−1,x2−r2,每次可以选择一堆任取若干个,不能操作者败的石子游戏。将四堆石子记为 a,b,c,d,由于任取,易得 SG(x)=x。

考虑 Alice 的选择,若令 a=0,则 a⊕b∈[0,x1−1],又因为 a⊕b≤a+b≤x1−1,故 a⊕b 的范围确定,可以在这个范围内任取。

枚举 a⊕b 的值,则所有 a⊕b⊕c⊕d≠0 的 c,d 都可以计入答案,即 c⊕d∈{x∣x=a⊕b⊕i,i∈[1,n]}。

然后有对连续区间 [1,n] 异或的性质,考虑改变的最高位,可以发现根据最高位的不同,异或的结果形成 log 个连续区间,差分数组维护时间复杂度即正确。

最近更新