• 子集反演

$$g(S)=\sum_{T\subseteq S}f(T) \Leftrightarrow f(S)=\sum_{T\subseteq S}g(T)\cdot (-1)^{|S|-|T|}$$

$$h(S)=\sum_{T\supseteq S}f(T) \Leftrightarrow f(S)=\sum_{T\supseteq S}h(T)\cdot (-1)^{|T|-|S|}$$

• 二项式反演

$$g(n)=\sum_{i=0}^n\binom{n}{i}f(i)\Leftrightarrow f(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}g(i)$$

$$h(n)=\sum_{i=n}^m\binom{i}{n}f(i)\Leftrightarrow f(n)=\sum_{i=n}^m(-1)^{i-n}\binom{i}{n}h(i)$$

• 莫比乌斯反演

$$[\gcd(x,y)=1]=\sum_{d|x,d|y}\mu(d)$$

• 组合恒等式

• • 组合递推式：

$$\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$$

• 二分图最大匹配，最小点覆盖与最大独立集

二分图最大匹配 $=$ 最小点覆盖，最大独立集 $=$ 总点数 $-$ 最小点覆盖。

• 二分图匹配可行边，必经边，可行点与必经点

先对原图跑最大匹配，在残量网络上跑 tarjan 求强连通分量。

可行边：该边为原图上的匹配边或两点属于相同的强连通分量。

必经边：该边为原图上的匹配边且两点属于不同的强连通分量。

可行点：所有可行边的所有端点。

必经点：统计非必经点，从 $S$ 走流量为 $1$ 的边走到的左部点与从 $T$ 走流量为 $0$ 的边走到的右部点为非必经点。

• Hall 定理

定义二分图的完美匹配为匹配数量 $=$ 左部点数量。

CF1882E2 Two Permutations (Hard Version)

好题啊，E1 的构造已经让我想了好久了，E2 的第一步转化真的很妙！

需要最优化，首先考虑 dp，但是发现 dp 状态难以定义，所以需要对操作进行一些转化。

考虑在排列的开头加一个 $0$，标记整个排列的开头位置。当对位置 $x$ 进行一次操作时，等价于将位置 $x$ 与 $0$ 的位置进行交换。

操作完后，整个序列就是从 $0$ 开始往后的数循环构成的排列，这样我们就完成了 $O(1)$ 的交换操作，而且交换两个元素也比原题意的神笔操作正常一些。

由于 $n,m\le 2500$，所以考虑枚举两个排列最后的形态（即 $0$ 的位置），随后对于每一种最终状态。

对于一种对应的状态，对应点之间连边后，最少步数是去除所有一元环后，所有 $0$ 不在的环的步数是环长 $+1$，$0$ 所在的环的步数是环长 $-1$。而如果要多一些步数去拟合另一个排列，可以操作 $2$ 次。

将所有结束状态分为奇偶两类，对应的取 $\min$ 即可，构造方案是容易的。

感觉最为逆天的地方还是在于第一步加入一个 $0$ 的转化，后面的做法还是较为套路的。

CF1879F Last Man Standing

10 月了，是不是马上要 NOIp 了，是不是马上要省选了 /fad。

CodeForces-1007C

转化为找平面上的一个点，对于两维同时倍增，如果都不在对应区间，则同时缩小步长。

CodeForces-995F

容易进行朴素 dp，$f_{u,i}$ 表示 $u$ 子树，根 $\le i$ 的方案，发现转移就是点积和前缀和，所以多项式度数 $\le n$，直接插值即可。

Luogu-P7554

对于询问进行二分，check 是查询区间某个区间内的值个数可以主席树维护。

CodeForces-788E

发现 $p_1$ 和 $p_5$ 根本不重要，可以直接移到 $p_2$ 和 $p_3$ 上，对于每个值域开线段树维护。

CodeForces-724E

构造题的解决方法较为丰富，感觉需要较多的人类智慧与灵感，但是一些套路的构造题通常会有以下几种构造方式。

递归/分治构造

我们能够解决一个较小规模问题的构造，而构造一个大规模的问题可以在构造完小规模的子问题后进行合并，从而完成构造。

CodeForces-1773K King’s Puzzle

题意：给你两个整数 $n,k$，你需要一张构造一张简单无向联通图，没有自环，使得点的度数集合大小恰好为 $k$。$1\le k\le n\le 500$。

如果我们能够构造出 $n=k+1$ 的情况，那么只需要在外面接一条链即可完成构造。

考虑该问题的特殊情况 $n=k+1$ 时应该如何构造。当 $n\le 3$ 时是容易的。

当 $n>3$ 时的 $(n,k)$，考虑构造子问题 $(n-2,k-2)$，然后再新建两个点 $(u,v)$，将 $u$ 与子问题中的 $n-2$ 个点一一连边，将 $u$ 与 $v$ 连边，这样能恰好使度数集合大小增加 $2$。

至此，本问题得到解决。

二进制构造

说到 $O(n)-O(1)$ rmq 问题，最广为认知的就是四毛子，但是四毛子不好写，因此来记录几个较为好写的 $O(n)-O(1)$ rmq 算法。

分块

• 优点：较为好写，且能够做到严格的 $O(n)-O(1)$。
• 缺点：不能算非常好写。

