Prutekoi's blog

rt

• 拉普拉斯展开：对于一个方阵A，A的行列式相等于某一行所有元素的值乘上他的代数余子式的和。

• 范德蒙德行列式：每一列都是从1开始的等比数列的矩阵的行列式是 $\prod_{1\leq j<i\leq n}(x_i-x_j)$，其中 $x_i$ 是第 $i$ 列的公比。数学归纳可证。

• 求代数余子矩阵可以用伴随矩阵的性质：$A^*=|A|A^{-1}$ 求出伴随矩阵，再转置就是代数余子矩阵了。

• 积和式是行列式的式子中去掉了-1的幂，是NP问题，但因在%2意义下1=-1故可以转化为求行列式。

• 异或高斯消元可以bitset优化。

• 矩阵树定理:基尔霍夫矩阵=度数矩阵-邻接矩阵，它的任意一个代数余子式即为生成树数量。

• 定义一棵生成树的权值是所有边的权值积。我们将度数矩阵中的度数改为边权和，邻接矩阵连通性改为边权，就可以求出来所有生成树的权值和。

• 我们将度数矩阵改为入度，邻接矩阵改为有向边的邻接矩阵，以 $x$ 为根的生成树形图个数是 $C_{xx}$（代数余子式）

• 一张有向图 $G$，若有欧拉回路（弱连通且每个点入度等于出度，这也可以推出强连通），则欧拉回路的数量是 $t_1(G)∗\prod_{i=1}^n(deg(i)−1)!$，其中 $t_1(G)$ 表示以1为根的生成树形图的个数，$deg(i)$ 表示 $i$ 号点的入度。
  来自清芷酱的证明：假设欧拉回路从1号点开始，$p(x)$ 表示最后一个进入 $x$ 的边，发现 $p(2),p(3)\dots p(n)$ 形成了以1为根的树形图（因为它们不可能有环，会出矛盾），然后就把剩下的边任意排序，这样是 $t_1(G)∗deg(1)!*\prod_{i=2}^n(deg(i)−1)!$ 的，但每种方案都被算了 $deg(1)$ 遍，除下去就好了。得证。Orz rqy

• ln和exp的泰勒展开（在求解低项数多项式ln和exp时直接应用定义有奇效）

  $ln(1-A(x))=-\sum_{i\geq1}\frac{A(x)^i}{i}$

  $exp(A(x))=\sum_{i\geq0}\frac{A(x)^i}{i!}$

• dfs树一个重要性质：若v,w是图中节点且dfn[v]<=dfn[w]，则任意从v到w的路径必然包含它们在dfs树中的一个公共祖先。

• 莫反的一个扩展

• 与一个数互质的数是成对的，即 $(m,n)=1\Leftrightarrow(n-m,n)=1$。更相减损术。。故可得到

• $\sum_{i=1}^ni[(i,n)=1]=\frac{1}{2}([n=1]+n\varphi(n))$

• 二分图的最小顶标和=最大权匹配。（顶标和：给每个点定一个点权，满足任意一条边的边权小于等于两点权之和，顶标和为点权之和）

• n以内所有素数的倒数和是 $O(\ln\ln n)$ 的，埃氏筛复杂度就是这么估计的。

• 贝尔数（集合 $\{1,2,3,...,n\}$ 划分的方案数）的EGF为 $e^{e^x-1}$，硬着头皮推的证法，还可以直接用论文里的结论：有标号集合计数为元素生成函数的exp。

• 一些斯特林数有关的恒等式，推式子是会用到的呜呜呜

• $m^n=\sum_k{n\brace k}{m\choose k}k!$

• ${n\brace k}k!=\sum_i{k\choose i}(-1)^ii^{n-i}$

• 第一个是 $n$ 个小球装进 $m$ 个盒子的方案数，第二个是容斥，这俩互为二项式反演。

• $n!=\sum_k{n\brack k}$

• 这个是考虑到排列是置换即可显然。

• 一道关于“反排序”的结论题

• 真分式可以分解为部分分式和，可能可以帮助直接解出系数，而不用执行多项式算法（对要求的次数非常高时大概只能用这种方法），工具%5Cleft(1-x%5E%7B3%7D%5Cright)%5Cleft(1-x%5E%7B5%7D%5Cright)%7D)（需要梯子），分解前一定记得先给分母分解因式。。

• Miracle博客里的%%%，里面貌似有一点小错误，进入左边时我觉得应该要mod左边多项式的连乘积。
  n- 只选偶数个的指数生成函数 $1+\frac{x^2}{2!}+\frac{x^4}{4!}+\dots=\frac{e^x+e^{-x}}{2}$，类似地，只选奇数的为 $\frac{e^x-e^{-x}}{2}$。就是用负数的幂消掉了对应奇偶性的项。

