MathJax Party
我是一中截图王
等差序列求和
\(\sum\limits_{i=1}^{n}{a_n}\ (a_i = a_{i-1} + d)\)
\(=n\times a_1 + \dfrac{n(n-1)}{2}\times d\)
等比数列求和
\(\sum\limits_{i=1}^{n}{a_n}\ (a_i = a_{i-1} \times d)\)
\(=\dfrac{a_1(1-d^{n})}{1-d}\)
设: \(T = \sum\limits_{i=1}^{n}{a_i}\),
有: \(aT = \sum\limits_{i=1}^{n}{a_i \times d}\)
则有: \((a-1)T = aT - T = a_{n+1} - a_1\)
等差数列求积
\(\sum\limits_{i=1}^{n}{a_n}\ (a_i = a_{i-1} + d)\), \(\sum\limits_{i=1}^{n}{b_n}\ (b_n = b_{i-1} + q)\)
求 \(\sum\limits_{i=1}^{n}{ai\times b_i}\).
设: \(T =\sum\limits_{i=1}^{n}{ai\times b_i}\).
有: \(qT = \sum\limits_{i=1}^{n}{ai\times b_i}\).
两式相减, 有:
斐波那契数列
\(f_0 = f_1 = 1,\ f_i = f_{i-1}+f_{i-2}\).
凑一个等比数列形式:
\(f_i - yf_{i-1} = x\times (f_{i-1} - yf_{i-2})\)
\(f_i = (x+y)\times f_{i-1} - xy\times f_{i-2}\)
根据递推公式, 有:
\(\begin{cases} x+y = 1\\xy = 1 \end{cases}\)
解得\(x = \dfrac{1-\sqrt{5}}{2}, y = \dfrac{1+\sqrt{5}}{2}\)
有:
组合数
杨辉三角第\(i\)行\(j\)列即为 \(C_{i,j}\).
\(\sum\limits_{i=a}^{b}{C_{i,c}} = C_{b+1, c+1}-C_{a,c+1}\)
证明用杨辉三角:-
例题:
求: \(\sum\limits_{i=0}^{n}{C_{n,i} \times f_i}\), \(f_i\)为斐波那契数列第\(i\)项.
\(30\%:n\le 1000; 100\%:n\le 10^6\).将\(f_i\)写为通项公式.
\(\sum\limits_{i=0}^{n}{C_{n,i} \times f_i}\) =
向量
点积: \(W = \overrightarrow{F} \overrightarrow{s} = \mid\overrightarrow{F}\mid \times \mid\overrightarrow{S}\mid \times \cos(F,s)\)
\(\overrightarrow{a} = \overrightarrow{b}\)
- 线性性.
- 两向量方向相同, 点积即为其大小相乘.
两向量方向垂直, 点积 = 0.
- 坐标系内向量可表示为 有序数对.
向量可在平面内随意平移.
复数
定义 \(a + b_i\) 此整体为复数.
- 加法: \((a+b_i) + (c + d_i) = (a + c) + (b_i + d_i)\).
乘法: \((a+b_i) \times (c_i + d_i) = ac + ad_i + bc_i + c{d_i}^2 = (ac_i - bd_i)\)
夹角相加, 模长相乘- 坐标系上, \((a + b_i)\) 与 \((a,b_i)\)一一映射.
坐标系上, 复数运算 = 向量运算.
\(x^2 = 1\)
强行定义\(i^2 = -1\), 显然\(i\notin R\).
多项式
\(f = a_0 + a_1x + a_2x^2+...+a_nx^n\).
n 项多项式 可写成n + 1维坐标形式.
n + 1个点 确定一个 n项多项式.
写成坐标形式便于相乘.
FFT
自闭了
原根
费马小定理:
\(p\)为质数, 有: \(a^{p-1}\%p = 1\).
对于一个\(a\), 和一个质数\(p\)若存在:
\(\{a^1, a^2, ..., a^p-1\} = {1, 2,...p-1}\), 则称a为p的一个原根.
判断原根:
- 首先, \(a^{p-1} = 1\)一定成立.
- 若存在: \(a^{\dfrac{p-1}{q_i}} \not= 1(p_i\mid p)\) 则\(a\)不为原根.
\(p_i\)暴力枚举即可.
寻找原根:
原根数量为\(\Phi{p-1}\), 暴力枚举即可.
离散对数(BSGS)
- 原根求 \(\log\).
- 暴算 \(a^0, a^1, ..., a^{\sqrt{p}}\)
- 再暴算 \(a^{\sqrt{p}}, a^{2 \times\sqrt{p}}, ..., a^{\sqrt{\sqrt{p}\times \sqrt{p}}}\)
- 然后看图...
- 暴算 \(a^0, a^1, ..., a^{\sqrt{p}}\)
模意义下 开方
求模\(p\)意义下\(k\)的平方.
先找原根, 则存在\(b\), 有: \(a^b = k\).
则有: \(\sqrt{k} = a^{\dfrac{b}{2}}\).
若\(k\)为奇数, 则不可开方.
例题:
gugugu
中国剩余定理
- 模意义下线性同余方程组， 模数两两互素。
- 有通解
Lucas
将\(n,m\)写成\(p\)进制, 每一位算出后对应相乘.
积性函数
\(\gcd(a, b) = 1, f(ab) = f(a_\times f(b)\)
若\(\gcd(a, b) \not= 1, f(ab) = f(a_\times f(b)\), 则称为完全积性函数.
例题: SDOI2008 仪仗队
欧拉欧拉欧拉欧拉欧拉
例题:
求: \(\sum\limits_{i=1}^{n}\sum\limits_{i=1}^{n}{\gcd(i,j)}\)
求: \(\sum\limits_{i=1}^{n}\sum\limits_{i=1}^{n}{lcm(i,j)}\)
解多元一次方程
\(\begin{cases}\sum\limits_{i=1}^{n}{a_{1i}x} = b_1\\\sum\limits_{i=1}^{n}{a_{2i}x} = b_2\\\dots\\\sum\limits_{i=1}^{n}{a_{ni}x} = b_n \end{cases}\)
生成树计数
给定一无向图, 求其生成树的个数.
NIM游戏
全部异或起来
等价类计数
给定一\(n\times n\)的矩阵, 可将任意一格子进行黑白染色.
求使旋转后互不相同的染法的数量.
请自行阅读抽象代数学已获得解法.
- 例题: BZOJ1004
置换群...
群
- 封闭性.
- 结合性.
- 单位元.
- 逆元.
\[\Huge I\ Hate\ MathJax\]