「置顶」各类 tricks

求答案第 $k$ 大/前 $k$ 大问题

指数乘积拆解：$\displaystyle ij=\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}$
\(a^{ij}=\frac{a^{\large\binom{i+j}{2}}}{a^{\large\binom{i}{2}}a^{\large\binom{j}{2}}}\) 应用：P6295

若干个集合，每个集合有若干个数，每次删去两个不同集合中的一个数，求最后最少剩下几个数。

设 $k$ 为集合大小最大的一个集合，$siz(x)$ 表示 $x$ 集合的大小，$sum$ 表示所有集合的大小的和：

• 若 $siz(k) \le sum - siz(k)$，那么每次删除最大值与次小值，最后只剩下 $0/1$ 个数。
• 若 $siz(k) > sum - siz(k)$，那么每次用 $k$ 集合里的一个数与其它集合里的一个数删除，最后只剩下 $siz(k) - (sum - siz(k)) = 2siz(k) - sum$ 个数

应用：AGC034E

没有负环 → 差分约束有合法解

应用：AGC036D

《b i t s e t 字 符 串 匹 配》

应用：CF914F

对于期望方程组类型的题目，且矩阵相对稀疏，可以考虑递推系数的方法消除大部分未知数。

无穷级数求和：可以先推导出生成函数的封闭形式（尤其是涉及到组合数一类的无穷级数求和），然后将 $x=1$ 带入。如果有指数形式的可以直接带 $x=a$ 实现系数乘 $a^n$。

贝尔级数 可以比较轻松解决一些杜教筛/狄利克雷卷积的问题？

有生之年也不知道能不能碰上的）

eg. $f(1)=1,f(p^c)=p^c+(-1)^c \Rightarrow f_p(x)=ID_p(x)+\lambda_p(x)-e_p(x) \Rightarrow \frac{1-px^2}{(1-px)(1+x)}$

这有啥用啊，卷完也不会做）

$\sum_{i=1}^n \mu^2(i)=\sum_{i\leq\sqrt n} \lfloor\frac{n}{i^2}\rfloor\mu(i)$

• 在线：建 SAM
• 离线：建 AC 自动机
• 如果模式串极长（由规律给出）考虑 AC 自动机 GYM103409H
• bitset 匹配 CF914F

给定字符串 $s,t$，$q$ 次询问，每次找 $s$ 的一个子串在 $t$ 的 SAM 上的对应节点：

首先将 $s$ 在 $t$ 上跑一遍，记录下每一个前缀在 $t$ 上能匹配的最大后缀所代表的节点。

查询时直接在最长的节点倍增跳 $fail$ 即可 $O(\log n)$ 查找单个节点。

注意当最长节点的长度小于询问串的情况。

int get(int p, int l) {
    for (int i = 19; i >= 0; i--) {
        int q = fa[p][i];
        if (len[q] >= l) p = q;
    }
    return p;
}

应用：CF666E 【ULR #1】打击复读

对于一个字符串的正反 SAM，可 $O(n)$ 找到正串某个节点代表的最长字符串对应的反串节点与正串某个节点代表的所有字符串对应的反串节点的权值和。

大体做法是压缩后缀自动机中出度为 $1$ 的节点，具体看 题解。

树形 DP 中如果需要记录顶点所在连通块的大小，可以转化成从顶点所在连通块中选出一个关键点来将 $0\sim siz_u$ 的状态压缩到 $0 \sim 1$（仅记录是否已经选取关键点）

树上 $dep_{lca(u,v)}$：

• $dep_{lca(u,v)}=\frac{dep_u+dep_v-dis_{u,v}}{2}$

• $dep_{lca(u,v)} = \sum_{i\in T} [u\in T(i)][v \in T(i)]$