0x3B_总结与练习
0x3B 总结与练习
本章知识点
质数
质数的判定，试除法
质数的筛选，Eratosthenes 筛法、线性筛法
算术基本定理，试除法分解质因数
约数
算术基本定理的约数个数推论、约数和推论
试除法求约数，倍数法求 每个数的约数集合
最大公约数，最小公倍数，更相减损术，欧几里得算法
欧拉函数的定义与基本性质，积性函数的定义与基本性质
试除法计算欧拉函数，Eratosthenes筛法与线性筛法快速递推欧拉函数
同余
同余、同余类、剩余系的定义
费马小定理，欧拉定理及其推论
Bézout定理，扩展欧几里得算法
乘法逆元的计算与应用
线性同余方程、方程组的求解，中国剩余定理
高次同余方程中指数的求解，Baby Step, Giant Step 算法
矩阵乘法
矩阵乘法运算与基本性质
矩阵乘法加速递推，状态矩阵、转移矩阵的构造方法
高斯消元与线性空间
系数矩阵、增广矩阵、主元、自由元、初等行变换等概念
高斯消元的实现，方程组唯一解、多解、无解的判断
线性空间的相关概念，高斯消元求线性空间的基
线性空间的推广，异或空间的性质与应用，去重与不去重异或空间的形态
组合计数
加法原理，乘法原理，排列数，组合数及其性质
组合数的递推求法、逆元求法、分解质因数约分求法
二项式定理，Lucas定理
多重集的排列数和组合数
Catalan数列的定义和应用
容斥原理与Mobius函数
容斥原理的理解与应用
多重集组合数的完整解析
Mobius函数的定义、计算与应用
概率与数学期望
随机变量、概率、数学期望等相关定义
数学期望的线性性质，数学期望的递推计算，数学期望与动态规划的结合
0/1分数规划
0/1分数规划模型与二分法求解
博弈论之SG函数
NIM游戏等简单博弈模型
SG函数的计算与应用
练习
完成本章中所有例题的代码实现
2.GCD
题目地址：BZOJ2818，提示：线性筛法/最大公约数/欧拉函数递推
3. Longge's problem
题目地址：POJ2480，提示：最大公约数/欧拉函数/积性函数
4.青蛙的约会
题目地址：POJ1061，提示：扩展欧几里得算法
5. Xiao 9*大战朱最学
题目地址：TYVJ1339，提示：中国剩余定理
6.计算器
题目地址：BZOJ2242，提示：线性同余方程/高次同余方程
7. Matrix Power Series
题目地址：POJ3233，提示：矩阵乘法/分治
8.233 Matrix
题目地址：HDOJ5015，提示：矩阵乘法/递推
9. Widget Factory
题目地址：POJ2947，提示：高斯消元/同余
10. XOR
题目地址：BZOJ2115，提示：线性空间/高斯消元/生成树
11. 新NIM游戏
题目地址：BZOJ3105，提示：线性空间/高斯消元/博弈论
12.排列计数
题目地址：BZOJ4517，提示：组合/错排问题
13. Sky Code
题目地址：POJ3904，提示：容斥原理
14.守卫者的挑战
题目地址：TYVJ1864，提示：概率/动态规划
15. 换教室
题目地址：NOIP2016/BZOJ4720，提示：数学期望/动态规划
16. Dropping tests
题目地址：POJ2976，提示：0/1分数规划
17. 魔法珠
题目地址：TYVJ2049，提示：博弈论/SG函数
18. Georgia and Bob
题目地址：POJ1704，提示：博弈论