• 扩展卢卡斯需要模数分解成的每个 $p^k$ 都是线性可以承受的范围。一般出出来就能看出来，所以感觉不怎么会出

• 手写的二叉堆在随机数据下插入复杂度期望 $O(1)$。考虑深度为 $log$，往上交换每条边的概率都是 $\frac{1}{2}$。而弹出却是满的 $log$。

• 算组合数真有意思。

• $O(n^2)$ 递推。无任何限制。

• $O(n)$ 预处理阶乘和阶乘逆元。适用于 $n,m$ 不大，且存在逆元（模数为大质数）

• 卢卡斯定理。适用于模数为小质数。$n,m$ 都可很大，预处理复杂度为模数相关，单次 $O(log)$，好像可以看成常数啊？

• 阶乘分解质因数约分再相乘。适用于 $n,m$ 不大，模数非质数。只能单次 $O(n)$ 求一个。

• 上下约掉 $(n-m)!$ 后暴力 $O(m)$ 相乘。适用于 $m$ 不大且不大于模数，模数是质数，但 $n$ 很大。单次 $O(m)$。

• 扩展卢卡斯。适用于模数分解为的质数的幂都不大。单次复杂度与分解为的质数的幂线性相关，与 $n,m$ 的对数相关。

• 发现组合数的 $n^2$ 递推是线性变换，用矩乘优化。适用于 $m$ 很小，模数可以非质数，复杂度为 $O(m^3logn)$。

• 模数是 $10^9$ 范围的非质数。预处理阶乘与模数互质的部分和逆元，再记录阶乘和逆元对于模数每个质因子的指数。设模数有 $c$ 个质因子，则预处理复杂度 $O(nc)$，求单个 $O(c)$。
  字符串相关：

1. 串 $s$ 有一个长为 $p$ 的 border $iff$ 串 $s$ 有一个长为 $|s|-p$ 的周期。
2. 若 $p$ 和 $q$ 都是 $s$ 的周期，$p+q-\gcd(p,q)\leq|s|$，则 $gcd(p,q)$ 也是 $s$ 的周期。（注意这里有长度限制，于是后面的性质中都在满足这个长度限制）
3. 字符串 $u,v$ 满足 $2|u|\geq|v|$，则 $u$ 在 $v$ 中的所有匹配位置构成一个等差数列。（这个性质用了上面的第二条性质，$2|u|\geq|v|$ 为了满足 $p+q-\gcd(p,q)\leq|s|$，让这个性质直接可以用。）若匹配至少三次，则匹配位置公差为 $u$ 的最小周期。
4. 串 $s$ 的所有不小于 $|s|/2$ 的border长度构成等差数列。（这个是用了下border与周期的转化，然后也是通过不小于 $|s|/2$ 来使第二条性质得以应用。）
5. 串 $s$ 的所有border长度排序后可分成 $O(\log|s|)$ 段，每段是一个等差数列。（将所有border按长度分类，$[1,2),[2,4),[4,8)...[2^k,n)$，每一类都可以类似第四条证出是等差数列。）
6. 一个串的所有回文后缀长度可以表示成 $O(\log n)$ 个等差数列。
7. 如果 $s$ 是一个双回文串（$s=a+b$，$a,b$ 都是回文串），则存在一种拆分方法 $s=a+b$ 使得 $a$ 是 $s$ 的最长回文前缀或 $b$ 是 $s$ 的最长回文后缀。（这个证明起来有一点神仙，倒过来倒过去的）
8. 最大循环同构串：设 $s[p,n]+s$ 是 $s+s$ 最大后缀，则 $s[p,n]+s[1,p-1]$ 即为最大循环同构串。

• 若 $p$ 是质数，则 $\prod_{i=0}^{p-1}(x-i)\equiv x^p-x\pmod p$，这个可以插值证（用一下费马小定理）

• ~~$10^7$ 左右的质数（哈希表用）$9999991$（但是到底它和 $999979$ 哪个快还真不好说）~~不需要记啊/cy，直接写个判质数的函数然后for循环找一下不就好了/cy

• 竞赛的四五元环计数均可以用 $O(\frac{n^3}{w})$ 的时间求出，且常数为 $\frac{1}{2}$。（三元环就直接用个度数就好了）代码可以见（新板子）

• prufer序列可以用来枚举无根有标号树。树转序列的过程是每次删掉一个标号最小的叶子，并把与它相连的点的标号输出，直到只剩两个点（因为这时与叶子相连的还是叶子了）。序列转树的过程是维护一个集合 $S$，初始时为 $1$ 到 $n$。每次找出集合中不在序列中的最小的数（就是第一次删掉的叶子），并连接这个数和序列首项，并都删除。（都可以用set维护）

• 通过观察构造过程可以发现prufer序列中某数出现 $x$ 次则在树中度数即为 $x+1$。

