素数与同余
素数个数定理
-
记 \(\leqslant x\) 的素数个数为 \(\pi(x)\)，则有 \(\pi(x)\sim\dfrac{x}{\ln x}\)。
-
不会证。微积分？
Miller-Rabin 强伪素性检测算法
-
简称为 Miller-Rabin 测素。
-
顾名思义，它是一种高效地检测一个数是否有足够强的素性，或者说，是否足够像一个素数/足够可能是一个素数的算法。
-
它不能真正证明一个数是素数（但可以证伪）。
-
实现略，后面再补。
数列
Fibonacci 数列
\[\gcd(F_n,F_m)=F_{\gcd(n,m)} \]-
证明如下：
-
定理 \(1\)：\(\gcd(F_n,F_{n+1})=\gcd(F_n,F_{n+2})=1\)。
-
\(\gcd(F_n,F_{n+1})=\gcd(F_n,F_{n+1}-F_n)=\gcd(F_n,F_{n-1})\)，显然可以利用更相减损法无穷递降到 \(\gcd(F_1,F_2)=1\)。
-
\(\gcd(F_n,F_{n+2})\) 显然可以更相减损一次化归到上面这种形式。
-
-
定理 \(2\)：\(F_{m+n}=F_{m+1}F_n+F_mF_{n-1}\)。
-
首先这里 \(m,n\) 是平等的（可以互换位置）。故我们归纳证明的时候实际上只用证一个。
-
考虑归纳证明这个东西。不妨令 \(F_0=0\)，则当 \(n=m=1\)，\(F_{1+1}=F_2F_1+F_1F_0\)，显然成立。
-
然后不妨假设结论对 \(n,m\leqslant k\) 成立，试证明对 \(n=k+1\) 成立：
-
\(F_{m+n}=F_{m+k+1}=F_{m+k}+F_{m+k-1}=F_{m+1}F_k+F_mF_{k-1}+F_{m+1}F_{k-1}+F_mF_{k-2}\)
-
合并同类项，有 \(F_{m+n}=F_{m+1}F_{k+1}+F_mF_k=F_{m+1}F_n+F_mF_{n-1}\)。证毕。
-
为了直观的话，我们顺带把对 \(n,m\leqslant k\) 成立的 \(m=k+1\) 证一下：
-
\(F_{m+n}=F_{k+1+n}=F_{k+n}+F_{k-1+n}=F_{k+1}F_n+F_kF_{n-1}+F_kF_n+F_{k-1}F_{n-1}\)。这里的拆法稍有不同。
-
化一下，\(F_{m+n}=F_{k+2}F_n+F_{k+1}F_{n-1}=F_{m+1}F_n+F_mF_{n-1}\)。看到本质是对称证明。
-
-
定理 \(3\)：\(\gcd(F_m,F_n)=F_{\gcd(m,n)}\)。
-
不妨令 \(m>n\)，于是有：
-
\(\gcd(F_m,F_n)=\gcd(F_{m-n+n},F_n)\)，由定理 \(2\)：
-
\(F_{(m-n)+n}=F_{m-n+1}F_n+F_{m-n}F_{n-1}\)。
-
接下来分类讨论。
-
当 \(F_{m-n}F_{n-1}\leqslant F_n\)：
-
显然此时 \(F_{m-n}<2\)（可参看博弈论-斐波那契博弈中的相关证明），即 \(m-n\leqslant 2\)。
-
由定理 \(1\)，\(\gcd(F_m,F_n)=1=F_1=F_2\)，又由 \(m-n\leqslant 2\) 知 \(\gcd(m,n)\leqslant 2\)，结论成立。
-
-
当 \(F_{m-n}F_{n-1}>F_n\)：
-
反复使用更相减损法，则 \(\gcd(F_m,F_n)=\gcd(F_{m-n}F_{n-1},F_n)\)。
-
由定理 \(1\)，\(F_{n-1}\perp F_n\)，故上式等价于 \(\gcd(F_{m-n},F_n)\)。
-
故我们相当于对求 \(\gcd\) 的两个 \(F\) 的下标在做更相减损。显然可以无穷递降得到 \(\gcd(m,n)\)，故 \(\gcd(F_m,F_n)=F_{\gcd(m,n)}\)。
-
-
调和级数
\(\sum\limits_{i=1}^n\dfrac{1}{i} \sim O(\log{n})\)
\(\sum\limits_{i=1}^n\dfrac{n}{i} \sim O(n\log{n})\)
- 其中 \(\sim\) 表示趋近于。不会证，微积分？
不等式
排序不等式
- 给定两个单调不降的数列 \(a_{1\sim n},b_{1\sim n}\)，定义其正序和、乱序和、逆序和分别为
-
总有正序和 \(\geqslant\) 乱序和 \(\geqslant\) 逆序和。
-
证明：反证法。
-
假设存在一种不同于正序的顺序可以取到最大，那么把 \(b\) 数组重新按当前序列编号，选择其中两个逆序对（\(i<j,b_i>b_j\)），交换后显然更优，与假设矛盾。
-
同理可证乱序和 \(\geqslant\) 逆序和。
-
四边形不等式
- 参见“DP 优化：决策单调性优化”。
方程式
高斯消元法
-
解多元一次方程式组。
-
实现原理：
-
枚举主元，找到一个含有该主元的方程。
-
使用加减消元法消去其他所有方程中的该主元。
-
反复直到解出。注意判同构（无解）情况。
-
double a[maxnum][maxnum];
bool same(double x,double y){return fabs(x-y)<eps?1:0;}
il void gauss(){
for(int i=1;i<=num;++i){//枚举主元
int pos=i;//pos是找的方程 a是系数，特别地,a[?][n+1] 是式右的结果
while(pos<num && same(a[pos][i],0.0)) ++pos;
if(same(a[pos][i],0.0)) continue;//寄了
else for(int j=1;j<=num+1;++j) swap(a[i][j],a[pos][j]);//把那个方程换上来
double now=a[i][i];
for(int j=1;j<=num+1;++j) a[i][j]/=now;//调一下系数，使得主元的系数是1
for(int j=1;j<=num;++j)//每一行地减过去
if(j!=i){
double now=a[j][i];//对应的该主元系数
for(int k=1;k<=num+1;++k) a[j][k]-=now*a[i][k];
}
}
}
编码
康托展开
-
康托展开用于给 \(1\sim n\) 的排列编号，排列 \(P\) 的编号就是字典序比 \(P\) 小的排列数 \(+1\)。
-
朴素的哈希方法显然是做成 \(n+1\) 进制数，但凭感觉就能知道，\(n\times (n+1)^{n-1}>>n!\)。
-
康托展开的办法则是，从排列本身的字典序出发。
-
公式不太好写，因为这个东西本质上是递推的。我们看一个例子：\([2,5,3,4,1]\)。
-
比第一位小的：\(1\times 4!\) 种。
-
第一位一样但是比第二位小：除去第一位。\(3\times 3!\) 种。
-
前两位一样但是比第三位小：\(1\times 2!\)。
-
前三位一样但是比第四位小：\(1\times 1!\)。
-
前四位都一样就确定了。
-
看到这个东西要求“还没有出现过的比我小的数量”，很树状数组。
-
故可以 \(O(n\log n)\) 地做。
-
现在我们有式子了：\(\sum\limits_{i=1}^n(a_i-1-get(a_i))\times (n-i)!\)。
-
注意这是“比我小的排列数”，排名的话，得再 \(+1\)。