ZigZagK的博客
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$ 的最小值 $...