Something about Maths…

终于能够填坑了。。
这里主要记录一些数论，组合函数还有一些奇奇怪怪的东西的性质之类的，方便以后运用。

数论部分

斐波那契数列

定义式：

$$fib_n = \begin{cases} 0, & n = 0 \\ 1, & n = 1 \\ fib_{n-1} + fib_{n-2}, & n > 1 \end{cases}$$

性质1：

$$fib_n = \frac {1} {\sqrt 5}[(\frac {1 + \sqrt 5} {2}) ^ n - (\frac {1 - \sqrt 5} {2}) ^ n](比内公式)$$
证明：不会证。不动点特征根？

性质2：

$$lim_{n \to \infty} \frac {fib_n}{fib_{n-1}} = \frac {\sqrt 5 - 1}{2}(黄金分割比)$$
证明：不会证。不过是个众所周知的性质。

性质3：

$$\begin{array}{lcl} fib_1+fib_3+fib_5+...+fib_{2n-1} & = & fib_{2n}-fib_2+fib_1 \\ fib_2+fib_4+fib_6+...+fib_{2n} & = & fib_{2n+1}-fib_1 \\ fib_1+fib_2+fib_3+...+fib_{n} & = & fib_{n+2}-1 \\ fib_1^2+fib_2^2+fib_3^2+...+fib_n^2 & = & fib_n \cdot fib_{n+1} \\ fib_1+2fib_2+3fib_3+...+nfib_{n} & = & nfib_{n+2}-fib_{n+3}+2 \\ fib_{n-1} \cdot fib_{n+1} - fib_n^2 & = & (-1)^n \\ \end{array}$$
证明：全部都可以归纳得到。

性质4：

$$fib_n \perp fib_{n + 1}(n \geq 1)$$
证明：可考虑采用归纳和裴蜀定理。

性质5：

$$fib_n = fib_m \cdot fib_{n-m+1} + fib_{m-1} \cdot fib_{n-m} (n \geq m \geq 1)$$
证明：可以采用归纳法并与斐波那契的递推式结合可得。

性质6：

$$gcd(fib_n, fib_m) = fib_{gcd(n, m)}$$
证明：结合性质4和5。不妨设$n>m$。
$$\begin{align} gcd(fib_n, fib_m) & = gcd(fib_m \cdot fib_{n-m+1} + fib_{m-1} \cdot fib_{n-m}, fib_m) \\ & = gcd(fib_{m-1} \cdot fib_{n-m}, fib_m) \\ & = gcd(fib_{n-m}, fib_m) \\ & = fib_{gcd(n, m)} \\ \end{align}$$

性质7：

$$fib_n = \sum_{k = 0}^{\lfloor {\frac {n-1}{2}} \rfloor} C_{n-k-1}^k$$
证明：可以通过杨辉三角得到。

性质8：
斐波那契数列在模任意$p(p>1)$意义下出现循环节，设其为$\pi(p)$。
则有：
(1).若$(n, m) = 1$，则$\pi(nm) = \pi(n) \pi(m)$；
(2).若$p$是质数，则$\pi(p^k) = p^{k-1} \pi(p)$；
(3).$\pi(2) = 3$；
(4).$\pi(5) = 20$；
(5).若$p$是模$10$得$\pm1$的质数，则$\pi(p) \leq p-1$且$\pi(p) \mid p-1$；
(6).若$p$是模$10$的$\pm3$的质数，则$\pi(p) < 2(p + 1)$；
(7).根据以上所有性质，$\forall n \in \mathbb{Z}$，$\pi(n) \leq 6n$。

证明：都不会证，要用群、环、域的知识解决，看起来很高深。
其中$\pi(n)$叫做第$n$个皮萨诺周期，图像长这样：

例题：
[hdu 6363] bookshelf

离散对数

概念:
已知$a,b,c$，要求满足$a ^ x \equiv b (mod \ c)$的最小整数解$x$。

算法：
一般采用BSGS或exBSGS算法（大步小步）。

BSGS：
当$a \bot c$时，运用meet-in-middle的思想，设$m = \lceil \sqrt c \rceil$，将$a^0, a^1, ... , a^{m-1}$扔进hash表里面。
然后设$a' = a ^ m$，从${a'} ^ 0$开始，一直到${a'} ^ {m - 1}$，在hash表里面询问$b * inv({a'}^i)$最早出现的位置$k$（可能没有出现过）。若出现过，答案就是$im+k$。
否则整个过程下来没有找到解，就是无解。
复杂度$O(\sqrt nlogn)$，求逆元的复杂度。
但是当$a$和$c$不互质怎么办？用扩展版。