• 我们有一个式子 $F(x_1,x_2,...,x_k)$，要求 $x$ 之和等于给定数的所有方案的 $F$ 值之和。若它可以写成 $F_1(x_1,x_2,...,x_k)+F_2(x_1,x_2,...,x_k)+...+F_m(x_1,x_2,...,x_k)$，每个 $F_i(x_1,x_2,...,x_k)=\prod g_{ij}(x_j)$（即贡献可以拆成好多部分，每部分都是每个 $x$ 独立的乘法原理），则可以把每个 $g_{ij}(x_j)$ 换成 $\sum_kg_{ij}(k)x^k$，然后用这些生成函数相乘再相加得到就是了。

• $O(\sum sz[x]^2)=O(n^3)$。

• 设 $f(x)$ 是一个 $k$ 次多项式，则数列 $a_i=f(i)$ 是一个 $k+1$ 阶齐次线性递推。~~（这个咋证啊？）~~用拉格朗日插值表示多项式，代入的 $k+1$ 个点是 $i-1$ 到 $i-k-1$。然后把 $i$ 带进去就会发现系数与 $i$ 是无关的，所以是常系数。

• 下降幂的后向差分结构与通常幂的求导一样。即 $(x+1)^{\underline{k}}-x^{\underline{k}}=kx^{\underline{k-1}}$。求和的结构与通常幂的积分一样。即 $\sum x^{\underline{k}}\sigma x=\frac{x^{\underline{k+1}}}{k+1}+C$（不定和式）经常要求的前缀和就直接拿 $x+1$ 和 $1$ 往里代再相减就好了（它是左闭右开的）。于是见到求多项式前缀和或者已知 $f(x)$ 求 $f(x+1)$ 的题目用下降幂处理会很好。

• 若 $F(x)=\frac{1}{G(x)}$，且 $G(x)$ 是一个 $n$ 次整式多项式，要求 $F(x)$ 的负指数幂的系数，看起来很难处理。如果直接求逆得到的仍是一个整式多项式。所以考虑一下怎么出来负指数。发现系数翻转可能出现负指数。但是如果先求逆再翻转，得到的其实仍是整式。那么我们尝试先把 $G(x)$ 翻转再求逆。 $H(x)=\frac{1}{x^nG(x^{-1})}=x^{-n}F(x^{-1})$。设 $H(x)=\sum_k h_kx^k,F(x)=\sum_k f_k x^{-k}$，则 $h_kx^{-k-n}=f_{k+n}x^{-k-n}$，所以我们可以求出 $f$ 的 $-n$ 次幂及以下的系数。第二类斯特林数列就是用到这个，把我卡了好一会。
  （真是难为我了。。。这玩意有正常一点的推法的。$F(x)=\frac{1}{G(x)}$，求 $F(x)$ 的负指数的系数的话，可以 $F(x^{-1})=\frac{1}{G(x^{-1})}$，这样就是求这玩意的正指数次幂，再对右边做些通分之类的变换。上面的做法与这等价。）

• $x^{\overline{-k}}=\frac{1}{(x-1)^{\underline{k}}}$，这个直接拿 $x^{\overline{-k}}=\frac{(x+k-1)!}{(x-1)!}$ 推就好了。。

• 硬币博弈：一排硬币，有一种特定的规则选择一些硬币，要求最右边的硬币是反面朝上，并把它们全部翻面。结论是游戏的SG函数为所有反面朝上的硬币的异或和。即 SG(11010)=SG(10000)^SG(01000)SG(00010)。我们可以对这个游戏转化，每次操作改为给最右边位置的硬币数减 $1$，选到的其他位置硬币数加 $1$。然后考虑给每个硬币染上不同颜色，一个硬币生成出的硬币和它颜色相同，这样就显然看出对于每个硬币是独立的，可以直接异或。而这个游戏的必胜策略和原问题是一样的。如果A必胜，B某次选择了奇数个硬币的堆，那A照必胜策略走，否则他可以模仿B使得奇偶性不变。

• 平面上有一些黑点和一些白点，每次给出三个白点询问这个三角形内有没有黑点。这个可以三方预处理 $O(1)$ 询问的。预处理是选定一个原点，枚举两个白点，计算一下两个白点和原点之间有向面积中有多少黑点。询问时套用求面积的方法（即三角剖分）看看得出是否为 $0$ 即可。然而边界问题不好处理，这个做法大概只能处理边界上的点计算的时候。方法是我们随机选择一个实数点为原点，那么原点-黑点-白点三点共线的概率就接近为 $0$。但是会有白点-黑点-白点三点共线，这时这两个白点就不能在同一个三角形内了，给这个值赋成正 $INF$ 即可（无关有向面积，否则还可能抵消）。

• tarjan求完SCC之后编号的倒序就是一个拓扑序。可以少写一个拓扑排序，而且lyd书上那种构造2SAT方案的方法就利用了这个。

