加载中...

周期引理 PL (Periodicity Lemma.)

发表于2023-12-21|OI（高中）2023-2024赛季

|总字数:157|阅读时长:1分钟|浏览量:

周期引理 PL (Periodicity Lemma.)

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135121747

在这里插入图片描述

在这里插入图片描述

原先串：若干 $p$ ，加一个前缀，因此是 $\dfrac {A(x)}{1-x^p}\bmod x^{n+1}$

这个：在这里插入图片描述

$\bmod x^{n+1}$ 为0。（多项式）

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

我们有 $R(x)\bmod x^{n+1}=0,deg(R)\in n$ ，所以 $R(x)=0$ ，所以左式恒为0。

在这里插入图片描述

右边度数可以分析。（多项式除法度数相减）

文章作者: zhangxixi

文章链接: http://zhangxixi.top/post/97129703

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！

字符串 PL 周期引理

相关推荐

broder剃头去尾的新broder

broder剃头去尾的新broder 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135122233 若红色为1串的broder，则显然黄串为2串的broder 因此broder在剃头去尾可以用于均摊分析题目：POI2012」Prefixuffix

【GDOI2022PJD1T1 邹忌讽齐王纳谏】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16179574.html D1T1 邹忌讽齐王纳谏题目齐国人邹忌对齐国国君齐威王说，大王身边的人会因为私情、利益等原因而对大王阿谀奉承，所以不能光听好话，只有广泛接受群众的批评意见，才不会被蒙蔽双眼，齐国才能强盛。齐威王接受了这个意见，于是昭告全国：如果有臣民当面对齐威王提出建议，则获得价值为 A 的奖励；如果有臣民以书信的方式对齐威王提出建议，则获得价值为 B 的奖励；如果有臣民在街市中议论齐威王，意见流传到宫廷，则获得价值为 C ...

【CF827C DNA Evolution】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16306588.html 题目链接题目 DNA链由核苷酸组成。有四种类型的核苷酸：“A”，“T”，“G”，“C”。 DNA链是核苷酸序列。科学家决定追踪一种稀有物种的进化，它最初的DNA链为s。物种的进化被描述为DNA的一系列变化。每个变化都是某些核苷酸的变化，例如，DNA链“AAGC”中可能发生以下变化：第二个核苷酸可以变为“T”，然后变成“ATGC”。科学家们知道DNA链的某些片段会受到某些未知感染的影响。这些感染可以被表示为核苷酸序列...

manacher算法一图复习

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16555504.html 完整版请戳这

【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...

【P3538 [POI2012]OKR-A Horrible Poem】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15810272.html 题目原题来自：POI 2012 给出一个由小写英文字母组成的字符串 S，再给出 q 个询问，要求回答 S 某个子串的最短循环节。如果字符串 B 是字符串 A 的循环节，那么 A 可以由 B 重复若干次得到。思路首先，我们如果有三点：一个字符串的循环节必然是字符串长度的约数循环节的倍数如果长度还是字符串长度的约数，那么他也是循环节如果一个长度 iii 是字符串循环节长度，那么 [l,r−i][l, r-i]...

数据加载中