【BZOJ4650】【NOI2016】优秀的拆分

丧心病狂出题人还卡自然溢。。

令\(c_i\)为以\(i\)开头的\(AA\)串的个数,\(d_i\)为以\(i\)结尾的\(AA\)串的个数

那么答案显然是\(\sum_{i=1}^{n-1}c_i d_{i-1}\)

那么如何求出这两个值呢?思想很巧妙

枚举A的长度\(k\),将字符串每\(k\)位分成一段。

可以发现\(AA\)一定是某一段的一个前缀拼上上一段的后缀拼成一个\(A\),这一段剩下的部分和后一段的前缀拼成另一个\(A\)。

那么A的前缀就是该段和上一段的一个公共后缀,A的后缀就是该段和下一段的一个公共前缀。

那么求出相邻两端的LCP和LCS,剩下的就是区间加法了。因为只要最后询问一次,所以差分即可。

求LCP和LCS可以用后缀数组,当然数据范围小也可以二分hash。

说点什么

您将是第一位评论人!

提醒
wpDiscuz