题解 P3727 【曼哈顿计划E】

will7101 · 2017-04-22 18:28:19 · 题解

一句话题意：

一颗树上每个点有权值（SG函数值），问能否选择一条链，使SG函数值异或和为零。

预备知识

不会SG函数的同学请移步这里 -> ydc老师的博客

题解

直接放神犇同学@loveyayoi的题解:

• 知识需求：sg函数，点分治

• 做过一些点分的题的同学应该一眼就能看出这是一道点分

• 做过一些博弈问题的同学应该一眼就能看出这是一道SG函数博弈

• 我们分别讨论n，k，w三个条件

n

• 对于n<=1000的情况，直接暴力DFS即可

• 对于n<=30000的情况，点分治+set/hash

k

• 通过打表可以发现一些规律

• k=1时就是普通的nim游戏，sg(x)=x

• k=2时通过打表可以发现明显的规律，如果s是偶数，sg函数有长度为s+1的循环节，值为0,1,0,1,0,1,0,1....,2，如果s是奇数，那么sg(x)=x\ mod\ 2

• k=3时，打表也可以看出规律，sg(x)=\lfloor \frac{x}{s} \rfloor

- k=4时，打表得知，
$$sg(x)=
\begin{cases}
0 & \text{ , } x= 0 \\
x & \text{ , } x\equiv 1,2 (mod\ 4) \\
x+1 & \text{ , } x\equiv 3 (mod\ 4) \\
x-1 & \text{ , } x\equiv 0 (mod\ 4)
\end{cases}