错误总结、套路集锦
带公式的项目前面编号会显示不出来，并不会修
常识
- 标准差是方差的算术平方根，所以说所谓方差是不需要开根的
- cmp函数不能在结构体内部
- 注意！multiset的count复杂度和对应元素数量相关
- 注意！set等非随机访问结构的lower_bound，必须调用结构内部的，用stl的那个函数会一次O(n)
- 在无c++11的时候，queue系列的swap是o(n)的
错误总结
- 不等式的移项 一定要分析正负性
- stl的比较重载不能随便搞，一定要满足传递性和大小情况单一性（stl用<和>推导出=）
- fft得答案时要round
- 带取模计数，判无解不能用答案=0，因为答案可能是模数的倍数
- 注意 s&bin[i] 和 (s&bin[i])>0 的不同（惯犯
- 用指针a[]表示数组的时候，sizeof a只会得到单位大小，而不是整个数组的大小
- 如果一个东西的插入复杂度是通过势能分析保证的（如sam、朴素pam、ac自动机）
那么通常不能支持删除操作，因为可以多次进行再回撤高复杂度的操作 - 在CF上，任何自选模数的题都应该rand或者双模数，例如路径关键点、hash
- 线段树如果值域int，求mid的时候可能爆int
- 我习惯定义的循环宏fo，注意循环变量是ll的情况
- 感觉自己经常在想题过程中把题意扭曲了……以后如果卡住了要再三检查前面的题意转化是否出问题
做数论题的常用姿势
调和级数，$\sum_{i=1}^n n/i=O(n*ln(n))$，所以像$g(n)=\sum_{d\mid n}f(d)$这类较简单狄利克雷卷积无脑做是一个log的，但可以更快，类似高维前缀和的思想做。复杂度$=O( \sum \frac{n}{prm_i}=所有数的质因子个数和 )=O(n*log_2(log_2 n))$
1
fo(i,1,prn) fo(j,1,N/prm[i]) f[j*prm[i]]+=f[j];
关于约数，一个数num的约数可以$O(\sqrt{num})$枚举，可见约数个数上界为$2\sqrt{num}$；如果枚举一个数的倍数就是调和级数的复杂度，可见M内所有数的约数个数和上界为$O(n*ln(n))$；有时可以分析一个数的不同质因子数量（通过$2*3*5…>num$），典型题目
phi小性质：「对于n>1，1~n中与n互质的数的和为$n \times \varphi(n)/2$ ，证明：$gcd(n,x)=gcd(n,n-x)$」、「深度为log级别。考虑n为偶数，则$\varphi(n)\le n/2$；若n为奇数，$\varphi(n)$一定是偶数」；一个显然正确的式子：$\varphi(ab)=\frac{\varphi(a)\varphi(b)d}{\varphi(d)}(d=gcd(a,b))$
关于整除：「$当x \le \sqrt n,\left \lfloor \frac{n}{\left \lfloor \frac{n}{x} \right \rfloor} \right \rfloor=x$」、「$\forall a,b,c\in\mathbb{Z},\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor$」、「数论分块，将$\lfloor \frac{n}{i} \rfloor$相同的i合并起来计算，不同个数是$O(\sqrt n)$的，因为当值比根号大时，分母一定在根号内」
第二条的证明：
$$
\begin{split}
&\frac{a}{b}=\left\lfloor\frac{a}{b}\right\rfloor+r(0\leq r<1)\ \Rightarrow \\ &\left\lfloor\frac{a}{bc}\right\rfloor =\left\lfloor\frac{a}{b}\cdot\frac{1}{c}\right\rfloor =\left\lfloor \frac{1}{c}\left(\left\lfloor\frac{a}{b}\right\rfloor+r\right)\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c} +\frac{r}{c}\right\rfloor =\left\lfloor \frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor\
\end{split}
$$$\sum_{i=1}^n d(i)^2约为nlog^2n$（毫无数学依据）
对于一个素数P，任何P以内的x，其倍数在模P意义下可以表示出所有P以内的数
x不断对「<x」的数取模，只会进行$O(logn)$ 次，讨论一下就知道了
对于$\prod_{\sum x_i=S} x_i或\prod_{\sum x_i=S} x_i^k$这样的东西，不管在树上还是序列上，可以考虑其组合意义：每个块内恰放k个球。于是可以边走边放，记录当前所在的块内有多少个球，然后在位置上看要不要放，在间隔看要不要放隔板。
$gcd(x_1,x_2…x_n)=gcd(x_1,x_2-x_1,….,x_n-x_{n-1})$，经典问题就是区间加法求区间gcd
数学
- 期望有个套路的转化，恰好到达的状态的概率*步数之和，等价于所有未到达的状态的概率之和，这个你可以通过「把当前概率推到上面的步数个祖先上」理解
- 若$H*W且gcd(H,W)=1$的网格左下角射出$(0,0)\to(1,1)$的光线，碰到边框就反射，则$\forall x,y \in N,(x+y)\%2=0,(x,y)会被经过$，其中不在边框上的点会被经过多次，且上述结论是充要的
- 一个1到n的集合，选若干个不互质的数，要求和最大；bzoj3308
结论：选出的每个数最多两个不同的质因子，且一个在根号n内，一个在根号n外，并不会证明 思维僵化如我，$O(n)$求n个数的逆元，类似递推求阶乘逆元一样，求出$\prod a_i$的逆元再还原出前缀逆元，配合前缀积求出单个逆元
树形结构
点分的本质：点分树上点对的LCA一定也在原树两点路径上，可以从这个LCA统计这个路径的信息；然后点分有个小trick，如果处理一个块的复杂度通过根号分治达到$O(B\sqrt B)$，总复杂度为$n*\sum (n/2^i)^{1/2}=n \sqrt n*\sum \frac{1}{2^i}=n\sqrt n$
直径的性质（在一棵边权非负的树上）：「与该点最远的一定是直径的某个端点」、「直径的中心唯一」、
「每个点的最远点，都一定经过直径的中心」、「改一条边，端点最多变化一个」重心和直径有个类似的结论：在一个点权为0/1的树上考虑带权直径、带权重心，「记下两个不重点集各自的任意一条直径端点，点集并的直径的端点一定能在这四个点中产生」，「记下两个不重点集各自的任意一个重心，点集并的所有重心一定都在这两个重心的路径上」
树上点集的连通块个数=点-边，极度常用；另外将点集搞起来的最小虚树边数=「dfs序排序后成环，相邻两个求路径长度」/2
很多模型能转化为树形：
A: 互不重叠只包含的区间（最近一个包含作为fa），例如析合树、一些性质题
B: 某个变量只有单一指向（作为fa），这个其实是最常见的，举例：跳跳棋
C: 入栈出栈序列也是可以表示为树形结构的，节点x的子树大小为k，则表示x先入栈，然后子树内的元素为[x,x+k-1]且都更晚入栈更早出栈，举例：HDU5181 numbers
虚树上（或者给定点集）找到原树某个点的祖先中第一个在虚树上的：第一个祖先肯定是第一个dfs序能包含的节点，且所有祖先的dfs序区间是包含的，等价于找到$dfn_y \leq dfn_x$的y中$dfn_y+siz_y-1$最小的那个，如果能离线最简单的写法是按照dfs序从小大大回答询问，用个int维护合法y中最小右端点来自哪里，这样是线性的；如果强制在线可以线段树上询问$[1,dfn_x]$上最小右端点来自哪里
多个点的lca=dfs序最小和最大点的lca
用可重路径覆盖一棵树的每条边，最小数量为度=1的点数量，向上取整地除2。构造很简单，见下面经典问题2，那么就是要找到一个点作为根，各个子树叶子数$mx*2 \le sum$，这就是个带权重心，构造直接用堆模拟没毛病，多出来那货随便连一个点就是对的；例题:「BalticOI 2015」网络
用路径交可以判断是否存在一条路径包含某节点，求交的话，路径$(a,b)与(c,d)$如果有交，一定是$lca(a,c),lca(a,d),lca(b,c),lca(b,d)$中深度最大的两个点间路径
给定一棵树结构，每个点标号成排列，要求每个点的编号比子树其他点小，合法方案个数=$\frac{n!}{\prod siz_i}$，这个我是感性理解，独立地乘上这个子树成立的概率
随机序列的笛卡尔树深度为log（每次期望为分成两半），即上升序列长度为log；笛卡尔树的期望子树大小也是log级别的
树上高斯消元可以线性：将每个方程写成$f(x)=k_x*f(fa)+b_x$的形式，这个从叶子开始就能搞出来，最后$f(rt)=b_{rt}$
图论-其他
- 对于无向图，一个点双内如果有奇环，那么内部每条边都至少在一个奇环中；点双内有奇环的充要条件是在dfs搜索树上存在一个「一条非树边+若干树边」组成的奇环
- 让拓扑序的逆字典序最小，应建反向边跑大根堆
- 无向图的dfs树不会有横叉边，这种边很恶心所以一般随便找个生成树的时候都会选择dfs
- 一个图如果只有奇环，那么只会有简单环，因为两个奇环相交会产生偶环
- 基环内向树森林修改出边得到一个环的最小步数为孤立环+叶子；策略的话先说一棵基环树，就是将环上每个点a挂的树内所有叶子向下个叶子连接，然后a的上一个点连向a的树得到的叶子链的首部。加入其它孤立环的话，从某个a那里拆就只会增加一次操作。例题：projecteuler522 Hilbert’s Blackout
- 众所周知森林有$联通块=点-边$，同理仙人掌有$联通块=点-(边-环)$
字符串
- 串的计数，枚举长度，建立间隔为长度的关键点（调和级数），然后每个串会经过一个关键点，枚举关键点算贡献
举例：「NOI2016」优秀的拆分、股市的预测、poj3693 Maximum repetition substring - 如果一个串是双回文串，一定存在一种分割，满足前面是最长回文前缀或者后面是最长回文后缀
- 同一个串重复无限次得到串的最长回文子串，如果不是无限长，则最多是两个合并起来
决策算法
找前k优的区间，固定一个点后，左边的优秀情况是极值问题。可以用堆维护左边，取出一个位置后把左边区间拆成两半放回去，举例：超级钢琴、树上的路径
对于一些求大小为k最优集合的题目，不妨尝试猜测k一定为k-1的增量，感觉一般都不太好证明，不过可以画一画感受一下有没有反例:D
解题思路
目前碰到处理棘手的删除问题的方法主要有两个，基本都需要离线
一个是倒着做，这个对题目的要求较高；另一个是贪心，离线后按出现时间处理，然后按结束时间贪心
举例：「bzoj4644」经典傻逼题「集训队互测2015」最大异或和、「bzoj5040」航线规划「bzoj4229」选择平方形式，可以转为为数点对，或者是进行两次然后相同的情况，又或者可以处理其差分1,3,5,7,9,11……
举例：NOI2009 管道取珠， 蔬菜，学习小组，WC2007石头剪刀布很多计数问题要求排列，可以时刻保证排列性，然后插入一个数，将比它大的数+1
举例：51nod1296 有限制的排列、以及一些比较经典的树上dp跟极值有关的区间问题，考虑一下已知存在某个极值贴着区间外所带来的影响（笛卡尔树dp之类的）
举例：hnoi2016序列、hnoi2017影魔、ioi2018会议、noi2019机器人的50分部分分（都有题解）问从状态A操作到B，可以考虑倒着操作，适用于做某种操作可达性、构造
表格图上行和列两侧成二分图，$(i,j)有棋子则i到n+j连边$
求只包含一点、只不包含一点的信息的一类问题
套路大概是分治，大概没法直接说懂，给出两道题，选一道题看，然后大概就能理解并做出另一道题了
假如在序列上有很多区间，但这些区间长度都是L，那么可以对序列按L分块，于是每个区间一定是「某个块一段后缀」+「某个块一段前缀」组成，举例：「LR11」Misaka Network 与 Accelerator
有的问题如果确定一部分，另一部分的限制会很强，可以考虑meet in middle，如CF1257F
技巧
- 取模题对拍时，如果暴力能做范围很小，可以改小模数检验
- 对于比较陌生的题目操作形式，可以多造几组数据来模拟，找到一些性质，用这些性质转化题目
经典问题
- 权值总和为S的背包，可以$O(S \sqrt S)$ 完成，和根号分治类似有根号级别的不同权值，每种权值单调队列优化多组背包即可
- 若干个不同的集合，要求选最多对数满足来自不同的集合；当$mx>sum-mx$，显然答案为$sum-mx$，否则考虑在一个堆中每次取最大的两个集合拿出一对数再塞回去，答案为$\lfloor \frac{sum}{2} \rfloor$；如果每次要k元组，那应该只能用堆模拟了？不过有一个不错的式子，反过来对于一个答案W，有哪些k可以至少取到W：$kW \le \sum min(count_{num},W)$，这个的必要性显然，构造证明式子是紧的：先把大于W的那些给W组都丢一个，小的那些选最少的若干个丢一个进去，肯定能搞出W个（其实这样构造的话组的大小只会有A和A+1两种，找A的那些放即可）
- max n的排列的收尾相接相邻差；最小化这个，可以递增奇数+递减偶数
- 两个凸函数f和g，做$(max,+)卷积，即h_{i+j}=max\ f_i+g_j$，得到的h也是凸函数，证明显然；$h_{i+j+1}的(i,j)构成，与h_{i+j}的(i,j)构成$，一定能只改变一个，于是可以双指针线性合并
- 01分数规划，例如最大化平均数，二分判断是否存在$sum-ln*T \ge 0,\sum (val-T) \ge 0$
- 一个数的所有约数的哈斯图的最长反链（定义一个数被另一个数整除时可比）。首先肯定是Dilworth去转成最小链覆盖，然后观察这个图的特性发现这其实每个点$\prod p_i^{k_i}可以看做(k_1,k_2..k_{cnt})$，然后发现是可以按$\sum k_i$分层的，而分层dag的最小链覆盖显然是最大的那个层的大小，对于本题就是$\prod_i (\sum_{j=0}^{mx_i} z^j)$的最大系数，可以分治NTT做。事实上一个结论是这东西的系数是先递增再递减的，且其最高点为$[z^{\lfloor (\sum mx)/2 \rfloor}]$，相关资料可见此OEIS。例题：CF1257G Divisor Set
- 麻将，「CF1110D」Jongmah
其他
- 设cnt(x)为x二进制下1的数量，$cnt(a \oplus b)$ 为奇，当且仅当一个cnt为奇，另一个是偶
因为两个1在一起是偶，不在一起也是偶 - 二进制数相减，不要考虑借位，而是允许-1存在，加法类似
- 所有n的排列中，奇排列数p=偶排列数q，因为交换任意两个元素必定使逆序对奇偶性变化，对所有p交换某两个位置，$p \ge q，同理q \ge p$