后缀自动机系列最后一发——后缀自动机和博弈的小综合~hihocoder#:后缀自动机六·重复旋律9

时间限制:ms单点时限:ms内存限制:MB描述小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段字符构成的字符串。现在小Hi已经不满足于单单演奏了！他通过向一位造诣很高的前辈请教，通过几周时间学习了创作钢琴曲的基本理论，并开始对曲目做改编或者原创。两个月后，小Hi决定和前辈进行一场创作曲目的较量！规则是这样的，有两部已知经典的作品，我们称之为A和B。经典之所以成为经典，必有其经典之处。刚开始，纸上会有一段A的旋律和一段B的旋律。两人较量的方式是轮流操作，每次操作可以选择在纸上其中一段旋律的末尾添加一个音符，并且要求添加完后的旋律依然是所在作品的旋律（也就是A或B的一个子串）。谁词穷了（无法进行操作）就输了。小Hi和前辈都足够聪明，但是小Hi还是太年轻，前辈打算教训他一顿。前辈表示会和小Hi进行K次较量，只要小Hi赢了哪怕一次就算小Hi获得最终胜利。但是前提是开始纸上的两段旋律需要他定。小Hi欣然同意，并且表示每次较量都让前辈先操作。前辈老谋深算，显然是有备而来。他已经洞悉了所有先手必胜的初始(两段)旋律。第i天前辈会挑选字典序第i小的初始(两段)旋律来和小Hi较量。那么问题来了，作为吃瓜群众的你想知道，最后一天即第K天，前辈会定哪两个旋律呢？初始时两段旋律的字典序比较方式是先比较前一个旋律字典序，一样大则比较后一旋律的字典序。输入第一行包含一个正整数，K。K=10^18第二行包含一个非空的仅有小写字母构成的字符串，表示作品A。

A

=10^5第三行包含一个非空的仅有小写字母构成的字符串，表示作品B。

B

=10^5输出输出共两行，每行一个字符串（可能为空），表示答案。如果无解则只输出一行"NO"。样例输入5abcd样例输出acd

