broder剃头去尾的新broder
broder剃头去尾的新broder
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135122233
若红色为1串的broder，则显然黄串为2串的broder
因此broder在剃头去尾
可以用于均摊分析
题目：POI2012」Prefixuffix
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-08-29
后缀自动机SAM
后缀自动机SAM 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132560666 https://www.luogu.com.cn/problem/P3804 fail：当前区间-1（最短串 去掉最前面 的字符） nxt：任意串 加上最后面 考虑新加入的字符为x，上一个为p，则 nxt[p][x]=cnxt[p][x]=cnxt[p][x]=c 当前的每个后缀如果本身nxt为空，都可以加x 代码： 然后考虑现在这样： 如果整个区间可以直接...
2022-01-17
【Loj #10047. 「一本通 2.2 练习 3」似乎在梦中见过的样子】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15812840.html 题目 原题来自：2014 年湖北省队互测 Week2 「Madoka，不要相信 QB！」伴随着 Homura 的失望地喊叫，Madoka 与 QB 签订了契约。 这是 Modoka 的一个噩梦，也同时是上个轮回中所发生的事。为了使这一次 Madoka 不再与 QB 签订契约，Homura 决定在刚到学校的第一天就解决 QB。然而，QB 也是有许多替身的（但在第八话中的剧情显示它也有可能是无限重生的），不过，意志坚定的 H...
2022-01-10
【CF5C Longest Regular Bracket Sequence】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15783397.html 题目链接 题目 This is yet another problem dealing with regular bracket sequences. We should remind you that a bracket sequence is called regular, if by inserting «+» and «1» into it we can get a correct mathematical ex...
2021-12-02
【CF554A Kyoya and Photobooks】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15634024.html 题目链接 暴力是肯定可以的。所以这里讲 O(1)O(1)O(1)。 首先不考虑重复，则有 (∣s∣+1)×26(|s|+1)\times 26(∣s∣+1)×26 种可行方案。 然后重复的就是在一个字母的左右放和这个字母相同的字母，有 ∣s∣|s|∣s∣ 种可能。 所以总共有 (∣s∣+1)×26−∣s∣(|s|+1)\times 26-|s|(∣s∣+1)×26−∣s∣ 种可能。 Code 12345678910111...
2023-12-21
增量构造+答案上界推出增量构造上界确定复杂度：CF1063F
增量构造+答案上界推出增量构造上界确定复杂度：CF1063F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135129285 https://www.luogu.com.cn/problem/CF1063F 可以贪心一波， ttt 长度必然是 ans,ans−1,ans−2,ans−3,…,3,2,1ans,ans-1,ans-2,ans-3,\dots,3,2,1ans,ans−1,ans−2,ans−3,…,3,2,1 这样子。 如果一个 kkk 不存...
2023-12-21
周期引理 PL (Periodicity Lemma.)
周期引理 PL (Periodicity Lemma.) 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135121747 原先串：若干 ppp ，加一个前缀，因此是 A(x)1−xp mod xn+1\dfrac {A(x)}{1-x^p}\bmod x^{n+1}1−xpA(x)modxn+1 这个： mod xn+1\bmod x^{n+1}modxn+1 为0。（多项式） 我们有 R(x) mod xn+1=0,deg(R)∈nR(x...