毒瘤题解 BZOJ2410

某次搜 “Nim” 手贱搜出这破题来,结果自闭了一上午,自闭了。

首先考虑 k>2 的情况,因为任意一个格子都可以填颜色而两边的格子不会影响它,答案是 0 的格子数的奇偶性决定的。

那么再来考虑 k=1 的情况。此时我们把每段白格子单独拿出来看:

首先(除掉整个序列的开头和结尾)每段的第 1 和最后一个这两个格子是不能染色的。

那么假设我们在中间染了一个,那就分成了两个子局面,比较显然这两个子局面是相互独立的,那么我们就可以用 SG 定理了。

再考虑如何算一段白格的 \mathrm{SG} 。首先长度为 0 的白格子的 \mathrm{SG}0 ,长度为 1 的因为只能转移到 0 所以  \mathrm{SG}=1

那么接下来考虑长度为 n 的,我们先假设这 n 个格都能被染色

那么染位置 i 会让剩下两段为 i-2n-i-1

(注意特判 i=1i=n 的情况,这两种本质上是一样的)

那么我们爆算一波 \mathrm{SG}  值。

打个表找规律

0,1,1,2,0,3,1,1,0,3,3,2,2,4,0,5,2,2,3,3,0,1,1,3,0,2,1,1,0,4,5,2,7,4,
0,1,1,2,0,3,1,1,0,3,3,2,2,4,4,5,5,2,3,3,0,1,1,3,0,2,1,1,0,4,5,3,7,4,
8,1,1,2,0,3,1,1,0,3,3,2,2,4,4,5,5,9,3,3,0,1,1,3,0,2,1,1,0,4,5,3,7,4,
8,1,1,2,0,3,1,1,0,3,3,2,2,4,4,5,5,9,3,3,0,1,1,3,0,2,1,1,0,4

然后发现除前两段之后循环节为 34

(其实这个非常神奇,不过这种模型居然也出现在 《Winning Ways》 里面了,Orz……可以看一下这个A002187 )

然后就直接乱搞就可以了。。

这就完了,再来考虑 k=2 的情况

如果你不去管全部空白的特殊情况,那么空白块总共有三种:

  1. 有一端与一个染色块相邻,另一端为整个序列的首或尾。
  2. 两端都与染色块相邻,两端颜色不同。
  3. 两端都与染色块相邻,两端颜色相同。

可以把 [2] 和 [3] 一起考虑,很轻松的使用归纳法证明 [2] 的 \mathrm{SG} 值都是 0 ,[3] 的 \mathrm{SG} 值都是 1

那么考虑第一种情况,随便画个图或者写个暴力可以得到长度为 n 的段的 \mathrm{SG}=n

这样就基本做完了。再回来考虑全部空白的情况。如果长度为 N ,后继局面显然有 N 种。

然后你发现每种都是两个子局面异或起来,假设先手从位置 i 劈开,那么就是 i-1 \oplus n-i

然后 O(n) 求一下 \mathrm{SG} 就好了。

不过事实上是数据过水,导致没有这类情况,不用写就能过。。。。

另外搜 A002187 的资料的时候我搜到一份很有趣的文档讲的是这个序列和井字格游戏的关系,好像可以出一道题的样子。。

 

– END –

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据