[后缀自动机+线段树合并]Codeforces GYM102411L【Lengths and Periods】题解
题目概述给一个字符串 $S$ ，选一个子串 $T$ ，使 ${T\over T-Border(T)}$ 最大。解题报告每个串的Border并不好考虑，但是可以考虑枚举Border，然后去找子串。...
[单位根反演+Bluestein套路]LOJ3058【「HNOI2019」白兔之舞】题解
题目概述LOJ3058解题报告这个 $m\bmod k=t$ 以及 $k$ 是 $MOD-1$ 因子显然是单位根反演，所以考虑用生成函数表示答案。令转移矩阵为 $M$ ，定义 $F_i(x)$ ...
cdq分治FFT
非自身卷积$f_i=\sum_{k=0}^{i-1}f_kg_{i-k}$ ，$f_0$ 已知，给出 $g_{1..n}$ 。（ $k>i$ 同理）cdq分治，先处理 $[L,mid]$ ...
[DP+多项式exp]HDU5279【YJC plays Minecraft】题解
题目概述HDU5279解题报告首先每个连通块里必须是森林，然后连接每个连通块的 $n$ 条边只要删掉一条，就肯定不会存在全局环，这样每个连通块就独立了。定义 $f_i$ 表示 $i$ 个点树的方...
[Min25筛]2021牛客暑期多校训练营6 G【Hasse Diagram】题解
题目概述Hasse Diagram解题报告考虑 $f(n)$ 的递推式，但是如果只考虑单个素数，很明显会数重复，因此一次性考虑完一个素数，即 $p^k$ 。对于 $n\over p^k$ 的所有...
[生成函数+分治NTT+多项式ln]洛谷4705【玩游戏】题解
题目概述Luogu4705解题报告二项式展开后：$$
{t!\over nm}\sum_{k=0}^{t}{1\over k!}(\sum_{i=1}^{n}a_i^k){1\over(t-k)...
[除法分块+Min25筛]2021 CCPC 威海 I【Distance】题解
题目概述Distance解题报告$i$ 走到 $j$ 不管怎么走，每个相差的素数都必须走一遍，所以...
[NTT]AtCoder Grand Contest 005F【Many Easy Problems】题解
题目概述AGC005F解题报告考虑每个点对 $k$ 的贡献：$$
\sum_{i=1}^{n}[{n\choose k}-\sum_{(i,j)\in E}{size_j\choose k}]=...
Lyndon分解
性质$S$ 是Lyndon串当且仅当 $S$ 本身是所有后缀中的最小串。$S$ 是Lyndon串可以推出 $S$ 是所有循环表示中字典序最小的。各种性质与推论：$A,B$ 都是Lyndon串且 ...
[DP+分治NTT]HDU5322【Hope】题解
题目概述HDU5322解题报告考虑连通块是什么样的，对于 $n$ 的排列，$n$ 所在位置之前的点肯定都是 $n$ 连通块中的，并且 $n$ 没有往后的边。然后对于 $n$ 右边的数列也可以递归...
