求问 SG 函数证明
查看原帖
求问 SG 函数证明
191748
Rosaya楼主2024/4/22 17:40

本题的结论是:将关键点构成虚树内的点全部视为黑点,边按照端点黑点数量分为 0 白边,1 灰边,2 黑边。

整个游戏的 SG 函数为灰边子树 SG 异或虚树内边数。

但市面上题解都并未详细说明它的正确性(或许是我没找到,如果有能否告知我),大量题解中所谓的虚树内外独立性也是基于可以将关键点构成虚树内的点全部视为黑点为前提才成立的,CF 上的题解在证明小于当前 SG 的状态都能达到时也仅仅是将其归纳到了 k=2k=2 的情形,没有继续证明。

所以能否有大佬提供下证明思路,求求了。

目前只有灰边 SG 全部为偶数(+1+1 后)且虚树内边数为奇数一种情况没有解决,只需要给出一个操作使得操作后的 SG 值恰为原灰边 SG 异或即可。

2024/4/22 17:40
加载中...