the set of tricks.
13671135581
二项式反演
\[\begin{aligned} f(n) = \sum_{i = n}^m \dbinom{i}{n} g(i) \\ \rightarrow g(n) = \sum_{i=n}^m (−1)^{i - n} \dbinom{i}{n} f(i) \end{aligned} \]
欧拉反演
\[\begin{aligned} \sum_{d|n}\varphi(d) = n\\ \rightarrow \sum_{i=1}^n\gcd(i,n) = \sum_{i=1}^n\sum_{d|\gcd(i,n)}\varphi(d)\\ =\sum_{i=1}^n\sum_{d|i}\sum_{d|n} \varphi(d) \\ =\sum_{d|n}\sum_{i=1}^n\sum_{d|i} \varphi(d) \\ =\sum_{d|n}\frac{n}{d}\varphi(d) \end{aligned} \]
组合恒等式
\(\dbinom{n}{k}=\frac{n}{k}\dbinom{n-1}{k-1}\)
\(\dbinom{n}{k}=\dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}\)
\(\sum_{k = 0} ^ {n} \dbinom{n}{k} = 2^n\)
\(\sum_{k = 0} ^ {n} (-1) ^k \dbinom{n}{k} = 0\)
\(\sum_{k = 0} ^ {n} k \dbinom{n}{k} = n 2 ^ {n - 1}\)
\(\sum_{l=0}^n\dbinom{l}{k} = \dbinom{n + 1}{k + 1} n, k \in \mathrm{N}\)
一些结论
\[d(ij) = \sum_{x \mid i} \sum_{y \mid j }[\gcd(x, y) = 1]\]\[[\gcd(i, j) = 1] = \sum_{d | \gcd(i, j)} \mu(d) \]
\[\begin{aligned} &\sum_{i = 1}^{n} \sum_{j = 1}^{m} [\gcd(i, j) = k] \\ = &\sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor} [\gcd(i, j) = 1] \\ = &\sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor} \sum_{d \mid \gcd(i, j)} \mu(d) \\ = &\sum_{d = 1}^{\min(\lfloor \frac{n}{k} \rfloor, \lfloor \frac{m}{k} \rfloor)} \mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor \end{aligned} \]
整除分块
for (int i = 1, last = 1; i <= n; i = last + 1) { last = min(n / (n / i), m / (m / i)); res += f() * (n / (i * k)) * (m / (i * k)); }
noip 之前也写过这么个玩意儿。
然后我又整一个，算是个补充，这 \(3\) 个月。
- 集合之间的转移考虑一个点一个点按顺序合法地往里面加
- 打表发现答案的范围，转移次数的范围，转移区间的范围。
dp优化考虑把状态映射在图上，考虑状态点构成的几何关系。DAG上的dp转移考虑建图跑- 多个操作独立分开思考
- 状压可以往
DAG上靠 - 二分图构造方案数对每个连通块单独考虑
- 善用具有 “一键抹销” 功能的操作
dfs/bfs生成树与构造题- 在一张图中，匹配数等于点数减去最大独立集
- 对于每个树上的点求答案考虑换根
- 树上任意一点的最远点是树直径上的两个端点之一
- 序列的方案数考虑按顺序往序列里一个一个把数加进去线性
dp - 序列的方案数考虑区间
dp - 序列的方案数考虑笛卡尔树上
dp/ 支配区间 - 捡锤子和砸墙是一种操作
- 矩阵的方案数考虑在行列分开计数
- 矩阵的方案数考虑处理行的同时维护列线性
dp - 相对位移，选一点钦定不动作为端点，其它点相对移动
- 网格图行列连边，有障碍物也无所谓
- 对于操作顺序对答案没有影响的问题考虑从左往右依次做
- 对序列计数可以等价为序列的前缀和 / 差分序列计数
- 对前缀和 / 差分序列计数注意值域的变化
- 两变元移项之后互相限制
- 图上只加边或者只删边的考虑并查集配合线段树转化成序列上的询问
- 序列反转时考虑不变的是元素间的距离，那么只需要考虑某个端点就能刻画出整个序列了
- 序列计数考虑如何转化成另外能与之一一对应的序列计数
- 树上信息可以递归时数据结构合并解决
- 必要条件或许是简单的，可以尝试构造解然后判断是否满足要求转化成充分条件
0/1排序是简单的，0/1比大小是简单的，考虑二分某数字后转化成0/1比较问题- 对于转移上多的一维偏序关系，考虑外层套树状数组解决
- 相信启发式合并
- 树上一点到多点的距离和考虑转化成
lca深度问题，lca深度和考虑树剖解决 - 拓展上一技巧，一点对多点的查询考虑把查询挂在
lca上处理 - 后效性 dp 在高消过不了时一定可以消掉后效性
- \(E(x^k) \not = E(x)^k\) 是废话
- 状态转移复杂度过高时考虑预处理降复杂度
- 两点往上跳问题要不树剖要不倍增
- 偏序关系用 值域 和 链接符号 \(< \ or \ \le\) 刻画
- 正难则反
- 对于每个恰好 \(i\) 求答案可以转化成对 \(\ge i\) 求答案然后容斥
- 博弈论首先判断是否有必胜策略
- 对于扔区间到序列上的
dp，可以把左右端点拆开，在从左往右dp时只要保证左端点数 \(\ge\) 右端点数就可以继续转移 - 对于期望 \(E = p_i \times i\) 可以把 \(i\) 换成 \(\sum_{j = 1}^{i}\) 然后两个求和改变顺序，把单点的概率 \(p_i\) 转化成后缀概率和
- 排序影不影响答案？排序影不影响答案？排序影不影响答案？
- 答案范围允许枚举吗？答案范围允许枚举吗？答案范围允许枚举吗？
- 相加为质数作为限制条件时，奇偶分开连边，特判一
- 相邻 \(3\) 个不相同等价于 \(2i\) 和 \(2i - 1\) 不相同
- 要永远相信根号算法的速度
- 矩阵过大，考虑能不能压缩得小一点
- 枚举子集不要写萎了
- 合并两个等价子问题时为保证不重复需钦定
- 分治好用
- 数列 \(\gcd\) 考虑差分
- 不定方程有解的条件：\(\gcd\) 可以作为计数的状态
- 若有两个序列 \(a,b\) ,如果一次只挪动一个元素，记 \(sum_a\) 为 \(a\) 的前缀和序列，\(sum_b\) 为 \(b\) 的前缀和序列，那么把 \(a\) 挪成 \(b\) 需要的最小的操作步数是 \(\sum_{i=1}^{n - 1} \mid sum_{a_i} - sum_{b_i} \mid\) 。
- 等差数列用
hash判，hash用线段树维护 - 线段树同时做
hash和离散化 - 找所有解考虑构造特解，再在特解的基础上拓展
- 中位数考虑
0/1或者-1/1赋值 - 强连通块内点等价时考虑缩点
dp范围通过分析性质缩小- 区间的拼接可以理解成最短路
- 看到 区间覆盖 想起 灯笼照明状态
- 最小环用倍增
floyd - 状态只存在两个元素（字符、数字、、、）可以拉到图上理解，配合线性规划
dfs树构造，返祖边证明，构造从数据范围限制入手- 多源改良版
spfa bfs一圈一圈更新- 矩阵
dp可以建树跑dp - 删除和加入对于计数等价时可以互相转换
- 手玩小范围的结论尝试推广
- 偏序关系用拓扑刻画
- 对于题目限制拆成几个等价的小限制，把某一维限制作为状态干掉
- 贪心构造，
dp计数 - 重新描述？
- 单点性质往往是容易被发现且容易被维护的
- 按顺序动态加入贡献比对已经构造完成的序列更容易发现性质
- 期望是否有对称性？
- 拆绝对值
- 当操作要使两个序列相同时，思考这个操作能不能倒着做，如果可行，考虑把这两个序列同时该变成一个非常简单的形势。
- 记住构造唯一的树的方式
- 当题面说操作失败不算次数时考虑把这一次当作
dp的维度 - 树上颜色相同的连通块可以缩点
- \(\gcd\) 可以通过辗转相除转换
- 与序列最大值最小值相关的题可以想到笛卡尔树
- 平面内生成一个新块的情况只有两种，一线贯穿或者两线相交
- 注意棋子的等价性
- 两个序列共用一套操作是考虑二分图
- 交错构造
- 满足条件的情况是否是简单的？
- 带权最小覆盖状压一半搜一半
- 子树内外分开计算
- 这种从高往低二进制贪心题想不出正解时可以利用数据的随机性加上特判去骗分
- 当
dp的状态转移后会“重置”时可以把这个作为一个阶段，因为条件不变，但问题范围缩小。 - 还是注意单点贡献，当区间操作难以刻画时用点去反向计算
- 可以圆方树做吗？
- 容斥 ???
- 当做法极其恶心时（需要大型数据结构）肯定有更小清新的做法
meet in the middle???- 对于很多题，只需要考虑最终状态就可以了，淡化过程
- 状态数真的那么多吗？
- 当复杂度肯定与某一个变量无关的时候，应当去思考这一个维度有没有整体的性质，能不能整体维护，能去掉无效状态吗，能压缩状态吗？
- 反悔贪心 ???
- 能不能更数学化地去刻画特殊点的性质（被覆盖的次数等？）
- 网格图走路
- 暴搜剪枝 ???
- 能不能想起来
Tarjan？？！ Trie树上对二进制进行处理- 当
dp复杂度不对的时候可以把状态和结果中某一位对换来降低复杂度 - 在修正主义的道路上不断前行