写法优美的常用函数
写法优美的常用函数
收录一些优美的常用函数写法。
分解质因数
有人根本不会用 do while 和 vector。
1 | vector<int> v(0); |
SCC
缩点。
1 | int dfs(int u){ |
最短路 Dijskstra
如果 \(dis\times n\le 8\times 10^{18}\)，完全可以它们压成一个数。
1 | priority_queue<LL,vector<LL>,greater<LL>> q; |
网络流相关
网络流
内容主要为自己对网络流的一些理解和一些典例。
一些约定：
- s 为源点，t 为汇点
- 对于集合 \(S,T,T\subseteq S\)，约定 \(S-T\) 为从 \(S\) 中删掉 \(T\) 中每个元素之后的集合
- 网络流图为 \(G=(V,E)\)，边 \((u,v)\) 容量记为 \(c_{u,v}\)
最大流最小割定理和增广路定理
这两个定理是网络流问题的核心定理。
内容
最大流 = 最小割。
残量网络中不存在增广路是当前流为最大流的充要条件。
证明
若当前流为最大流，显然不存在增广路。
若当前流等于某个割，显然当前流为最大流，且该割为最小割。
若不存在增广路，我们证明当前流等于一个割。
令 \(S=\{v,\exist\ p_{s,v}\}\)，\(S\) 即 \(s\) 在残量网络中能到达的点的集合。令 \(T=V-S\)。显然 \((S,T)\) 是一个割，对于当前残量网络 \(G'=(V,E')\)，一定有 \(\forall x \in S,\forall y\in T\)，边 \((x,y)\) 满流，否则 \(y\in S\)。容易证明当前流恰好为 \(S\) 到 \(T\) 的所有边的容量和，也就是割的大小。因为此时原图 \(S\) 到 \(T\) 所有的边流量为容量，\(T\) 到 \(S\) 的边流量为 \(0\)，所以流量为 \(S\) 到 \(T\) 的边的流量之和，也就是割 \(S,T\)。
算法
Dinic
考虑对残量网络 bfs 分层，强制流量只能流向下一层，再进行一次 dfs，求限制下所有的增广路，搞定。
复杂度 \(O(n^2m)\)
每次增广复杂度为 \(O(nm)\)，共计增广 \(n\) 次，因为每次增广都会让 \(dep[t]\) 增加 1。
每次增广的复杂度不是很好证，但加了当前弧优化其实就很松。
代码记在脑子里了，不放了。
ISAP
咕咕咕
HLPP
咕咕咕
费用流相关
一般指最小费用最大流，暂时没啥感觉，不写。
最小割
非常常见的一个网络流模型应用。
核心思想
通过构造一个图的割到决策方案的映射，其中决策必须可拆分计算，求出最小的代价，一般来说决策的限制如果比较奇怪就应该考虑最小割。
常用于规划 \(0/1\) 独立贡献决策问题。
适用条件
- 不能存在负容量边权，我不知道有没有人会，反正我是不会。
1.最大闭合权子图问题
给定一张有向图，点带权（权可以为负），选一个子图出来，要求如果 \(u\) 选了那如果存在 \((u,v)\)，那 \(v\) 也要选。求最大权值和。
决策贡献独立，决策类型为 0/1。应该可以最小割。令割中与 \(s\) 同集合的点为选择的点，与 \(t\) 同一个集合的点为未选择的点。那么每个点应该和 \(t\) 连一条流量为权值的相反数的边，代表选它的代价，再对于每条 \((u,v)\) 从 \(u\) 向 \(v\) 连一条 inf 边,代表选了 \(u\) 不选 \(v\) 的代价。考虑这张图的一个最小割，它必然不会包含 inf 边，也就是说，我们选了 \(u\) 在 \(s\) 中一定会让 \(v\) 在 \(s\) 中，所以一定合法。然后发现原问题的每一个答案都可以和图上的一个不含 inf 边的割一一对应，故最小割就是原问题的答案的相反数。
这张图有负数，不行，所以考虑先默认选所有正数。那么选负数的代价为相反数，不选正数的代价为本身。
那么应该从 \(s\) 向正权点连边，从负权点向 \(t\) 连边，最后对于 \((u,v)\) 从 \(u\) 向 \(v\) 连 inf 边即可。
一些科技的总结
总结一些科技
主要收录比较神仙的，实用的算法技巧。
快速取模
原理
找到一个近似 \(m^{-1}\) 的形如 \(m'>>k\) 的数。
不妨就取 \(k=64,m'=\lceil\frac{2^{64}}{m}\rceil\)
然后 \(a\%b = a-a\times\lfloor\frac{a}{b}\rfloor = a-(a\times m'>>64)\)
纯纯的整数运算，经过误差分析，可以知道后式结果最多多减去一个 \(m\)，判断掉就行。
因为 \(a\) 常常是 \(\text{long long}\) 级别的数，所以开
__int128
优化据说有 \(5-6\) 倍，如果模数是
const，编译器会自动帮忙用这个优化。
代码
1 | struct barrett{ |
注意事项
- 为啥
im,m用ull,uint，因为m=2时，会爆long long。 - 可以重载括号。
光速乘
用于计算两个 long long 级别的数乘积对一个 long long 级别的数取模的结果。
1 | long long multi(long long a,long long b,long long mod){ |
1 | long long mul(long long A, long long B, long long P){ |
原理很简单，long double 的精度误差虽然有，但是我们 -0.5 之和核查范围变成了 [0,1]，肯定不会超出这个。
C++ 标准中要求了 unsigned long long 类型在溢出后保证为原值对 \(2^{64}\) 取模的结果，所以直接用就行。
第二个原理类似，在 G++ 编译器中，O2 中，保证 long long 的溢出行为有定义。
推荐用第一个，各个平台都不会出锅。
如果 \(P\leq 10^{14}\) 可以改成 double
判断一下是否减少了就行。
常用数学结论证明汇总
简单事实
- \(\gcd(a,x_1)=1,\gcd(a,x_2)=1 \iff \gcd(a,x_1x_2)\)
- 若 \(n\ |\ m\) 则 \(\phi(n)\ |\ \phi(m)\)
- 若 \(\gcd(a,p)=1\),则 \(ax,x \in [1,p]\) 模 \(p\) 意义下互不相同，反之亦然。
模运算和满足的运算率
注：符号均为模 \(p\) 意义下。
- 加法交换律
- 加法结合律
- 乘法交换律
- 乘法结合率
- 如果 \(p\) 为质数 ，\(g\) 为 \(p\) 的一个原根，则 \(\log_x(y) = \frac{\log_g(y)}{\log_g(x)} \pmod {p-1}\)
复数运算满足的运算性质
- 加法交换律
- 加法结合律
一些抽象代数内容
事实1
令 \(g\) 为 \(p\) 的一个原根，记 \(\log_g(x) = y\)，模 \(p\) 意义下 \(x\) 的阶数为 \[ \Large ord = \frac{\phi(p)}{\gcd(\phi(p),\log_g(x))} \]
证明1
显然 \(g\) 的阶数为 \(\phi(p)\)，又因为 \(g^y = x\)。所以 \(x^{ord} = 1\)。
然后证明 \(x^i,i \in [1,ord]\) 互不相同。
反证，如果相同，设为 \(i,j(i\ge j)\)，那么 \(g^{yi} = g^{yj}\) 得到 \(\phi(x) |\ y(i-j)\) 两边同时除以 \(\gcd(\phi(p),y)\)，得到 \(ord |\ y'(i-j)\)，其中 \(\gcd(y',ord) = 1\) ，得出 \(i-j \ge ord\) 矛盾。
所以 \(x\) 的阶数为 \(ord\)
裴蜀定理
内容
\(\exist\ x,y \in \Z\) 使得 \(ax+by=\gcd(x,y)\)
证明
归纳构造。
先证明 \(\exist\ x',y'\in \Z\) 使得 \(bx'+(a\%b)y' = \gcd(a,b)\)
即 \(ay' + b(x'-\big\lfloor\dfrac{a}{b}\big\rfloor y') = \gcd(a,b)\)
构造 \(x = y',y=x'- \big\lfloor\dfrac{a}{b}\big\rfloor y'\) 即可满足条件。
递归证明构造式子，得到边界证明 \(\exist \ x,y\) 使得 \(\gcd(a,b)x + 0 \times y =\gcd(a,b)\)
令 \(x=1,y=0\)
欧拉函数是积性函数
即证明若 \(\gcd(n,m) =1,\) 则 \(\phi(n*m) = \phi(n) *\phi(m)\)
证明一
考虑若干个同余方程组 \[ x ≡ r_1 \pmod n\\ x ≡ r_2 \pmod m\\ \] 列出 \(n,m,nm\) 意义下的最小缩系 \(S_n,S_m,T\)
容易证明 \(\forall\ r_1\in S_n, r_2 \in S_m\)，存在唯一 \(x \in [1,nm]\) 是上同余方程组的解，且 \(x \in T\)。
存在唯一就是 EXCRT， \(x\in T\) 由事实 1 显然。
故 \(\phi(n*m) \ge \phi(n) *\phi(m)\)
再证明 \(\forall\ x\in T\)，可以对应一个以上同余方程组的解，假设不对应，那么它一定与 \(n,m\) 中的一个不互质，由事实 1 推出矛盾。
故 \(\phi(n*m) \le \phi(n) *\phi(m)\)
证毕。
证明二
欧拉定理
内容
\[ \Large 若 \ \gcd(a,m)= 1 ,\ 则\ a^{\phi(m)}≡1\mod m \]
证明
考虑模 \(m\) 意义下的最小缩系，即最小完全剩余系删去与 \(m\) 不互质的元素后的剩余系，记为 \(S\)。
构造 \(T = \{ax,x \in S\}\)
可以证明 \(T=S\)， 若 \(\exist\ x_1,x_2\) 使得 \(x_1\neq x_2\) 且 \(ax_1 ≡ ax_2 \pmod m\) ，因为 \(\gcd(a,m)=1\)
所以 \(m\ |\ x_1 - x_2\)，并推出 \(x_1 \neq x_2\)，故 \(T\) 中元素两两不同且均与 \(m\) 互质，即为 \(S\)。
考虑 \(T,S\) 中所有元素的乘积，得到 \(\prod\limits_{i=1}^{\phi(n)} ax_i ≡ \prod\limits_{i=1}^{\phi(n)} x_i \pmod n\)，又因为 \(\prod\limits_{i=1}^{\phi(n)} x_i\) 与 \(m\) 互质，所以 \(a^{\phi(n)} ≡ 1\pmod n\)
扩展欧拉定理
内容
\[ \Large 若 \ b≥φ(m) ,\ 则\ a^b≡a^{b \mod φ(m) +φ(m)}\mod m \]
证明
对 \(m\) 考虑唯一分解定理。
对于任意因子 \(p_i^{k_i}\)，若与 \(a\) 互质，那就有 \(a^b≡a^{b \mod φ(m) +φ(m)}\mod p^{k_i}_i\)。
如果和 \(a\) 不互质，因为 \(b\ge \phi(m)\)，那么因为有 \(b\ge \phi(m)\ge k_i\)，所以 \(a^b,a^{(b \mod φ(m)) +φ(m)}\) 都是 \(p^{k_i}_i\) 的倍数。
得到 \(a^b - a^{(b \mod φ(m)) +φ(m)}\) 是 \(p_i^{k_i}\) 的倍数，故同余。
原根：
定义：
如果 \(x^1,x^2,x^3 \cdots x^{\phi(n)}\) 模 \(n\) 意义下互不相同，且 \(\gcd(x,n)=1\)，则称 \(x\) 为 \(n\) 的原根。
性质:
质数 \(p\) 的原根的方幂能取遍 \([1,p-1]\)
求质数的原根
数学大佬证明了一个数 \(n\) 的最小正原根不超过 \(n^{\frac{1}{4}+\epsilon}\)，所以枚举每个数，检查所有 \(n\) 的约数是否是 \(a\) 的阶，如果不是，那么 \(a\) 为一个原根，复杂度 \(\sqrt n\)，瓶颈在分解质因数。
应用
开离散对数的时候上原根和换底公式有奇效。
原根存在定理
一个数 \(x\) 有原根当且仅当 \(x= 2,4,p^n,2\times p^n\)，其中 \(p\) 为奇素数。
证明不会。
中国剩余定理
咕咕咕
平面图欧拉定理
顶点数-边数-连通块数+区域数=1
几何体欧拉定理
顶点数-边数+面数=2
除法下取整相关：
- \(\lfloor\frac{a}{b}\rfloor\ge x\iff b\le
\lfloor\frac{a}{x}\rfloor\)
- 含义：\(b=\lfloor\frac{a}{x}\rfloor\) 是满足 \(\lfloor\frac{a}{b}\rfloor\ge x\) 的最大的 \(b\)。
- \(\lfloor\frac{a}{b}\rfloor< x \iff
b>\lfloor\frac{a}{x}\rfloor\)
- 上面那个反过来。
- \(\big\lfloor\dfrac{\lfloor\frac{n}{a}\rfloor}{b}\big\rfloor=\lfloor\dfrac{n}{ab}\rfloor\)
- 设 \(n=kab+r,r< ab\)，则 \(\lfloor\frac{n}{a}\rfloor<(k+1)b\)，自然有 \(\big\lfloor\dfrac{\lfloor\frac{n}{a}\rfloor}{b}\big\rfloor\le \lfloor\dfrac{n}{ab}\rfloor\)。又因为 \(\lfloor\frac{n}{a}\rfloor\ge kb\)，因此 \(\big\lfloor\dfrac{\lfloor\frac{n}{a}\rfloor}{b}\big\rfloor\ge \lfloor\dfrac{n}{ab}\rfloor\)，得证。
余数相关
- 若 \(\gcd(x,y)=1,k\in[0,y)\)，则
\(kx\pmod y\) 互不相同。
- 证明反证法，移到同一边然后是倍数。
解析几何相关
- \((x_0,y_0)\) 关于 \(y=x+m\) 的对称点：\((y_0 - m,x_0 + m)\)。
- \((x_0,y_0)\) 关于 \(y=-x+m\) 的对称点：\((- y_0 + m,- x_0 + m)\)。
数学算法汇总
数学算法介绍
主要介绍一些数学相关的算法。
多项式
- DFT:离散傅里叶变换，方式有两种， FFT 和 NTT。
- IDFT:逆离散傅里叶变换。
FFT 多项式乘法
最开始学这玩意的时候感觉非常迷，后面数学水平上去了其实也不难。
多项式有两种表示方法，一种是系数法，另一种是点值法，总所周知 \(n\) 个不同点唯一确定一个 \(n-1\) 次多项式。
原理：多项式的两个系数表达式相乘是 \(O(n^2)\) 的，但是其点值表达式相乘却是 \(O(n)\) 的，所以考虑将系数表达式转成点值表达式然后相乘。
事实上，点值表达式和系数表达式的互相转化，如果点值取特殊点，可以做到 \(O(n\log n)\)，即使是任意点，即多项式多点求值和多项式多点插值也可以做到 \(O(n \log^2n)\)
设最终多项式次数为 \(n-1\)，我们进行多项式乘法时选择的点值叫单位根，即 \(x^n=1\) 在复数域上的所有根。
这玩意有一些性质，不过我们得先把次数变为 \(n=2^k\) 形式。
无法想象发明这个东西的人是怎么想到的，可能这就是被记在历史书上的人的水平。
以下内容如果将坐标系视为极坐标系会更好理解 $$ \[\begin{align} W_n^i &= -W_n^{i+\frac{n}{2}}\\ W_{\frac{n}{2}}^{i} &= W_{n}^{2i}\\ \end{align}\] $$ 考虑这样一个问题，对于一个多项式 \(a_0+a_1x+a_2x^2 \cdots a_{n-1}x^{n-1}\) ，我们需要同时求出它在 \(W_n^{0},W_n^{1}\cdots W_n^{n-1}\) 处的取值。发现由于第一个性质，貌似可以偷个懒，因为后 \(\frac{n}{2}\) 个 \(W_i\) 就是前 \(\frac{n}{2}\) 个数的相反数。
相反数的性质，奇数次幂的符号要改变。考虑对系数按奇偶性分类，式子变成了这个样子。
\((a_0+a_2x^2+\cdots +a_{n-2}x^{n-2})+x(a_1+a_3x^2+\cdots + a_{n-1}x^{n-2})\)
然后考虑前后两个部分，都是一个多项式，需要对他们各自求 \(x=W_\frac{2}{n}^0,W_\frac{2}{n}^1\cdots W_\frac{2}{n}^{\frac{n}{2}-1}\) 处的取值，本质上是求 \(x^2=W_{\frac{2}{n}}^0,W_{\frac{2}{n}}^2\cdots W_{\frac{2}{n}}^{n-2}\) 处的取值，结合第二个性质，woc，就是两个子问题，解决之后就可以 \(O(n)\) 得到原问题的解，边界显然是 \(n=1\)。
复杂度 \(T(n)=2T(\frac{n}{2}) + O(n) = O(n\log n)\)
1 | void FFT(int now,com *a,int op) |
但是如果递归的话，常数会比较拉跨。因为递归必然需要复制数组重新弄成一个下标 \(1-n\) 的问题，无论用什么办法解决，你的高速缓存都会表示意见很大，所以考虑迭代写法。
本质上递归是一层一层合并了两个数组，那么能不能直接模拟这个合并的过程呢，答案是可以的。
观察发现本质上是将下标二进制 reverse
之后逐层合并的，我们也这么做就行。
求 reverse 可以 \(O(n)\)，如下（如果你不了解运算顺序，请老老实实打括号）
这个原理很简单，不看最后一位，其它位先
reverse，然后处理一下最后一位就行。
1 | for(int i=1;i<1<<lim;i++)res[i]=res[i>>1]>>1|(i&1)<<1-lim; |
下面是迭代写法代码，本质是模拟了递归合并的过程。
1 | void FFT(com a[],com b[],int op) |
搞完了系数转点值，接下来是点值转系数。
前人告诉我们只需要将单位根改为 \(W_n^{0},W_n^{-1}\cdots W_n^{-n+1}\)，再做一遍系数转点值的过程就可以得到系数，但是系数会变成原来的 \(n\) 倍，除掉就行。
给出简要证明，\(i\) 次项的系数为 \(a_i\)，转一次点值
之后变为 \(b_i\)，再做一次变成 \(c_i\) \[ \begin{eqnarray} c_x &=& \sum\limits_{i=0}^{n-1}b_iW_n^{-ix} \\ &=& \sum\limits_{i=0}^{n-1} W_n^{-ix}\sum\limits_{j=0}^{n-1}a_jW_n^{ij}\\ &=& \sum\limits_{i=0}^{n-1} \sum\limits_{j=0}^{n-1}a_jW_n^{i(j-x)}\\ \end{eqnarray} \] 对于 \(j=x\)，贡献显然为 \(\sum\limits_{i=0}^{n-1}a_xW_n^{i\times0} = na_x\)
对于 \(j\neq x\) 贡献为 \(a_j \sum\limits_{i=0}^{n-1}(W_n^{j-x})^{i}\)
对这个式子的求和用等比数列求和公式有贡献为 \(\dfrac{W_n^{n(j-x)}-1}{W_n^{j-x}-1}\)
显然分子为 \(0\)，分母不为 \(0\)，所以贡献是 \(0\)，所以结果就是 \(na_x\)
搞定。
NTT 多项式乘法
FFT 多项式乘法是由缺陷的，由于浮点数精度和运算速度问题，FFT 可能并不能很好的解决一些问题，所以引入了 NTT，NTT 从有限整数域中找到了这样一组具有同样优秀性质的 \(W_n\)，即 \(g\)，也就是原根。
原根的内容可以参考数学证明总结中的介绍。
注意，和 FFT 一样，NTT 也需要严格的按照 \(2^k\) 取次数，因为我们利用了 \(W_n^{2i} = W_{\frac{n}{2}}^{i}\) 这一重要性质
所以能取出较大的 \(2^k\) 作为阶的质数才可以作为 NTT 的模数，常见的 NTT 模数是 \(998244353=2^{23}\times 7\times 17 +1\) ，我们可以取它的原根 \(g=3\) 作为基本单位根带入，实际上如果要找到一个应用于 \(n\) 的单位根 \(W_n\)，需要取 \(W_n=g^{\frac{p-1}{n}}\)。这样它就满足了我们在 FFT 证明中用到的一切性质。
然后照着 FFT 打一遍就行，只是基本运算这些换为模 \(p\) 意义下的运算就行。
1 | void NTT(int *a,int type) |
其它多项式乘法和一些优化
FFT 三次变两次
FFT 三次变两次，把 \(b\) 扔到 \(a\) 的虚部去，变成了 \(A(x) = (a_0+b_0i) + (a_1+b_1i)x+ \cdots + (a_{n-1}+b_{n-1}i)x^{n-1}\)
然后求 \(A^2(x)\)，得到的系数表达式的虚部就是 \(2ab\)。
证明显然，会比 NTT 略快。
任意模数 NTT
NTT 解决的是模意义下的乘法问题，当然，如果确保值域不超出模数，那么模意义下的结果就是正确结果。
如果模数不是 NTT 模数，就需要写任意模数 NTT。
实现方式有两种，其一是拆系数 FFT，其二是多模数 NTT 后用 CRT 合并。
多模数 NTT
一般选取 998244353 1004535809 469726049 作为 NTT
模数，它们的原根都是 3。分别进行 NTT
后，可以得到在模它们意义下的结果，用中国剩余定理合并，得到一个模约 \(5\times 10^{26}\)
的数的结果，一般来说任意的模数不会超过 \(10^9\)，所以乘起来的结果不超过 \(10^{24}\)，直接用合并的结果就行。
提一下实现细节。
一种方式是写个 Num 类，里面放三个 int，重写一下加减乘除，正常做。
另一种方式是写个 Poly 类，封装个乘法，用 for 做三次，都比较阳间。
用 CRT 时记得 __int128。或者用一个科技
一共三个方程，考虑这样合并。
其中 \(mod_1^{-1}\) 表示 \(mod_1\) 在 \(mod_2\) 意义下的逆元。 \[ x = x_1 \pmod {mod1} \\ x = x_2 \pmod {mod2} \\ k_1 mod_1 + x_1 = x_2 \pmod{mod2}\\ x = (x_2-x_1)mod_1^{-1}mod_1 + x_1 \pmod {mod_2*mod_1} \]
发现这样第二次合并的时候可以直接在模需要的模数 \(p\) 下进行计算。
注意，务必考虑好取模的顺序，计算第二个时不能先对 p 取模，因为可能结果还需要先模上 \(mod_1*mod_2*mod_3\)，
怎样避免 __int128 ?
把 \((x_2-x_1)mod_1^{-1}\) 对 \(mod_2\) 取模即可，注意处理正负号，保证任意时刻结果在 [0,对应模数) 内。
拆系数 FFT
FFT 精度不高，一般来说 double 跑个 \(10^{14}\) 问题不大（最后除掉 \(n\) 以后的结果，也就是乘出来的多项式的系数，举个例子就是如果跑 \(n=10^4\)，那需要保证 \(a_i,b_i\leq 10^5\)），但是跑 \(10^{24}\) 次方， FFT 表示我做不到，用 long double 也不行。
所以考虑拆系数，把每个数写成 \(a_1\times2^{15} + a_2\) 的形式。
然后乘法就变成了 \(a_1b_1*2^{30}+(a_1b_2+a_2b_1)*2^{15}+a_2b_2\)。
设新的四个多项式为 \(A_1,A_2,B_1,B_2\)
一共 8 次 FFT，但可以优化，考虑复多项式 \[ P=B_1+B_2i\\ T_1=P\times A_1 \\ T_2=P\times A_2 \]
发现需要的系数在 \(T_1,T_2\) 的实部和虚部，对这俩做 IDFT，收工。
一共 5 次 DFT。
也可以这样:
先考虑 \[ P=A_1+A_2i\\ P'=A_1-A_2i\\ Q=B_1+B_2i \]
再考虑： \[ T_1=PQ=(A_1B_1-A_2B_2)+(A_1B_2+A_2B_1)i\\ T_2=P'Q=(A_1B_1+A_2B_2)+(A_1B_2-A_2B_1)i \] 最后： \[ T_1+T_2=2(A_1B_1+A_1B_2i)\\ T_1-T_2=-2(A_2B_2-A_2B_1i) \]
弄出 \(T_1,T_2\) 的系数表示法就行。其实复系数多项式乘法和普通系数多项式乘法没有什么区别。
这种 5 次的思路还有其它方式，不一一介绍了。
听说有种方法可以把两次实数域多项式的 DFT 和 IDFT 整成一次复数域的，但我觉得没啥必要会。
DFT 思路是构造一个多项式 \(P=A+Bi\)，对其做 DFT，然后线性求 \(Q=A-Bi\) 的 DFT 结果。
IDFT 思路不会。
更推荐第一种写法，不会出现精度问题，如果效率不够再考虑改成第二种
深入理解计算机系统学习笔记
C 语言编译过程
- 源文本-------预处理，处理 define,include 等
- 预处理文本--------编译
- 汇编文本----------汇编得到二进制文件 .o
- 目标格式----------链接
- 可执行文件
二进制补码原理和 C 语言处理类型转换
- 二进制补码最高位本质是一个 \(-2^x\)
- 同时处理有符号和无符号整数比较时或者进行其它二元运算时，C 语言会默认无符号且均为正数。
- 编译器处理一个
-x的表达式时，会先读x然后取反，所以-2147483648是不合法的，应该写为-2147483647-1
简单的汇编语言
操作系统将物理内存抽象为了一个一维数组，所有汇编层面的操作均在一维数组内进行
每一条汇编指令都可以被描述为两个部分，指令和操作对象，这两部分的整体可以被一个或多个字节描述，此规则本质上是一颗哈夫曼树。
一个程序的汇编指令会被保存在主存上，有一个程序计数器
epi指出当前执行到的地方。常用寄存器名有
eax,ecx,edx,ebx,esi,edi,esp,ebp。前三者的数据由当前程序保存在栈中，后三者的值由下级程序保存，最后二者为帧指针和栈指针，一般不使用。前四个寄存器可以通过ah,al,ax等形式访问低二字节和低一字，但都可以用di形式访问低一字。传送指令分为三种
movb movw movl分别表示字节，字和双字。传送对应类型时，应该使用对应的寄存器位置。push,pop指令为压栈和弹栈，本质上是操作了主存和栈指针。lea指令可以快速计算a+b*(1,2,4,8)+c，a必须为常量，b,c必须为寄存器中的数。操作数分为三类，一类是立即数，一类是寄存器，一类是主存数据，访问格式如下。
1
2
3
4
5
6
7
8
9
10$imm //立即数 imm
eg. $0x3f
E //寄存器 E
eg. eax
Imm(e1,e2,s) //主存上 Imm+e1+e2*s 位置上的数据，Imm 可以缺省，后二者可以缺省，e1 缺省时不能省略 ','
eg. 0x3f(eax,ebx,4)
eg. (eax)用
test和cmp指令来控指条件，本质上，它们改变了条件寄存器内的值，test x x等价于cmp 0 x。执行cmp后，jl等条件跳转语句会在cmp成立时执行，jl表示小于时跳转，cmp x y可以看作是y<x时执行jlcall指令会将返回地址 (call) 语句后那条语句的地址入栈后跳转到函数所在位置。ret指令利用返回地址跳转回去，一般来说，用eax保存返回内容。由于程序寄存器中的某些值会被缓存到主存中，所以使用
gets等不安全函数读取时，如果读取的内容过长超出了为此缓存区分别的字节后，会污染一些先前被存储在主存中的寄存器值，因为超出分配的内存后，会写在外面，通过这样的操作，我们可以改变一些系统寄存器的值，让程序跳转执行一些我们希望让它执行的代码（这样的代码通常被写在我们的输入里），这就是缓冲区攻击，通常操作是改变ebp的值使得ret操作跳到我们希望的地方。
语法，语法糖，标准库函数
语法，语法糖，标准库函数
介绍一些有用常用但鲜为人知的 C++ 语法，语法糖。
运算顺序
记好表，记不住打括号，最好打括号。
| 运算符说明 | 运算符 | 替代方法 |
|---|---|---|
| 第 1 组优先级，无关联性 | ||
| 范围解析 | :: |
|
| 第 2 组优先级，从左到右关联 | ||
| 成员选择（对象或指针） | 或 -> |
|
| 数组下标 | [] |
|
| 函数调用 | () |
|
| 后缀递增 | ++ |
|
| 后缀递减 | -- |
|
| 类型名称 | typeid |
|
| 常量类型转换 | const_cast |
|
| 动态类型转换 | dynamic_cast |
|
| 重新解释的类型转换 | reinterpret_cast |
|
| 静态类型转换 | static_cast |
|
| 第 3 组优先级，从右到左关联 | ||
| 对象或类型的大小 | sizeof |
|
| 前缀递增 | ++ |
|
| 前缀递减 | -- |
|
| 二进制反码 | ~ |
compl |
| 逻辑“非” | ! |
not |
| 一元求反 | - |
|
| 一元加 | + |
|
| Address-of | & |
|
| 间接寻址 | * |
|
| 创建对象 | new |
|
| 销毁对象 | delete |
|
| 强制转换 | () |
|
| 第 4 组优先级，从左到右关联 | ||
| 指向成员的指针（对象或指针） | 或 ->* |
|
| 第 5 组优先级，从左到右关联 | ||
| 乘法 | * |
|
| 除法 | / |
|
| 取模 | % |
|
| 第 6 组优先级，从左到右关联 | ||
| 加法 | + |
|
| 减法 | - |
|
| 第 7 组优先级，从左到右关联 | ||
| 左移 | << |
|
| 右移 | >> |
|
| 第 8 组优先级，从左到右关联 | ||
| 小于 | < |
|
| 大于 | > |
|
| 小于或等于 | <= |
|
| 大于或等于 | >= |
|
| 第 9 组优先级，从左到右关联 | ||
| 等式 | == |
|
| 不相等 | != |
not_eq |
| 第 10 组优先级，从左到右关联 | ||
| 位与 | & |
bitand |
| 第 11 组优先级，从左到右关联 | ||
| 位异或 | ^ |
xor |
| 第 12 组优先级，从左到右关联 | ||
| 位或 | | |
bitor |
| 第 13 组优先级，从左到右关联 | ||
| 逻辑与 | && |
and |
| 第 14 组优先级，从左到右关联 | ||
| 逻辑或 | || |
or |
| 第 15 组优先级，从右到左关联 | ||
| 条件逻辑 | ? : |
|
| 转让 | = |
|
| 乘法赋值 | *= |
|
| 除法赋值 | /= |
|
| 取模赋值 | %= |
|
| 加法赋值 | += |
|
| 减法赋值 | -= |
|
| 左移赋值 | <<= |
|
| 右移赋值 | >>= |
|
| 按位“与”赋值 | &= |
and_eq |
| 按位“与或”赋值 | |= |
or_eq |
| 按位“异或”赋值 | ^= |
xor_eq |
| 引发表达式 | throw |
|
| 第 16 组优先级，从左到右关联 | ||
| 逗号 |
标准库
函数
std::swap
对于除了
array容器之外的所有标准库容器，都可以 \(O(1)\) 交换交换数组的复杂度为 \(O(size)\)，对二维数组的某一维使用，会将当前行视为一维数组进行交换。
memcpy
memcpy(dst, src, size)
dst:目标数组起始位置
src:源数组起始位置
size:需要复制的字节数
lower_bound,upper_bound
看下实现吧：
upper_bound如果对类使用，那么类的比较函数需要定义为友元函数。lower_bound返回第一个大于等于它的位置，upper_bound返回第一个大于它的位置，comp为默认小于号。- 如果要对不增序列操作，那么
comp为大于号，lower_bound返回第一个小于等于它的位置，upper_bound返回第一个小于它的位置。
1 | template<class ForwardIt, class T, class Compare> |
atan2
1 | double atan2(double x,double y){ |
for_each(begin,end,fun)
对 begin 到 end 区间的每一个元素 x，执行 fun(x)。
如果需要传参，可以利用类的构造函数。
即给类重载一个 () 运算，然后构造输出。
accumulate(begin,end,start)
对 begin end 区间运用 + 操作，起始为
start。
效率不开 \(O2\) 时略高于循环，开了没差别。
count(begin,end,val)
返回 begin end 中 ==val 的数的个数。
开了 \(O2\) 效率和循环没差别。
结构体
一般来说 class 和 struct
竞赛上差别不大，struct 是默认 public 的
class。
重载括号
重载小括号运算符可以让你把结构体当函数用，其实本质上少写了一个
.{function name}。
它和构造函数不冲突。
1 | struct barrett1{ |
两者没有本质区别。
中括号可以重载，一般来说，重载中括号返回的是一个引用，中扩号只接受一个参数。
1 | struct array_2d{ |
构造
结构体的构造函数可以返回一个结构体实例，也可以允许在声明结构体的时候同时构造。
举个例子
1 | struct st{ |
这两种写法都行，注意不能变量重名，不会
CE，但是函数参数里会那个名字会覆盖掉全局的。
注意写了构造函数，所有的构造都必须带参数。
定义结构体的时候还可以给变量赋初值。
1 | struct st{ |
但是如果构造函数里写了，就会被覆盖。声明的局部变量写了的初值会固定，没写的初值就随机。
如果没写构造函数，那么会有一个默认的列表构造函数，按照结构体内声明变量的顺序将列表中的每一个值依次赋给对应变量。
1 | struct st{ |
其实构造函数还有另一种写法
1 | struct st{ |
和最开始的写法是等效的。
注意，如果写了构造函数，默认的列表构造函数会调用它，所以如果你想不同参数个数构造，需要填默认参数
1 | struct st{ |
列表构造式还可以自推导。
1 | struct st{ |
语法概念
运算优先级
容易出问题的是几个位运算。
永远记住，位运算除了左右移位外，优先级低于比较操作。
比较操作之间，等于和不等的优先级低于大于小于。
引用
引用可以认为是一个隐式指针，不需要 *
的修饰便可以直接访问内容。它既然是一个指针，自然会占用一个
long 的空间。
定义，返回一个引用
可以在函数中返回一个引用，只需要在函数名前面后加一个
&，定义引用也在变量名加一个
&，和指针类似。
1 | double &setValues(int i) { |
定义引用的示例：
1 | int n=0,m=0; |
在重载结构体 +=,= 运算符号的时候比较常用。
引用传参应该已经很熟悉了吧。
左值引用和右值引用
C++11 新概念。参考阅读
一般的，使用引用传参时，如果接受的参数为右值，那么不能修改右值，参数必须声明为
const 类型。
算了，先咕咕咕了吧。
模板
如果用的不好，容易出现找不到实现的问题。
一个原则：所有东西的类型必须在使用前就得知。
类模板
继承的时候需要写明父类的类型参数，如果子类也是模板类，可以用子类的类型模板参数作为父类的类型模板参数。
函数模板
函数模板是可以自动推导类型的，如果出现类型冲突，那么会报
CE。
常见例子是 std::max(1,1ll) 报错。
注意字面量的类型。
指定模板参数可以仅指定一段前缀，剩下的采用自动推导。
多文件的一些问题
按惯例编写的问题
通常情况下，你会在 .h 文件中声明函数和类，而将它们的定义放置在一个单独的 .cpp 文件中。但是在使用模板时，这种习惯性做法将变得不再有用，因为当实例化一个模板时，编译器必须看到模板确切的定义，而不仅仅是它的声明。
定义和声明一起写
可以将模板的声明和定义都放置在同一个 .h 文件中。这就是为什么所有的 STL 头文件都包含模板定义的原因。
习惯来说，一般把这种包含定义的头文件后缀名写为
.hpp。
使用 export
咕咕咕
Static 关键字
声明一个静态的东西，可以用来避免命名冲突，也可以用来更好的实现一个类。
Static 关键字声明的东西生命周期是整个程序的生命周期，但作用域仅限定为声明处的作用域。
举个例子，某个函数的执行过程和它被调用的次数有关，这个可以弄个全局变量记一个次数，但是我们也可以在它的内部写个 static 变量记录，这样就不会与外部空间变量名冲突。
所有静态变量的初始值为 0
1 | int cnt=0; |
也可以用静态成员来维护一个类，比如写链表的时候，我们通常要先写个 node 类，然后才能实现 list 类，但我们可以直接将 head 指针作为一个静态变量放入结构体中，这样，这个静态变量就可以被所有结构体的实例访问修改。
注意，如果需要两个链表，那种这种方式是不可取的，因为静态变量 head 对所有该结构体的实例来说都只有一个。
我们当然也可以声明静态成员函数。
对于结构体的静态资源，我们可以用 {结构体名}.{成员名} 来访问。
函数，匿名函数
C++ 的函数名，本质上是一个指向某个函数的指针，函数在二进制层面和数据没有差异。
functor (一般译为算子)，也可以调用，但它是一个对象。
函数类
C++ 的函数可以当作一个对象处理的，函数名是指向该对象的指针，比如说：
1 | void add(int &x){x++;} |
匿名函数
格式：["捕获列表"]("参数列表")->"返回类型"{"函数体"}
捕获列表指的捕获局部变量，在函数中可以使用和修改。
参数列表无参数时可以省略，返回值如果不指定则会自动推导。
捕获列表不可省略，[] 为强制不捕获，[&] 为引用捕获全部，[=] 为取值捕获全部，也可以用变量名 [x,&y] 取值捕获 x，引用捕获 y。
1 | sort(v.begin(),v.end(),[](const int &x,const int &y){return x>y;}); //降序排序 |
匿名函数也可以作为一个对象处理。
虚函数
这个东西自己写的时候用的比较少，毕竟不太注重面向对象，
这玩意和 Python 的 abstract_method
类似，我也不知道怎么解释，反正会用就够了。
竞赛中应用的话，可以用来重写 pd_ds
里面的平衡树，但是真的用的很少。
语法糖
函数相关
返回值为 void 的函数
你是否碰到过这样的情况，函数返回值为
void，但是返回又是有条件，并且还需要执行一些简单的操作，用
{} 括起来显得代码冗长，不妨试试：
1 | void do_cool_thing(int arg){ |
有返回值的函数
, 可以用在 return
语句，会返回最后一个值，当然也可以用在其它 Case。
1 | int get_v(){ |
列表初始化器
这东西说白了就是 {1,2,3,4,5}
这种，注意区分类成员初始化器，后者可以多类型，前者只能单类型。
循环
1 | for(int v:{0,1}){ |
分支更少，效率更高，代码更优美！
一些有点容易忘的基础算法
树链剖分
常用的树链剖分有重链剖分，实链剖分和长链剖分。
长链剖分主要用于部分和深度有关的树形 \(dp\) 的优化，一般采用指针数组实现。
我们说的树链剖分一般指重链剖分，即选择每个点子树最大的儿子。
不难证明从任何一个点到根都只会经过 \(log_n\) 条重链，这也是其复杂度的保证。
可以将每条重链用一个数据结构维护起来，就能做树上操作了。
动态树
动态树是基于实链剖分的数据结构，非常强大，但编码复杂度相对较高。
我使用的是基于 \(splay\) 的动态树。
动态树维护的是若干实链，每个实链用一颗平衡树维护。
动态树的核心操作是 access，意味将目标点 \(x\)
到根的路径全部打通，并且只包含这条路径。
其它操作简要介绍一下实现：
make_root :先 access，然后把 \(x\) splay 到根，然后翻转整颗
\(splay\) ，因为 \(splay\) 外的形态没有改变，所以只要 \(splay\)
内部的形态正确，那么整棵树的形态就正确，如果对于一个 \(splay\)
所有的节点交换了左右儿子，那么就是倒序了这颗 \(splay\) ，\(x\)
又是深度最大的点，所以这样是正确的。
link :很简单，直接将目标点 \(x\) splay
到当前根，当然，注意到原树之间的关系是 \(splay\) 根节点的关系，\(splay\) 根节点的父亲其实是 \(splay\)
中深度最小的点的父亲，然后改父亲改成 \(y\) 就行。
cut :假设有一个虚根 \(0\)，把 \(x\) make_root ，把 \(y\) access 然后
splay \(y\),直接双向断开。
1 | void push_up(int rt){} |
虚树：
一般用来处理询问很多但规模不大的树上问题。
点分治
用来处理树上路径的计数问题，特别是路径长度相关
后缀排序
对一个字符串的所有后缀排序，约定 \(sa[i]\) 表示排名为 \(i\) 的后缀的起始位置，约定 \(rk[i]\) 表示起始位置为 \(i\) 的后缀的排名。\(height[i]\) 为排名为 \(i,i-1\) 的后缀的 \(lcp\) 。
先按第一个字母基数排序一遍，然后倍增法。
1 | for(i=1;i<=n;i++)sum[rk[i]=ch[i]]++; |
莫队
莫队是暴力数据结构，将询问离线后，以较低的复杂度移动左右端点，然后处理询问。
设移动端点的复杂度为 \(O(x)\) ，那么莫队复杂度为 \(O(n \sqrt n\times x)\)，无法将 \(x\) 放在 \(\sqrt n\) 下面。
常见的卡常技巧有奇偶性排序等。
如果只能支持插入和删除中的一种操作，那么可以使用回滚莫队，拿一个栈记录操作，基于操作的撤销实现插入或删除。
树上莫队和普通莫队区别不大。
(差一个二次离线要补)
拓展KMP
咕咕咕
树哈希
一般来讲，可以这么哈希，再加上树大小的判断，就不会出问题。 \[ f_{now}=1+\sum f_{son(now,i)} \times prime(size_{son(now,i)}) \]
但这个哈希是有错的，可以对最小括号序列哈希。
具体的，一颗无标号有根树按照遍历顺序可以得到一个括号序列，即将子树的括号序列拼起来再套一个括号。
然后考虑对这个括号序列哈希，因为遍历顺序无关，所以要最小括号序列。
实际上可以直接对子树哈希值排序之后，按这个顺序往后写，外面添一层括号，对括号序列（二进制串）哈希。
从一道题看CPU底层优化-第一弹
关于某道题的优化
题意
给定一个长度为 \(n\) 的序列 \(a_i\)，求有多少个区间满足每个数出现次数均为偶数。
\(n\leq 3\times 10^4,a_i\leq 10^6\)
思路
双指针扫描每个区间，拿个桶，\(O(1)\) 更新状态，然后 \(O(n^2)\)，可以得到 \(40\) 的好成绩。
代码一
1 | #include<bits/stdc++.h> |
优化
1.高速缓存原理
计算机有个东西叫高速缓存，可以优化内存访问延迟。
一次独立的内存操作会读取一个 \(64Byte\) 的 \(cacheline\)，从指令发出到从内存收到数据需要约 \(200\) 个 \(CPU\) 周期，而 \(CPU\) 会将一些常用的数据塞进 \(cache\)，也就是高速缓存中，加速读取，寄存器的访问速度是最快的，只需要不到 \(1\) 个时间周期，\(L1\) 缓存需要约 \(3\) 个时间周期，\(L2\) 为 \(10\) 个左右，\(L3\) 为 \(20\) 个周期。
具体时间视计算机本身有差别，但基本的比例是这个。
代码一中，我们只关注瓶颈。
1 | now+=-1+((cnt[a[j]]&1)<<1); |
其中，对于 cnt 的访问和对于 a
的访问，由于高速缓存并不大，所以塞不下
cnt，因此我们每个循环都需要等一个 200
时间周期的延迟，这是相当致命的，实际上等待的延迟并没有 200
时间周期，因为 \(CPU\)
将部分数据还是放进来 cache，但具体放哪些是由
CPU 决定的。
对于这个致命的延迟，我们可以将数据离散化，然后就可以得到一个
75pts 的代码。
1 | #include<bits/stdc++.h> |
2.流水线模式和延迟隐藏
现代计算机各类硬件的设计都采用了流水线模式，将每条汇编指令的执行都划分为了不同的流水线。
也就是说 CPU 可以不间断的向内存发出访问指令，这些指令经过一定延迟后，内存会不间断的向CPU传数据，这个过程中，我们就只等待了一个内存延迟。打个比方，这玩意就像烧水，水壶很多，灌水和倒水的时间都很短，所以正确的方式是全部烧上等，而不是烧一个等一个。
所以，如果我们能够连续的发出内存访问指令，那么内存延迟可以被有效隐藏，但注意到代码中，访问了内存后执行了一些计算，而内存访问是依赖于这些计算的，这产生了一个依赖，我们必须等待计算完成之后才能进行访问，所以无法有效的隐藏延迟。
向内存写入数据也是需要等待延迟的。
3.流水线和依赖分析
上一部分简单介绍了流水线模式，在我们的 \(CPU\) 中，也采用流水线的设计。
一条汇编指令的执行在 \(CPU\) 上大致分为五个部分，分别是：取指，访(寄)存，计算，内存操作，写回。
\(CPU\) 在这五个部分的设计上也采用了流水线，一条指令开始访存时，另一条指令的取指就开始了。
而如果下一条指令对前一条指令有数据依赖，那么 \(CPU\) 会通过转发操作消除这种依赖，但如果下一条指令的内容对上一条指令有依赖（比如说 if），那么 \(CPU\) 就不得不停止流水线，向流水线中插入气泡以等待。
这会极大降低 \(CPU\) 的利用率，因此，内循环中的 \(if\) 是相当不应该的。
4.流水线和分支预测
事实上，硬件的设计者注意到了这种依赖，而 \(CPU\) 会对这种依赖做出预测，预测基于程序计数器的的原理和一些其它统计数据，正确率约在 \(65\%\) 左右，如果分支预测出现错误，那么会花费两个时间周期去消除这个错误，所以我们需要通过算术方式避免分支。
方式如下：
1 | #include<bits/stdc++.h> |
目前是最快代码。