• gcd,or,and 都满足不断扩展，不同的值只有log个。这种性质要利用好。

• $\lim_{n\to \infty}\sum_{i=1}^n\frac{1}{i^2}=\frac{\pi^2}{6}$（巴塞尔问题）。不过算复杂度时其实不用知道具体的极限，因为已经有结论 $\sum_{i=1}^\infty \frac{1}{i^c}$ 在 $c>1$ 时都收敛，所以它就是一个常数，对复杂度没有影响。

• 任意两个自然数互质的概率是 $\frac{6}{\pi^2}$。这个不会证233

• 无向图中的简单环有这样的性质：找出图的任意一棵生成树，每条非树边和它覆盖的树边都构成一个环，那么所有的简单环都能由这些环异或出来（字面意思）。大概就是考虑任意一个简单环上的所有点在生成树上一定是直上直下的关系（如果分叉代表不可达），然后每个点度数都为 $2$，随便构造一下发现所有的简单环都能被构造出来。于是如果题目中的环是具有异或的性质的话，那么有用的环其实只有 $m-n+1$ 个。（所有的非树边）

• 网格图（只能向右向上）中点到点的方案数可以方便地用组合数算出，而点到矩形的方案数（到矩阵中每个点的方案数之和）则需要推导一番。设 $F(x,y)$ 为 $(0,0)$ 到 $(x,y)$ 的方案数，则它除了用组合数算以外，还有类似dp的式子。可以枚举从哪里进入了最后一列，得到 $F(x,y)=\sum_{i=0}^yF(x-1,i)$。同样也可以从行展开。再次展开得到 $F(x,y)=1+\sum_{0\leq i<x,0\leq j<y}F(i,j)$。$1$ 是因为 $F(x-1,0)$ 无法再次展开。这个用组合意义来看的话，相当于枚举了路径中最后一条横线最左端的点下方的点（之后的路径固定，向右向上）。而如果最后一条横线在 $y=0$，则没有下方的点，于是要加 $1$。然后我们就有了类似二维前缀和的结构，差分一下即可。然后矩形到矩形的也就可以做了（因为变成了四个点到矩形的问题，不过常数就是16了/jk）

• 。。。。2-SAT输出方案好弱智啊。不用任何拓扑排序或者dfs。判定合法性之后，图成为由SCC构成的DAG。然后只用满足两个条件：选了一个点之后它能到达的点都要选，变量的两个取值不能有互达关系。考虑不能有互达关系比较容易做到。对于一个变量，只需选择拓扑序在后的取值，则它一定不能到达反面的取值。而拓扑序只需判断SCC的编号即可。但是这样能否保证满足第一个条件？可以的。因为我们加入了逆否命题，所以图有一种对称的关系，一个SCC一定有一个和它对应的SCC，其中包含的元素一一对应。这样对于这些元素一定都归属了同一个SCC。而不同SCC之间的，$x$ 能到达 $y$，则 $y$ 拓扑序会更大，$y'$ 拓扑序会更小，于是一定满足条件。就这么简单！结论是对每个变量取所属SCC编号较小的取值。

• 一张满足所有点入度等于出度的有向图，它的所有强连通分量之间不连通（每一个联通分支都是一整个强连通）。考虑对于一个联通块如果没有缩成一个SCC，那么对于两个SCC之间的边，它给SCC1提供了一个出度，给SCC2提供了一个入度，这样就不满足条件了。多重集的排列构成的置换有关题目

• or卷积是高维max卷积的特例，and卷积是高维min卷积的特例。一维max卷积的话可以构造出前缀和，相乘再“反演”回去。这是一种容斥。反演约等于容斥嘛。然后高维max卷积就是高维前缀和咯。高维前缀和用类似FWT的思路，复杂度为 维数*元素数（体现在FWT上就是 $\log n*n$）。（lcm和gcd分别可以看作高维max卷积和高维min卷积，一般打暴力用QAQ）

• 线性基个数的OEIS编号 A006116 。大小为 $q$ 的域上 $n$ 维向量空间中的 $m$ 维子空间（异或线性基的话 $q=2$，人话就是值域为 $0$ 到 $2^n-1$，线性基中有值的位置有 $m$ 个）个数为高斯二项式系数 $g_q$
  所以公式就是

$g_q(n,m)=\frac{\prod_{i=0}^{m-1}(q^{n-i}-1)}{\prod_{i=0}^{m-1}(q^{m-i}-1)}$

长得很像二项式系数的公式，于是它有很多与组合数类似的性质，所以被称为高斯二项式系数。
还有一种思路：线性基的统一化改造FOR(i,0,k)FOR(j,i+1,k)if(a[j]>>i&1)a[j]^=a[i]执行完这个之后可以保证只有 $a[i]$ 有第 $i$ 位。这样操作完之后不同的线性基就是本质不同的。
根据这个思路直接搜索构造合法的线性基也可以求出本质不同线性基个数。

