I. 基础知识
1. 带余除法（小学）
1. 定义
对于整数 (a,b)，若有 (q,r) 满足：
其中 (0le r<b)，那么 (r) 称作 (a) 模 (b) 的 余数，记作 (amod b) .
顺便一提，(a=leftlfloordfrac ab ight floor) .
2. 性质
[(a+b)mod p=((amod p)+(bmod p))mod p ][(a-b)mod p=((amod p)-(bmod p))mod p ][abmod p=((amod p)(bmod p))mod p ]Proof:
设 (a=a'p+r_0,b=b'p+r_1)，则有：
[(a+b)mod p=(r_0+r_1)mod p=((amod p)+(bmod p))mod p ][(a-b)mod p=(r_0-r_1)mod p=((amod p)-(bmod p))mod p ][abmod p=(r_0cdot r_1)mod p=((amod p)(bmod p))mod p ag*{□} ]
2. 最大公约数（gcd）/ 最小公倍数（lcm）
1. 定义
最大公约数：(max G;s.t.;pmod G=qmod G=0)，则 (G) 为 (p,q) 最大公约数，记做 (gcd(p,q)=(p,q)=G)
最小公倍数：(min L;s.t.;Lmod p=Lmod q=0)，则 (L) 为 (p,q) 最小公倍数，记做 (operatorname{lcm}(p,q)=[p,q]=L)
2. 性质
(gcd(a,b)=gcd(b,amod b))
3. 高精度
II. 矩阵及其应用
1. 定义
(n) 行 (m) 列的数表就是 矩阵（Martix），矩阵里的数叫做矩阵的 元素（Element），例如下面就是三个矩阵：
矩阵一般用大写字母 (A,B,C,cdots) 表示
特殊的矩阵有:
- 零矩阵 (O)，所有元素都是 (0) 的矩阵 .
- 单位矩阵 (I)（或写作 (E)），对角线是 (1)，其余为 (0) 的矩阵：(egin{bmatrix}1&0&0&cdots&0\0&1&0&cdots&0\0&0&1&cdots&0\vdots&vdots&vdots&ddots&vdots\0&0&0&cdots&1end{bmatrix}) .
2. 运算
相等：所有元素相等
相加减：所有元素相加减
数乘：用数乘每个元素
相乘
3. 递推
Fibonacci 数列：([F_n,F_{n-1}]egin{bmatrix}1&1\1&0end{bmatrix}=[F_{n+1},F_n])
更改系数类似
(F_n=F_{n-1}+F_{n-3}) 形：开 (F_n,F_{n-1},F_{n-2})
有常数项：例子：(F_n=F_{n-1}+F_{n-2}+1)，递推：([F_n,F_{n-1},1]egin{bmatrix}1&1&0\1&0&0\1&0&1end{bmatrix}=[F_{n+1},F_n,1])
求和：
- 推式子再做矩阵快速幂
- 通用办法：例子：求 Fibonacci 数列和，递推：([F_n,F_{n-1},S_n]egin{bmatrix}1&1&0\1&0&1\0&0&1end{bmatrix}=[F_{n+1},F_n,S_{n+1}])，(S_n) 是和 .
4. 图论
https://www.cnblogs.com/CDOI-24374/p/14407416.html
Problem 杰杰的女性朋友
对于每个点 (u) 给定属性 (in_{u,1},in_{u,2},cdots,in_{u,k})，(out_{u,1},out_{u,2},cdots,out_{u,k})
对于任意 ((u,v))，(u) 到 (v) 有 (sumlimits_{i=1}^k ou_{u,i}in_{v,i}) 条道路
问 (u) 到 (v) 不超过 (d) 条道路的方案数 .