cdq分治FFT
非自身卷积$f_i=\sum_{k=0}^{i-1}f_kg_{i-k}$ ，$f_0$ 已知，给出 $g_{1..n}$ 。（ $k>i$ 同理）cdq分治，先处理 $[L,mid]$ ...
Lyndon分解
性质$S$ 是Lyndon串当且仅当 $S$ 本身是所有后缀中的最小串。$S$ 是Lyndon串可以推出 $S$ 是所有循环表示中字典序最小的。各种性质与推论：$A,B$ 都是Lyndon串且 ...
两种常见的树上差分
树上差分忘完了……康复一下。记 $x$ 节点的父亲为 $fa(x)$ 。记 $x,y$ 节点的LCA为 $lca$ 。记权值数组为 $w_x$ ，差分数组为 $D_x$ 。记DFS序中 $IN_...
拉格朗日插值
求多项式我们知道 $n$ 个点可以确定 $n-1$ 次多项式（比如三点求抛物线）。假设 $f(x)=\sum_{i=0}^{n-1}a_ix^i$ ，如果我们要求 $f(k)$ ，可以先解出 $...
Min_25筛
一类问题已知积性函数 $f(n)$ ，其中 $f(p)$ 是简单多项式，且 $f(p^k)$ 可以快速计算（ $p$ 是素数），求其前缀和。上杜教筛？如果 $f(n)$ 很奇怪就没法卷另外一个...
[斯坦纳树]BZOJ2595(Wc2008)【游览计划】题解
题目概述在 $n\times m$ 的网格上有 $k$ 个景点，选取每个网格都有代价，求最小代价使得景点之间全部连通。解题报告感觉这个东西好mogical啊……定义 $f_{i,j,s}$ 表示...
[插头DP]BZOJ1814(Ural 1519)【Formula 1】题解
题目概述给出 $n\times m$ 的网格图，其中有些格子是障碍，求有多少种方法用一条哈密顿回路覆盖没有障碍的格子。解题报告ps：大量图片来自于cdq的课件QAQ。这道题的退化版是HDU169...
[容斥+二项式反演]BZOJ2839【集合计数】题解
题目概述有一个 $n$ 个元素的集合，求选出若干个子集（不可以不选）相交后元素个数刚好为 $K$ 的方案数。解题报告学Min-Max容斥的时候没有考虑过怎么构造，导致这道题的构造方法理解了半天…...
[Min-Max容斥+高维前缀和]BZOJ4036(HAOI2015)【按位或】题解
题目概述我写过了来着，鸽了。解题报告用Min-Max容斥再做一遍这题，学习自memset0。Min-Max容斥，对于一个集合 $S$ ，他的最大值 $max(S)$ 和子集 $T$ 的最小值 $...
