文章

字符串杂题记录 字符串刚刚入门。 考的少就贼亏。 Aho-Corasick AutoMaton 需要谨记的一点就是，$\rm{ACM}$ 跳的是 最长公共后缀，而不是 最长公共前后缀 。 不要和 $kmp$ 搞混了，千万不要相信什么 $\rm{ACM}$ 就是 $kmp$ 上树，千万不要。 Suff 阅读更多…

「洛谷题单界面」，如果有帮助可以 archive 一下。「洛谷博客界面」在 mina.moe 上可能更新比较延后，因为我要同时维护多个地方，懒得很…… 这里是由 @BoringHacker 以及 @Lautisticyc 维护的数据结构 100 题，简称 DS100P。 难度主要在提高组及以上。 阅读更多…

传送门 题面 题意 给定一个字符串 $s$ (起始位置为 $1$), 对 $s$ 的每个前缀求出最小循环表示的起始位置. 输入样例 abaacaba 输出样例 1 1 3 3 3 6 3 8 数据范围 $|s| \le 3 \times 10^6$. 思路 假设先从前往后扫一遍, 则对于每个前缀, 阅读更多…

前言 我第一次看到这个 idea 是神 $Fuyuki$ 去年 6 月份的时候出了一套题目，里面用到了这个东西，不过他当时没有给出证明。后来看到了 $boshi$ 在 $Mina$ 上发的计数合集，里面证明了这玩意儿的正确性，我个人认为还是一个非常妙的东西，所以专门开个坑记录一下。 柿子 $$ \t 阅读更多…

暴力连边的话，对于原图中的 $(x,y)$ ，将 $A_x\rightarrow B_y$ 给连上，然后如果 $B_i$ 是 $A_j$ 的前缀的话，将 $B_i\rightarrow A_j$ 连上。定义点 $A$ 的权值为其长度，点 $B$ 权值为 $0$ ，显然答案就是图上的最长路，当然如果出 阅读更多…

upd 2020/06/16 : 之前的图片貌似显示不了, 换了个图床, 应该可以显示图片了. 前言 刚装好 Ubuntu 20.04, 准备安装 emacs, 按照网上的步骤, 结果出现了下面的东西….. 怎么都无法解决…. 所以, 我决定, 手动安装 emacs. 网上的 阅读更多…

前言 这个 idea 不是我的，是之前在 UOJ 群里面有群友提出的一个做法，我这里只是根据当时提到的大致想法，结合自己的理解整合成了一个我认为较详细的可行方法。 (不好意思，我是真不知道那位群友是谁，如果看到了的话麻烦告知一声，会补上 id 的) 正文 1. 建广义 SAM 我们要解决的是多串公共 阅读更多…

首先对于需要按奇数次的开关，其生成函数为： $$ F_i(x)=\sum_{n\,is\,odd}^{\infty}p_i^{n}\frac{x^{n}}{n!} $$ 然后对于需要按偶数次的开关，其生成函数为： $$ F_i(x)=\sum_{n\,is\,even}^{\infty}p_i^{n 阅读更多…

证明我存在过 不会数学，若有错误请指出 qwq 指数型生成函数 $\rm{EGF}$ 基本定义： $$ F(x)=\sum_{i=0}^{\infty}\frac{x^i}{i!} $$ 一些性质： $$ e^x=\sum_{i=0}^{\infty}\frac{x^i}{i!} $$ 一些意义：先 阅读更多…