矩阵

1. 对于一个有向图G，我们用G[i][j]的邻接矩阵来表示这个图，并且图上所有的距离为1,那么GT$G^T$表示经过时间T后对于任意i通过时间T到j的方案数。

(From Saramanda) 证明：设图的邻接矩阵为A。在不考虑边权（或者边权都为1）的时候，An$A^n$ 中的元素Ani,j$A^n_{i,j}$也表示i到j经过n条边（路径长度为n）的方案数。 为什么呢？我们用归纳法证明。 因为当n=1$n=1$时显然成立，然后对于任意n>1$n>1$，有An=An−1∗A$A^n=A^n−1∗A$，则对于An中每个元素，有 Ani,j=∑An−1i,k∗Ak,j $$A^n_{i,j}=/sum A^{n-1}_{i,k}∗A_{k,j}$$ 如果性质在An−1$A^{n−1}$ 中成立，那么Ani,j$A^n_{i,j}$就表示i到k经过n-1条边的方案总数×k到j经过1条边的方案总数，结果就是i到j经过n条边的方案总数，所以An$A^n$符合性质，即如果An−1$A^{n−1}$满足性质，那么An$A^n$满足性质。所以命题得到证明。

2.求对于已知矩阵A，S=∑i=1nAi $$S=/sum_{i=1}^n A^i$$ 对于S=∑i=1kAi $$S=/sum^k_{i=1}A^i$$ 令B=∑i=1k/2Ai,X=Ak/2 $$B=/sum^{k/2}_{i=1}A^i,X=A^{k/2}$$ if(!(i&1)) S=B+B∗X $$S=B+B*X$$ else S=B+B∗X+Ak $$S=B+B*X+A^{k}$$ 3.关于类似于Fi=Fi−1+i−1$F_i=F_{i-1}+i-1$的用矩阵优化的递推式。转移矩阵中可以加一个常数1来使得(i-1)增加，及对于该模板递推方程的转移矩阵为： ⎡⎣⎢⎢100110011⎤⎦⎥⎥∗⎡⎣⎢⎢Fi−1i−11⎤⎦⎥⎥=⎡⎣⎢⎢Fii1⎤⎦⎥⎥ $$/begin{bmatrix} 1 & 1 & 0// 0 & 1 & 1// 0 & 0 & 1 /end{bmatrix}* /begin{bmatrix} F_{i-1}// i-1// 1 /end{bmatrix}= /begin{bmatrix} F_{i}// i// 1 /end{bmatrix}$$

递推

1.特征方程: 对于Fi=pFi−1+qFi−2$F_i=pF_{i-1}+qF_{i-2}$ 方程x2=px+q$x^2=px+q$ 解出两根s,t 通向公式:Fi=a∗sn+b∗tn$F_i=a*s^n+b*t^n$ a,b由数列中任意两项决定 通常可以用F0和F1$F_0和F_1$ 也可以从通向公式倒退回去

数论

1. 将一个正整数N拆成若干个正整数a1$a_1$,a2$a_2$,a3$a_3$⋯$/cdots$ak$a_k$，使得这k个正整数的乘积最大。 先找到一个k，令S=∏i=2ki $$S=/<a href="http://pr.VeVb.com/">PR</a>od^k_{i=2}i$$ 使得S<=N$S<=N$并且S∗(k+1)>N$S*(k+1) > N$然后用Δ=N−S$/Delta=N-S$使得后Δ$/Delta$个数字提升1，得到的最终乘积S′=∏i=1k−Δi∗∏i=k−Δ+1ki $$S'=/prod^{k-/Delta}_{i=1}i*/prod^k_{i=k-/Delta+1}i$$ 最大。

2.对于大整数S可以拆成若干个S=a∗10+b$S=a*10+b$ S%Mod=(a∗10+b)%Mod=a∗10%Mod+b%Mod$S/%Mod=(a*10+b)/%Mod=a*10/%Mod+b/%Mod$

3.Gcd(Fn,Fm)==FGcd(n,m) $$Gcd(F_n,F_m)==F_{Gcd(n,m)}$$

4.ϵ(n)=n∗∏i=1k(pi−1)/pi $$/epsilon(n)=n∗/prod^k_{i=1}(p_i−1)/p_i$$

5.n!=∏i=1mpkii $$n! =/prod^m_{i=1}p_i^{k_i}$$ 6. ki=∑X=1!(n/pXi)n/pXi $$k_i=/sum^{!(n/p_i^X)}_{X=1}n/p_i^X$$

逆元

(部分参考ACdreamers) a,x为正整数，如果有： ax≡1(mod m)$ax/equiv 1(mod ~m)$ 那么x的最小整数解为a模m的逆元

1.求得方法： 扩展欧几里得

费马小定理(m为素数)：am−2mod m$a^{m-2}mod~m$ 证明:am−1≡1(mod m)⇒a∗am−2≡1(mod m)⇒am−2≡1a(mod m)$a^{m-1}/equiv1(mod~m)/Rightarrow a*a^{m-2}/equiv1(mod~m)/Rightarrow a^{m-2}/equiv{1/over a}(mod~m)$

2.求ans=ab mod m$ans={a/over b}~mod~m$ ans=ab mod m=a mod (mb) / b$ans={a/over b}~mod~m=a~mod~(mb)~/~b$ 证明： ab=km+x(x<m)${a/over b}=km+x(x<m)$ a=kbm+bx$a=kbm+bx$ a mod (bm)=bx$a~mod~(bm)=bx$ a mod (bm) / b=x$a~mod~(bm)~/~b=x$ ab mod m=a mod (bm)/b${a/over b}~mod~m=a~mod~(bm)/b$

3.求正整数A的因子之和 A=∏i=1kpaii $$A=/prod^k_{i=1}p_i^{a_i}$$ Sum=∏i=1k∑J=0aipJi $$Sum=/prod^k_{i=1}/sum^{a_i}_{J=0}p_i^J$$           =∏i=1kpaii−1pi−1 $$~~~~~~~~~~=/prod^k_{i=1}{p_i^{a_i}-1/over p_i-1}$$

4.逆元的线性递推 Inv[i]=(M−M/i)∗Inv[M%i]%M $$Inv[i]=(M-M/i)*Inv[M/%i]/%M$$

5.对于两个正整数m,n如果m|n$m|n$，那么1−>n$1->n$中与m互素的数的个数为nmϵ(m)${n/over m}/epsilon(m)$

6.如果Gcd(a,b)==1$Gcd(a,b)==1$那么Gcd(a+k∗b,b)==1$Gcd(a+k*b,b)==1$