#include<bits/stdc++.h>
using namespace std;
int n,ans,pw[99];
void dfs(int x,int now,int num){
    if(x==n){ans+=now;return;}
    dfs(x+1,now,num);
    dfs(x+1,now*pw[x-num],num+1);
}
int main(){
    scanf("%d",&n);pw[0]=1;
    for(int i=1;i<n;i++)pw[i]=2*pw[i-1];
    dfs(0,1,0);cout<<ans;
    return 0;
}

• 一个数 $n$ 作用 $O(\log n)$ 次 $\varphi$ 就会变成 $1$。因为偶数的 $\varphi$ 最少除以 $2$，而除了 $1,2$，其他数的 $\varphi$ 都是偶数。这个就是考虑如果 $x$ 与 $n$ 不互质，那么 $n-x$ 与 $n$ 也不互质。

• 一个数 $m$ 有原根的条件是 $m=2,4,p^e,2p^e$，其中 $p$ 是奇素数，$e$ 是正整数。一个有原根的数 $n$ 有 $\varphi(\varphi(n))$ 个原根。这使得枚举数，再判定是否为原根成为一个可行的做法。因为 $\varphi(\varphi(n))$ 并不会很小，在 $n\leq 10^7$ 时对于所有的质数，随机取一个数是原根的概率最小值也达到了 $0.180525$。这说明期望 $6$ 次就可以找到原根。运用原根的性质的时候要特别注意原根的幂遍历的是简化剩余系，即与模数互质的所有数。

• $x^n\equiv m\pmod p$， 其中 $p$ 是奇素数，每个有解的 $m$ 有 $\gcd(n,p-1)$ 个不同的解。（把数表示成原根的幂来证明）。而奇素数的幂的情况需要处理一下转化成奇素数的情况。

• $x^n\equiv m\pmod 2^k$，其中 $m$ 是奇数，（$k$ 足够大），那么每个有解的 $m$ 有 n&1?1:2*lowbit(n) 个不同个解。而 $k$ 较小时解数只可能减小不可能增多。看起来匪夷所思，是打表得出的，不会证证出来了233

首先证明 $x^n\equiv m\pmod {2^k}$ ，$n,m$ 都是奇数，则 $x$ 有唯一解。
假设在 $k<q$ 时成立，而 $(x+2^{q-1})^n\equiv x^n+2^{q-1}\pmod {2^q}$ （用二项式定理展开）
也就是每次都能够成功地扩展出 $2^{q-1}$ 个新的 $m$ ，所以 $k=q$ 也成立...

而现在我们设 $n=2^cd$，$d$ 是奇数。于是原同余方程可以写成 $(x^d)^{2^c}\equiv m\pmod {2^k}$。
而根据上面的推导，$x$ 和 $x^d$ 有一一对应的关系，所以方程变成了 $x^{2^c}\equiv m\pmod{2^k}$

对奇数 $x$ 有 $x^{2^{k-2}}\equiv 1\pmod {2^k}$ 。
仍然归纳证明。假设这条性质对 $k<q$ 时成立。
$x^{2^{k-2}}-1=(x^{2^{k-3}}+1)(x^{2^{k-3}}-1)$
而左边括号是 $2$ 的倍数，右边括号是 $2^{k-1}$ 的倍数，故得证。

所以当 $c\geq k-2$ 时只有 $m=1$ 时有解，且有 $2^{k-1}$ 个解。
故 $c=k-2$ 时满足上述性质，尝试对 $k$ 归纳，让 $k++$ 。

$(x+2^{k-c-1})^{2^c}\equiv x^{2^c}+2^{k-1}+...\pmod{2^k}$
...后面是二项式展开中的其他项。我们只要证明这些项都同余于 $0$，就说明我们可以完整地从 $k-1$ 扩展到 $k$。（大概是先内部分化一下，每一组大小都除以 $2$ ，再复制一份，大小又乘 $2$ 。）
然后只要知道 ${2^c\choose q}$ 有 $c-log_2lowbit(q)$ 个因子 $2$ （$q$ 和 $2^c-q$ 都有 $log_2lowbit(q)$ 个因子 $2$）
就可以比较简单地证明出来了。然后就没有了。

震惊！中国剩余定理与多项式插值本质相同，简直是匪夷所思（U群里说的，EI也认同了/se）

如果 $c$ 是一个变量，$a$ 是一个一维数组，那么 $c[a]$ 表示的就是 $a[c]$。而 $c[a][b]$ 表示的就是 $b[a[c]]$（先作用 $a$ 再作用 $b$）啧啧啧啧太鬼畜了

• 关于二分图匹配的一些比较难办的问题（必需点，可行点之类的），一般都用到了一个东西：考虑两个最大匹配的对称差（异或），一定是一些长度为偶的交替环或者交替链。如果一个匹配点是偶链的一端，那么它就不是必需点。大概这么分析就会比较简单。