首先,对于样例数据,前辈只有10种必胜策略,按照字典序升序排序为("","c"),("","cd"),("","d"),("a",""),("a","cd”),("a","d"),("ab",""),("ab","c"),("b",""),("b","c"),所以答案是acd

根据我们对SAM的学习,知道在一个子串后面接上一个字符的含义其实是在SAM上按照trans进行转移.所以我们就把本题的拼接字符转换成了在A或者B的SAM上进行根据trans进行跳转.而题目中的一场较量其实就是给你两张DAG（A和B的SAM）,然后这两张DAG上分别有一枚棋子.两个玩家轮流选定一张DAG移动这张DAG上的棋子.不能继续移动者为失败.这不就是经典的DAG上博弈的问题么?使用SG定理予以解决.sg值是博弈论中SG函数的内容,不懂的童鞋可以去百度学习一下SG函数的内容.

所以和、、相比,本题每个SAM的节点上要维护的东西发生了变化——要维护的是"sg值"

求出每个SAM节点上的sg值只能解决如下问题

给定两个A、B中的子串,然后按照题目中的规则拼接字符,计算谁必胜.

因为一旦给定两个子串,我们就可以按照SAM的trans进行跳转,找到DAG上的博弈游戏的初始状态.然后计算此情形的sg值,根据sg值是否非零判断先手（前辈）是否必胜.

但是还不够,因为**本题是求字典序第k小的先手必胜初始状态（下面简称先手必胜初始状态为必胜态）.**这是一个挺棘手的问题~

以A="ab",B="cd"，K=5为例来说明整个过程.假设我们已经将SAM上每个节点的sg值已经求出来了.

记A的子串为sA,B的子串为sB.那么最暴力的想法是把所有必胜态(sA,sB)都求出来然后字典序升序排序然后取第k个不就好了?而我们想想看这些必胜态需要满足什么性质?根据SG定理,就是sg(sA所在节点)!=sg(sB所在节点).为了方便,记sgA为A的SAM上的sg函数,sgB为B的SAM上的sg函数.

为了后续讲解方便,我们

令cntA[prefix][x]是以prefix为前缀,并且sgA值为x的A的子串个数.同理定义cntB[prefix][x].令cntA[prefix][!x]是以prefix为前缀,并且sgA值不等于x的A的子串个数.同理定义cntB[prefix][!x].

首先,我们要判断一下是否会打印NO.其实只要K必胜态的总数的话,则就会打印NO,否则绝不可能打印NO.而所有必胜态的总数是多少呢?就是

如果tot=K的话,就一定不是NO,反之就是NO.

NO的问题解决了，我们来考虑怎么求第k小的必胜态.假设第k小的必胜态是(sA,sB)

我们考察第一关键字字典序最小的情形即sA=""的情况,我们自然对有多少个sB使得(sA,sB)为必胜态感兴趣.

首先A="ab"的SAM如下图所示（仅仅把trans画出来了，没有画slink，trans、slink这些基本概念可以学习）

显然,因为sgA("")=2（因为sgA(1)=1,sgA(2)=0,所以sgA("")=2,即所谓的minexcludemex操作）,所以有cntB[""][!2]个B中的子串使得(sA,sB)为必胜态.而B的SAM如下图所示（也没有画slink，只画了trans）

因为sgB("c")=1,sgB("d")=sgB("cd")=0，所以cntB[""][!2]=3

因为要求的K=53，所以可以断定sA一定不会是空串.排除掉刚刚sA=""情况下的三个必胜态,我们只需要求剩余的必胜态中的字典序升序排第二（K=5-3=2,切记,K已经变成2了哈~）的就是答案.此时我们就需要判断sA的第一个字符sA[0]是什么?

和刚刚的思路一样,我们也要计算出sA[0]=a时（即以"a"为前缀）必胜态的个数.根据乘法原理.答案是

事实上,我们具体计算一下就是（下面的计算式子中的sg位只出现了0、1、2是因为就样例数据而言sg值只有0、1、2三种——因为A或者B的SAM的字符集都只有2个字符）

cntA["a"][0]*cntB[""][!0]+cntA["a"][1]*cntB[""][!1]+cntA["a"][2]*cntB[""][!2]=1*2+1*3+0*3=5

因为5K=2,所以我们可以肯定sA[0]=a了.但是我们还想进一步确定一下sA四不四恰好就是"a".和上面计算sA=""情况一样,因为sgA("a")=1,所以答案就是cntB[""][!1]=cntB[""][0]+cntB[""][2]=1+2=3(即"c"和"d","cd"这三个)而K=2,所以我们可以肯定sA就是"a"了.下面开始确认sB是啥.即找到已知sA="a"的情况下,第K=2小的sB使得(sA,sB)为必胜态（即1=sgA(sA)!=sgB(sB)）

计算的方式也是类似的.我们先来看sB=""时,必胜态的个数,显然就是1个（即("a","")）.所以我们的K要进一步减少1变成K=2-1=1（切记,我们的K变成1了哈~）.然后就要确定sB[0].所以我们要计算cntB["a"][!1]、cntB["b"][!1]、cntB["c"][!1]、...、cntB["z"][!1]但是发现cntB["a"][!1]、cntB["b"][!1]都是0.而cntB["c"][!1]=1(就是"cd"),所以可以确定sB的第一个字符是"c".然后我们要看sB四不四恰好是"c",显然不是——因为sgB("c")=1=sgA("a"),所以("a","c")不是必胜态.所以sB一定会有第二个字符.所以我们要确定sB的第二个字符是什么.注意到cntB["ca"][!1]=cntB["cb"][!1]=cntB["cc"][!1]=0，cntB["cd"][!1]=1,所以可以确定sB的第二个字符是d,同时(sA="a",sB="cd")是必胜态.注意,此时K减掉1之后就是0.说明我们已经求出了第k小的必胜态为("a","cd")所以样例数据应该输出("a","cd").

回顾上面的分析过程,我们不难总结出解决本题的步骤

1.首先判断是否是NO2.逐个字符地确定sA3.逐个字符地确定sB

总体步骤如上,但是算法实现起来还是细节帝.要仔细~

鉴于确定每个字符的时候我们大量依赖cntA（cntB），所以我们需要解决的最后的一个问题是

如何高效维护cntA[prefix][x]与cntB[prefix][x]?

首先,在使用SAM解决问题的时候,一定要注意,如果涉及的属性对于在同一个等价类中的所有子串是相等的话,则就可以考虑使用SAM维护这一属性,否则就一定不能使用SAM维护这一属性.使用SAM来维护属性有什么好处?好处在于SAM有优秀的DAG结构（）以及slink树结构（）,有助于我们线性时间进行维护.

我们看看cntA[prefix][x]是不是对于一个等价类中的所有子串都是相等的呢?答案是肯定的，因为prefix就决定了该子串从SAM的哪个顶点出发.所以可以将cntA[prefix][x]视作是SAM的顶点的属性.也就是说我们可以将cntA作为SAM的顶点的属性维护起来.即本题的SAM节点上需要维护的属性不止有sg值,还有cntA[x]这种东西.而因为字符集不超过26个英文字母,所以根据sg值的mex类型的定义,x的取值范围（也就是sg值）不会超过26种，所以每个顶点开一个长度为26的数组cnt作为属性就好了.我们需要维护SAM节点的这个属性.说到维护,那自然要类似于那样充分利用SAM站在trans角度上看是一张DAG这一性质来维护.这也很简单.父节点的cnt[x]=所有DAG后继节点的cnt[x].那么叶子节点（即SAM的终止状态）的cnt[x]是什么呢?如果叶子节点的sg值等于x的话,则叶子节点的cnt[x]=1,否则等于0.整个维护的复杂度显然是O(26*N)，可以接受的.

最后要注意,本题可能爆int（前辈的必胜策略还真是多~所以和前辈打交道还是小心为上呢!）

本题分析完毕,开始切代码~

//#include"stdafx.h"#pragma