exBSGS：
设$d = (a,c)$。若$d \nmid b$显然方程是无解是无解的（当然$b=1$是特殊情况）。
否则方程变成$a / d * a ^ {x - 1} \equiv b / d (mod \ c / d)$
由于有可能$a$和$c/d$仍然不互质，那么继续这个过程就好了。
由于$c$每次除掉的都是大于$1$的数，所以最多执行$logc$次。
这里复杂度是$O({logn}^2)$的。
所以总复杂度是$O(\sqrt nlogn)$的。
注意还要暴力找一下$x \leq logc$的情况（其实写起来只要加一句话就可以了）。

例题：
[bzoj 2480] Spoj3105 Mod

高次剩余

概念：
已知$k,a,p$，要求满足$x ^ k \equiv a (mod \ p)$的整数解$x$。
这里讨论二次剩余和三次剩余。($k = 2, 3$)
一般只讨论$p$为素数的情况。

算法：
一种比较优秀的算法是Cipolla算法。

二次剩余：
$x ^ 2 \equiv a (mod \ p)$
首先定义二次剩余符号（legendre符号）$(\frac {a}{p})≡a^{\frac{p−1}{2}}(modp)$，一个数$a$是模$p$的二次剩余，当且仅当$(\frac {a}{p})$ = 1。
随机一个$\omega$使得$\omega^2−a$不是二次剩余，期望次数是2。
设$t = \sqrt {\omega^2−a}$，则$(\omega + t) ^ \frac{p + 1}{2}$在域$F_{p^2}$意义下是一个解。由于$p$是奇数，所以$-t$也是一个解。
根据拉格朗日定理，一个2次多项式最多有2个根。
所以至此，算法完成。

证明：
设$F_{p^2}=F_p(\sqrt{\omega^2 - a})=\{x+yt:x, y \in F_p \}$
可以证明$F_{p^2}$也是一个域。
我们要证明$((\omega + t) ^ \frac{p + 1}{2}) ^ 2 \equiv a (mod \ p)$
左边式子展开得到：

$$\begin{align} (\omega+t)^{p+1} & = (\omega+t)^p(\omega+t)\\ & = (\omega^p+t^p)(\omega+t)（这里要类比一下一般的模p意义下二项式展开） \\ & = (\omega - t)(\omega + t) \\ &（这里要注意，\omega^p \equiv \omega是根据费马小定理，而t^p \equiv (t^{2})^{\frac {p-1}{2}}t \\ & 根据t^2=\omega^2−a是二次非剩余，(t^{2})^{\frac {p-1}{2}} = -1）\\ & = \omega^2 - t^2 \\ & = a \\ \end{align}$$
这样我们可以在$O(logp)$的复杂度求出一个方程的解。

三次剩余：
$x ^ 3 \equiv a (mod \ p)$
类似的想法。
首先三次剩余的符号$[\frac {a}{p}] \equiv a^{\frac {p-1}{3}} (mod \ p)$
根据这个定义，我们要考虑$p$的不同情况。
若$p$在模3意义下不同余于1，
$x \equiv a^{\frac {2p−1}{3}}(mod \ p)$是唯一解。
若$p$在模3意义下同余于1，
随机一个数$\omega$，使得$\omega^3-a$是三次非剩余，期望次数为9。设$t = \sqrt[3] {\omega^3-a}$。
构造域$F_{p^3} = \{a + bt + ct^2 : a, b, c \in F_p\}$
然后$x=(\omega-t)^{\frac{p^2+p+1}{3}}$就是一个解。
另外两个解是$x\epsilon, x\epsilon^2$，其中$\epsilon = [\frac{\omega^3-a}{p}]$是模$p$意义下的三次单位根。
证明也像上面一样。

例题：
[timusOJ 1132] Square Root

多项式部分

拉格朗日插值法

概念：
一般地，若已知函数$y = f(x)$在互不相同的$n+1$个点$x0,x1,...,xn$处的函数值$y0,y1,...,yn$（即该函数经过这$n+1$个点，则可以通过一种插值构造法构造出经过这$n+1$个点，次数不超过$n$的多项式，满足：

$$P_n(x_k) = y_k , k = 0, 1, ..., n$$

