tricks

记录一些技巧

一半的半平面交

当求半平面交的一半(相当于求一个直线构成的下凸壳或上凸壳)时, 可以把如 $y=kx+b$ 的直线转化成 $(a, b)$ 求凸壳

长剖换根

长链剖分的换根说的是, 你做完长链剖分之后跑换根dp, 那么现在一个点有其长儿子的信息, 短儿子的信息和子树外的信息, 那么直接把所有短儿子都合并到子树外的信息上, 进入一个轻儿子的时候把自己删了, 把重儿子前 $h$ 个加入, 退出的时候撤销, 进入重儿子的时候就用全部的即可.

要求信息可合并, 可删, 且信息量是仅深度相关对.

二项式系数

$$
\sum \binom {n}{i}^2=\binom{2n}{n}
$$

证明考虑 $[x^k] (1+x)^{2k}$

排列

模 $n$ 的环上存在排列 $p_n$ 满足 $i-p_i$ 互不相同当且仅当 $n$ 为奇数.

必要性显然.

充分性考虑率 $\sum_i i=\sum_i i-p_i=\sum i-\sum p_i=0$ 即可.

末尾添加删除节点的线段树动态构建

UOJ191

Bitset字符串匹配

抄写 alexwei

对 $s$ 和多个模式串 $t$ 求 $t$ 在 $s$ 中出现位置, 对 $s$ 维护字符集个 bitset $b_c$ 表示字符 $c$ 的出现位置, 遍历 $t$ 中的每个字符 $t_i$, 那么如果 $t$ 要在 $x$ 处结尾则 $x-\vert t\vert+i$ 位置应该是字符 $t_i$, 于是把每个 $b_{t_i}$ 左移对应位与起来即可. 复杂度是 $\dfrac{\vert s\vert \vert \sum t\vert}{w}$

为了遍历结束位置, 可以用bitset的 _Find_first() 和 _Find_next(int x) 函数

奇怪卷积

给定集合的序列 $f, g$, 要求 $h_S=\sum_T f_Sg_T2^{S\cap T}$

考虑经典容斥 $2^{\vert S\vert}=\sum_{T\subseteq S} 1$, 有

$$
\begin{gathered}
h_S=f_S\sum_T g_T\sum_{A\subseteq S, A\subseteq T}1\
=f_S\sum_{A\subseteq S} \sum_{T\supseteq A} g_S
\end{gathered}
$$

发现是对 $g$ 先做高维后缀和再做高维前缀和.