2019HDU多校赛 第十场 HDU 6694 Play Games with Rounddog（后缀自动机 + 线性基）

大致题意：给你一个字符串S，然后q个询问，每次给出S的一个子串T。对于每个询问的子串T，Calabash可以在Ｓ中选择任意个以T作为后缀的子串，然后生成子串对应数目个石子堆，每堆的石子数量等于w[对应子串在S中出现的次数]。然后Rounddog可以从这么多堆石子中选择任意堆的石子（至少选一堆），两人开始玩Nim游戏，Calabash先手。现在问Calabash是否存在必胜策略，如果有输出Calabash在必胜策略下，能够选出来的最多的石子数目。

比赛的时候大概想到了，猜了一个结论，但是没敢写……

题目有点绕，但是经过分析我们可以慢慢理解题意。首先，直接考虑两个人玩Nim游戏，Calabash想要先手必胜，那么在游戏开始的时候所有堆的数字数目异或起来一定不能为0。这个条件其实很容易转换，因为异或和不为0，那么可以考虑线性基。显然如果要必胜，那么把最后的石子堆数插入线性基，一定都是可以成功插入的。所以，Calabash一定是可以找到至少一种方案使得他必胜。

然后考虑石子数目最多，也就是找一个和最大的线性基。这里就要用我们猜的到结论，就是对于一堆数字，从大的数字往小的数字依次往线性基里面插，这样的线性基基底的和一定是最大的。这个结论我也不太会证明，但是感觉确实是这个样子的。不过我比赛的时候也没敢写，赛后看别人有这么写过了的才来补。

这样，我们就完成了后半部分，现在我们考虑前半部分。这里需要知道，所有以某个子串作为后缀的串在原串中出现的次数，我们考虑用后缀自动机。考虑后缀自动机的parent树，根据定义，某个节点在parent树中所有的后代对应的子串的后缀都包含这个节点对应的串，所有它的后代节点的数量即right就是本题所求的出现次数。对于一个询问给定的子串，我们可以找到它在后缀自动机中的位置，这个位置以及其后代所有节点都是包含子串的可选串，对应他们的w[right]即为线性基中可以插入的数字。