冷滟泽的个人博客

2019-01-09 lengyanze 阅读(56) 评论(0)

莫比乌斯反演 莫比乌斯函数 定义 莫比乌斯函数 \mu 的定义如下： 首先将 n 质因数分解，表示成 n = \prod_{i=1}^{k} {p_i}^{a_i} 则 \mu(n) = \{\begin{matri...

2019-01-01 lengyanze 阅读(52) 评论(0)

题目链接 Luogu3302 BZOJ3213 题意 给出一堆森林（每个点有权值）和两种操作： 在点 x 和点 y 间连一条边，保证操作后图还是森林； 询问点 x 与点 y 之间路径上第 k 小的权值，保证 x...

2018-12-23 lengyanze 阅读(33) 评论(0)

题目链接 BZOJ4650 Luogu1117 算法分析 以下内容部分借鉴于 Sengxian's Blog 。 将以 i 开始 AA 串的个数记为 f[i] ，以 i 为结束的 AA 串的个数结尾 g[i] ；...

2018-12-16 lengyanze 阅读(99) 评论(0)

题目链接 BZOJ2754 Luogu2336 概述 本题解法众多，比如： AC 自动机 广义后缀自动机 后缀数组 + 莫队 ...... 这里我介绍一种新的解法：后缀数组 + ST 表 + 二分 +...

2018-12-13 lengyanze 阅读(76) 评论(0)

定义 后缀 i ：一个字符串从第 i 个字符到结尾的子串成为这个字符串的后缀 i ； 后缀排序：将一个字符串的所有后缀按字典序排序； sa[i] ：后缀排序后排名第 i 的后缀； rank[i] ：后...