分析

我们知道在 SAM 上从初始状态 \(t_0\) 某一个状态 \(x\) 的一条合法路径表示了一个子串。

所以题目可以转变为在两个 DAG 上有两个初始点,每次每个人可以选择一个点向后转移一步,第一个没有路可走的人就输了。

这部分可以用 SG 函数得到(by Kilo_5723):

这是一个显然的 DAG 上 SG 函数问题。两个 DAG 的问题就是组合起来,用异或判断是否为 \(0\) 即可。

于是先手的必胜初始态就是两个 DAG SG 值不同的 pair 。因为要求字典序的第 \(k\) 大,于是需要计数。

首先肯定是对于每一个字符串 \(A\) 对应的 SAM 上的状态计算其中一个元素为这个想状态的合法 pair 数量,也就是统计 \(B\) 对应的 SAM SG 值不同的个数。

根据这个值,我们求一个 DAG 上的前缀和,就能贪心的走,求出字典序第 \(k\) 大的了。

在完成第一个字符串的情况下,我们要继续完成第二个字符串。

因为第一个字符串已经确定了,那么第一个字符串对应的 SG 值也就确定了,于是对应第二个字符串就是要找到字典序满足要求,且 SG 值不等于第一个字符串的。

和上面类似的预处理 DAG 上前缀和,贪心的确定字典序对应的字符串即可。

要注意答案可能会爆 long long ,巨坑,对拍以后才发现这个问题。

 


发表评论

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