将序列按照每 $\log n$ 个元素分为一块，序列将被分为 $\frac{n}{\log n}$ 块，求出每个块内的最大值，并在块间建立 ST 表。并且对于每个块内，处理出前缀和后缀最大值。

对于一个询问 $[l,r]$，找出被完全包含的区间，求出这几个块之间的最大值，对于两边的散块，调用前后缀最大值即可。

至此，预处理时间复杂度 $O(\frac{n}{\log n}\cdot \log n+n)=O(n)$，查询时间复杂度 $O(1)$。

看似结束了，但是如果询问的区间被包含在了一个块内该怎么办呢？

在预处理时，可以对于每个块内分别跑一遍单调栈，维护块内每个位置的前缀的后缀最大值。同时，单调栈内的元素个数是 $O(\log n)$ 的，每个元素可以用他在块内的位置表示，值域也是 $O(\log n)$ 的。

我们可以将者 $O(\log n)$ 个值域为 $O(\log n)$ 的数压缩成一个值域为 $O(\log^{\log n} n)$ 的 long long 记录下来，不难发现这个 long long 可以在入栈和弹栈的时候同时维护。

另一种存贮方式是对于每个数，记录这个数到当前块的开头哪些位置在单调栈中，每次询问是可以使用 __builtin_ctz 函数进行查询。这种方式所使用的空间更少，单个元素的值域是 $O(2^{\log n})=O(n)$。

P9531 [JOISC 2022 Day4] 复兴计划

首先有结论：对于每条边，在最终方案中会被选择的 $X$ 是一个区间。

将所有的边按照边权排序，那么他被选择的代价关于 $X$ 是一个绝对值函数。对于每条边，找出前一条能与他形成环的边，那么分界的 $X$ 就是两条边边权的平均值。

找出每条边的 pre 可以在 $O(nm\alpha(n))$ 的复杂度内完成，并将询问离线，按照 $X$ 排序后维护一堆一次函数的和即可。

CF1801E Gasoline prices

对于每一个形如 $\{(u_1,v_1),(u_2,v_2)\}$ 的限制，等价于将两条路径上对应点并查集合并，最后在同一个并查集中的元素的值必须相等，因此在求出最后并查集的合并情况后，只需要求出每个并查集连通块内部 $L$ 的 $\max$ 与 $R$ 的 $\min$ 即可，这一部分是容易计算的。

接下来考虑如何在合理的复杂度内计算出并查集的合并情况。

首先发现，将所有点全部合并联通只需要进行 $n-1$ 次合并操作，因此有效的合并操作是 $O(n)$ 的，只需要依次找到有效的合并操作即可。

考虑将每个点赋值上他所在并查集的祖先的点权，每次产生一个新的限制时，可以二分两条链上权值组成的序列的 LCP，第一个不同的位置即为需要合并的两个点。

因此只需要支持对于一个树上的单点修改，链上 hash 查询操作，可以直接把树拍成 dfn 序之后用树状数组维护。

哎，9 月了，还在这里摆，忍不了了！

CodeForces-1864G

观察一下性质，然后直接数数，最后是一些阶乘的乘积。

Luogu-P5631

按照边权线段树分治，用并查集维护连通性。

CodeForces-1615F

将操作做差分转化为交换元素，求每个间隔对答案的贡献。

CodeForces-1354G

先通过随机寻找一个石头，再通过倍增和二分来寻找第一个礼物的位置。

CodeForces-838C

P5366 [SNOI2017] 遗失的答案

好题！首先判掉 $G\nmid L$ 的情况，接下来将 $n$ 与 $L$ 都除上 $G$。

假设 $L$ 分解质因数后的集合为 $\{(p_i,\alpha_i)\}$，原问题等价于选出一个 $\{1,2,\dots n\}\cap\{x|L\equiv 0\pmod{x}\}$ 的子集 $S$，满足对于任意的 $(p_i,\alpha_i)$，$\min_{x\in S} cnt_{p_i}(x)=0$，$\max_{x\in S}cnt_{p_i}(x)=\alpha_i$。

由于 $\omega(L)=|\{(p_i,\alpha_i)\}|$ 很小，最大只有 $8$，因此考虑状压。

定义一个长度为 $16$ 的二进制数 $s$，前八位表示对于每个 $(p_i,\alpha_i)$，是否满足 $\min_{x\in S} cnt_{p_i}(x)=0$，后八位则表示对于每个 $(p_i,\alpha_i)$，是否满足 $\max_{x\in S}cnt_{p_i}(x)=\alpha_i$。

从而每个 $1\sim n$ 中的 $L$ 的因数都可以被表示为值域为 $[0,2^{16})$ 的整数，原问题等价于选择一些数，使得他们的或和等于 $2^{16}-1$。

首先把二进制表示 $s$ 相同不同的数归为一类，假设第 $i$ 类的二进制表示为 $s_i$，个数为 $c_i$。

考虑 dp，令 $f_{i,j}$ 表示考虑了前 $i$ 种二进制数，其状态的或和 $=j$ 的方案数，则有：

$$f_{i,j}\to f_{i+1,j}\\ f_{i,j}\to f_{i+1,j|s_{i+1}}\times (2^{c_{i+1}}-1)$$

但是询问中需要钦定某个数不能选，因此考虑做出前缀与后缀的 dp，假设分别为 $f,g$。