• 对于不存在欧拉回路的图 $G$，若最少用 $a$ 条路径将图的每一条边经过一次，最少在图 $G$ 中加入 $b$ 条边使之成为欧拉图，则 $a$ 一定等于 $b$。这个定理考虑这两种方案之间都可以互相生成即可。这样就会有一种转化关系，可能用得上。

• splay和treap的启发式合并都是均摊 $O(nlogn)$ 的（最后合并出的东西有 $n$ 个节点）。
  因为有这两个定理
  
  
  splay在启发式合并时需要把小splay中的元素升序或降序插入到大splay中，treap在启发式合并时也是按顺序插入，不过要记录上次插入元素的位置，从那个位置开始找要插入的位置。（所以splay好写）

• splay和treap都可以通过某种带权的操作来得到更优的复杂度（一个点的权值在某种意义上表示访问这个点的频繁程度）。而splay不需要任何多余的操作，因为它具有强大的自适应性。treap则需要使用一种依赖权值的随机方法，随机权值为 $f(x)=x^{\frac{1}{w}}$，自变量在 $[0,1]$ 随机（这使得权值大的点靠近根的概率更大）。使用这种带权去优化多层树的嵌套问题（树链剖分或点分治 套数据结构）可以优化复杂度。比如树链剖分中每个点的权值定义为轻子树大小之和，每条重链维护一棵带权的平衡树，则可以优化到一个 log。然而这个东西用splay实现貌似就是LCT，这应该就是LCT优秀的原因。。

• 后缀数组查询一个串的出现次数：字典序比 s# 小的后缀的数量减去比 s 小的后缀的数量，# 代表一个虚拟的最大字符。

• 算法复杂度的各种符号：Θ-等于，O-小于等于，o-小于，Ω-大于等于，ω-大于

• 约数个数的界： $n$ 的约数个数为 $O(n^{\frac{1.067}{\ln \ln n}})$，还有一个比较松的上界是 $n^{\frac{1}{3}}$

• $[x=1] mod p$ 可以转化成 $\frac{p^x mod p^2}{p}$，于是一些形如 $\sum [a_i=1]$ 的计数就可以通过这个东西转化。如JZOJ6566，给定一张图，求有多少种选点的方案使得导出子图联通。保证边两边的编号绝对值之差不大于12。这个如果硬做的话大概是复杂度与贝尔数相关的连通性dp。而它给的模数为 $2$。于是运用上面的转化，就变成了求所有选点方案的 $2^{联通块个数}$ 的和。发现这是一个染色模型，于是状压之前的染色即可。而如果模数变大的话，状压颜色又要使用最小表示法，大概又变成了贝尔数相关。所以模数只能出到 $2$。

• 斐波那契膜大于 $5$ 的质数 $p$ 的循环节：如果 $p \mod\ 5$ 等于 $1$ 或 $4$（$5$ 是 $mod\ p$ 的二次剩余），则最短循环节为 $p-1$ 的约数，否则为 $2(p+1)$ 的约数。（二次剩余那里用了二次互反率，也可以用欧拉准则判定）其他质数可以暴力特判。$mod 2:3,mod 3:8,mod 5:20$。
  膜 $p^k$ 的循环节：$f(p)*p^{k-1}$，其中 $f(p)$ 为膜 $p$ 的循环节。（最短循环节实际上就等于它，但是现在数学上貌似只证出是它的约数）
  膜任何一个数的循环节：先分解质因数，对每个质数幂求一下，再lcm即可。用中国剩余定理证。

• $\frac{f(n)}{n}\leq 6$，当且仅当 $n=2*5^k$ 时取等。

• 打表发现 $f(n)=n$ 当且仅当 $n=24*5^k$。所有的 $n$ 一直作用 $f$ 都会收敛到这样的值。

• 广义fib循环节，大概合数的时候也有一样的结论吧...还要注意推导中的一些特殊情况：比如 $a^2+4b$ 或 $-b$ 同余于 $0$，这种情况大概特判一下就好了吧..

• $\varphi(xy)=\frac{\varphi(x)\varphi(y)gcd(x,y)}{\varphi(gcd(x,y))}$

• 树上选 $k$ 条不相交的链是凸的。证明是树形dp然后归纳。因为凸卷积也凸。（？）

• Huffman点分治与边分治与全局平衡二叉树等价（djq说的）

• 最长反链构造

• 长度为 $n$ 的+-1序列，满足所有位置前缀和非负的方案数是 ${n\choose \lfloor\frac{n}{2}\rfloor}$。考虑画出图象，翻转坐标系，变成了经典的路径计数，然后考虑枚举最后可能的终点，每个终点用翻折法计数，再累加发现可以消去一堆，变成了一个组合数。