形式：
对于某个确定的多项式函数，在其中的$k + 1$个值已知的点取值：
$(x_0, y_0), (x_1, y_0), ... , (x_k, y_k)$（满足$x_i$互不相同）
则我们构造一个拉格朗日差值多项式：

$$L_k(x) = \sum_{i = 0}^k y_i \cdot l_i(x)$$
其中$l_i(x)$叫做拉格朗日基本多项式，也叫插值基函数，满足：
$$l_i(x) = \prod_{j = 0, j \neq i}^k \frac {x-x_j}{x_i-x_j}$$
这个多项式意义何在？
注意到当$x$取$x0,x1,...,xk$时，整个插值基函数的值是$1$；否则就是$0$。
所以这样一来，对于每一个$i$，$L_k(x_i) = \sum_{i = 0}^k y_i$。

证明：
存在性
证明该算法确实能至少对应一个符合条件的多项式。
事实上，根据上面的分析，我们已经构造出了一个多项式$L_k(x)$。容易证明它是合法的。

唯一性
证明该算法确实只能对应唯一一个符合条件的多项式。
假设对应两个k阶多项式$P(x)，Q(x)$。
根据定义，$\forall 0 \leq i \leq k，i \in \mathbb{Z}$，满足$P(x_i) - Q(x_i) = 0$
如果设$R(x) = P(x) - Q(x)$，则由可知，$R(x)$是$(x-x_0)(x-x_1)...(x-x_k)$的倍数。
则$R(x)$的阶必然大于等于$k+1$。事实上，$P$和$Q$都是$k$阶多项式，相减以后阶数不可能超过$k$阶。
所以就证明了这个多项式是唯一的。

例题：
[codeforces 622F] The Sum of the k-th Powers

线性代数部分

子空间、列空间、零空间、秩

记空间$S$的维度为$dim$，对于一个$n行m列秩为r的矩阵A$，有定理：
$dim \ C(A) = r（列空间）$
$dim \ N(A) = m-r（零空间）$
$dim \ C(A^T) = r（A的转置的列空间）$
$dim \ N(A) = n-r（A的转置零空间）$

初等应用

解线性方程组$Ax=b$。
判断无解或是有解找出解很好办。万一要在无解的情况下找出最优近似解呢？
这要涉及到拟合直线的问题与投影矩阵。

挂个链接

投影、正交、正交矩阵，Gram-Schmidt正交化

正交：空间$S$和$T$正交简单说就是$\forall \vec a \in S, \vec b \in T, \vec a \cdot \vec b = 0$。
正交矩阵：满足$P^T = P^{-1}$的矩阵。
性质：任一两行行向量或任意两列列向量都正交。
优点：可以简化投影矩阵的一些公式等等。
eg.旋转矩阵就是一个正交矩阵：

$$\begin{bmatrix} cos\theta & -sin\theta \\ sin\theta & cos\theta \end{bmatrix}$$
Gram-Schmidt正交化：
将多个线性无关的向量变成一组正交向量（基）。
思想还是用到做投影的方法。
传送门

行列式

定义：记作$det \ A或 |A|$。
定义式：

$$det \ A = \sum_{\sigma \in S_n} sgn(\sigma) \prod_{i=1}^n A_{\sigma(i),i}$$
行列式的性质有很多，最妙的是，任取其中3条当作初始公理，都能推得剩下所有的结论。
下面给出常用的三条公理：
1. $|det I| = 1$；
2. 交换两个行向量使得行列式符号取反；
3. 行列式的对于代数运算的线性性。
从这三条里面还可以有另外7个推论，具体可以看这篇博客：
biu
行列式的计算方法：
一般化情况下，可以通过高斯消元，定义式，或代数余子式来计算。

代数余子式

余子式定义：$A_{i,j}$表式将矩阵$A$的第$i$行第$j$列差掉以后剩下的部分求行列式的值。
代数余子式定义：$\forall i, j$，$(i,j)$这个位置上的代数余子式就是该位置上的余子式乘以$(-1)^{i+j}$。

定理：$\forall i, det \ A = \sum_{j = 1}^n A_{i,j}*a_{i,j}$，其中$a_{i,j}$表示该位置上的代数余子式。
这个式子叫做按行$i$展开式，同样可以按列展开。

伴随矩阵

定义矩阵$A$的伴随矩阵为$A^{*}$，其位置$(i,j)$上的元素为矩阵$A$中位置$(j,i)$上的代数余子式。
经典定理：
$AA^{*} = |A|I$

应用