• 稀疏矩阵的问题很多都可以利用（稀疏矩阵乘法很快）来用线性递推知识解决。（因为线性递推要先求出 $I,A,A^2,A^3...$）比如解稀疏线性方程组、求稀疏矩阵行列式、稀疏矩阵秩之类的（复杂度 $O(n(n+c))$，$c$ 为非0位置数）...详见zzq论文

• 如果确定一个无穷数列的最短递推式长度 $\leq c$，那么取前 $2c$ 项的最短递推式就是了。

• 整式递推论文中大概提到这些内容：
  论文中的定义比较反人类，一个比较正常一点的形式：
  $a_n=\sum_{i=1}^mP_i(n)a_{n-1}$，其中 $P_i$ 为有理多项式，$m$ 称为阶数，$\max(deg P_i)$ 称为次数。这样大概可以很容易看出随便一个递推很容易是整式递推。（唯一一点限制是不能有常数项？？不过可以变换一下形式，比如 $a_n=n$ 既有 $a_n=a_{n-1}+1$ 又有 $a_n=\frac{n}{n-1}a_{n-1}$）
  数列是整式递推当且仅当其OGF $A(x)$ 的所有阶导数的张成空间有限（也即存在一个 $m0$ 使得对于任意 $i>m0$，$u^{(i)}$ 可被 $u,u'...u^{(m0)}$ 线性表示（系数是有理多项式））（称这样的多项式为微分有限）
  如果 $u$ 微分有限，$v$ 为代数多项式（是一个多项式方程（系数为有理多项式）的解），则 $u(v)$ 微分有限。（这里记住一些比较简单的函数如 $e^x,x,\frac{1}{x}$ 等都微分有限可以便于解题）
  整式递推数列作一些看起来很合理的操作之后仍是整式递推数列（线性变换，移位，卷积，点积）
  若一个整式递推的阶数为 $m$，次数为 $d$，则可以在 $O(n^2md)$ 求出一个有限数列的整式递推，对于无限数列取足够大的 $n$ 正确率就比较高。板子
  可以在 $O(\sqrt{nd}(m^3+m^2\log(nd)))$ 求出整式递推数列的第 $n$ 项，若 $m,d$ 为可忽视的常数则复杂度为 $O(\sqrt n\log n)$。
  非常神奇的是在随便翻具体数学时发现第7章第20，55道作业题就是论文中的一个定理的证明。。

• 根据原根的定义可以得到原根是二次非剩余，而根据勒让德符号是积性的，可以得到一个数是二次剩余当且仅当它是原根的偶数次幂。这个可以给“二次剩余是如何分布的”这个问题一个感性的认识，有时证明也用得上。

• 模奇素数 $p$，若 $x$ 不为 $1$ 或 $p-1$，则它与逆元奇偶性不同（奇怪的结论增加了）

• 「CodePlus #7」同余方程 的证明，刚半天决定咕咕咕了。。

• 两个数论函数的狄利克雷卷积是 $O(n\log n)$ 的，但是一个数论函数卷一个积性函数可以做到 $O(n\log\log n)$。由Mertens 第二定理，$\sum\limits_{p\leq n}\frac{1}{p}=\ln\ln n+C+O(\frac{1}{\ln n})$
  于是分析一波可以得到所有 $p^k$ 的倒数和也是这个界。

for(int i=1;i<=n;i++)q[i]=a[i];//这个a可以不积性
    for(int i=1;i<=tot;i++)
        for(int j=n/p[i];j;j--)
            for(LL k=p[i];j*k<=n;k*=p[i])
                q[j*k]=(q[j*k]+1ll*q[j]*phi[k])%mod;

直观的理解可以认为它是dp，但更深层的理解就是把积性函数的狄利克雷生成函数分解了，然后一个一个与这个数论函数卷积。
而如果两个积性函数的卷积，我们可以在每个质数幂处卷积，这样就得到了目标函数所有质数幂处的值，再根据目标函数积性就可以得到所有值了。卷积部分的复杂度是 $O(\sum_p\log^2_pn)$，可以分析出是 $O(\frac{n}{\log n})$ 的（因为 $\sum\limits_{p\leq n}\frac{1}{(\ln p)^2}$ 这东西可以这么估计：根据素数定理，m附近的素数密度大约是1/ln(m)，所以可以估计为sum 1/(ln^{3(i))，大概就是n/log}3(n)吧（照抄的U群回答，我也不太懂）），于是整个就是 $O(n)$ 的！具体实现可以写一个dfs，枚举质数的幂构造出每个数，顺便卷积算就可以了。

• 现在最优的计算 $\pi(n)$ 的算法复杂度为 $O(n^{2/3}\log^{-2}n)$。计算 $\pi(n)$ 与计算积性函数求和时min25筛等筛法运用的技巧很多是共通的。

• 质因数分解最优的复杂度为 $O(\exp((1+o(1))\sqrt{\ln n\ln\ln n}))$，是次指数级的。而整数分解与模意义下离散对数具有很大的相似性，它们都是BQP的.（照抄的冬令营课件），就有一些用Pollard's Rho 等质因数分解的算法来解决离散对数的问题，一般比BSGS要更优，但是太神仙了..

• 三元环和四元环的计数是很简单的。考虑把无向边定向，度数小的点连向度数大的点，这时有一个结论就是每个点的出度都 $\leq O(\sqrt m)$。这显然。然后三元环计数的复杂度是 $\sum in_iout_i$，四元环计数的复杂度是 $\sum d_iout_i$。这样因为 $out_i\leq O(\sqrt m)$，$\sum in_i=\sum d_i=O(m)$，于是复杂度就是 $O(m\sqrt m)$。网上很多证明更复杂，有些还是伪证...（大连小也是对的，而且要特别注意四元环时是先走有向边还是无向边，这跟定向的方式有关系。）

• 注意 $k$ 倍角正余弦的问题与复数域十分有关系。因为有 $e^{i\theta}=\cos \theta+i\sin \theta$，所以这个东西就变成了快速幂。然后表示一下复数域就行了。

• 不相交路径计数：有 $n$ 个起点个 $n$ 个终点，它们是有序的，即从第 $i$ 个起点到第 $j$ 个终点的路径一定会与从第 $j$ 个起点到第 $i$ 个终点的路径相交。然后现在要求 $n$ 条路径互不相交的方案数。我们有 Lindström–Gessel–Viennot lemma，只要构造一个矩阵，$a_{ij}$ 为第 $i$ 个起点到第 $j$ 个终点的方案数，然后求一个行列式即得答案。这也没什么玄妙的，其实就是容斥。因为一个逆序对数为 $x$ 的方案至少有 $x$ 个交点。

• 后缀数组的sa数组是后缀树的关键节点按dfs序排序，而如果我们想建出关键点的虚树，那么可以用height数组建出笛卡尔树。这就是虚树。

• 贝尔数可以 $O(n)$ 求，我们只要把它写成斯特林数的和，再把斯特林数拆开（卷积的那个式子），然后发现约掉一些东西之后两部分可以独立，然后就变成 $\sum_{i+j\leq n}\frac{(-1)^i}{i!}\frac{j^n}{j!}$ 这样就可以直接求了。
  
  如果套这个结论可以求更靠后的项。。

$\sum\binom{n-im}{i}$ 可以在 $O(\min((n/m)^2,m\log m\log n))$ 的时间求出，于是可以出到 $n,m\leq 10^9$..如果我们枚举 $i$ 暴力，那么是 $O((n/m)^2)$ 的。而如果利用 $\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$ 代换，可以得到一个递推式 $f(n)=f(n-1)+f(n-m-1)$，直接套线性递推即可。

ETT用经过就记录的欧拉序，换根操作相当于把整个序列循环移位。

kdt带插入的话替罪羊重构是不太行的，EI原话：“那个复杂度上面的指数和平衡度关系很大”。大概就是说kdt的复杂度分析是很依赖它完全平衡的性质的。具体来说：因为我们在分析时会用到：$T(n)=2+2T(n/4)$（这个是询问一条直线穿过矩形的情况，把这个算出来之后整个就能算了）那个 $n/4$ 就是用到完全平衡的性质，那么如果递推式改成 $T(n)=2+2T(n/a)$，得到 $O(n^{\log_a2})$。在 $a$ 取 $3$ 时得到 $n^{0.63}$。可以看出它对平衡度要求还是很高的。
EI还说平衡度设置在 $0.5+O(\frac{\log n}{\sqrt n})$ 也还行，“这样平衡度的偏差还是比较小，并且均摊的代价大概是 O(sqrt) 的”，不过它确实要求比较严格，在 $n=10^6$ 时就是 $0.52$。。
因为它是根号复杂度的数据结构，所以我们容易想到根号重构来维护。我们开两棵kdt，平时在第二棵树插入，根号重构，过大时就和第一棵树的元素一起重建成第一棵树，查询在两棵树查询，设 $B$ 次重构后并入第一棵树，则

可以得到重建的总复杂度是 $O(n^{\frac{5}{4}}\log n)$，不会对整个复杂度造成影响，于是皆大欢喜。
kdt的按方差划分和轮流划分其实影响根本不大，最劣是所有点退化到一条线的情况，这时只有 $\frac{1}{d}$ 次划分是有效的，会对常数产生一些影响，二维时常数最多差 $2$ 倍。
最近邻查询只能用计算几何三角剖分和v图相关的知识了，非常毒。建出v图，然后平面图点定位。。
而曼哈顿距离最近/最远，我们直接讨论一下位置关系，然后就变成了矩形查询最值，直接离线线段树，如果要插点就主席树就行了...