讲师：施开成，CTSC rk6!!!
数学
01分数规划
USACO18OPEN
二分答案，转化答案，发现 \(\sum(w_i-ct_i)\ge 0\)
随后背包解决问题。
数论
模 \(p\) 意义：忽略一个数的具体值，只关心在对 \(p\) 做除法后的余数。
对于模合数，一定要避免除法。
逆元
将 \(\frac{a}{b}\) 视为 \(a\times(\frac{1}{b})\)。
\(a\) 的逆元就是在模意义下的倒数。
互为逆元的数乘积为 \(1\)。
威尔逊定理
对于质数 \(p\)，存在 \(1\times 2\times\ldots\times (p-1)=-1(\mod p)\)
费马小定理
对于质数 \(p\) 和 \(a\ne 0(\mod p)\) ，有 \(a^{-1}=1(\mod p)\)
所以可以快速幂计算出逆元。
欧拉定理
对于合数处理逆元。
\(\phi(p)\) 定义为 \(1\sim p\) 与 \(p\) 互质的数的个数。
对于任意正整数 \(p\ge 2\) 和任意 \(a\) 满足 \(\gcd(a,p)=1\)，有 \(a^{\phi(p)}=1(\mod p)\)
对于 \(p\) 为质数，可以发现就是费马小定理。
考虑用费马小定理的方法证明。
线性预处理逆元
\(O(n)\) 求出所有数在 \(\mod p\) 的逆元。
递推公式
P3811
预处理阶乘逆元
可以递推计算。
线性时间复杂度。
推广，可以在 \(O(n+\log q)\) 的时间内求出 \(a_1,a_2\ldots,a_n\) 中每一个数的逆元。
预处理前缀积和前缀积逆元，blabla
矩阵
向量：一个 \(n\) 维向量就是由 \(n\) 个数构成的有序序列。
向量加法：长度相同向量中的每个元素都对应加。
转置：横竖换一下，右上角标 \(T\)
矩阵：\(A_{i,j}\)
矩阵与向量进行乘法。
列数与行数相同。
真tm抽象
线性变换
从向量到向量的变换是线性的。
映射。
一个矩阵可以描述一个线性变换。
一个 \(n\times m\) 的矩阵和 \(m\times p\) 的矩阵可以进行乘法，得到 \(n\times p\) 的新矩阵。
problem 3.0.1 连分数
听不懂
线段树维护矩阵乘积
矩阵乘法描述变换的复合。
矩阵乘法：\(C_{i,j}=\sum\limits_{k=1}^mA_{i,k}\times B_{k,j}\)
满足结合律
定义 \(n\) 阶方阵描述 \(n\times n\) 的矩阵，矩阵快速幂复杂度 \(O(n^3\log k)\)
\(\max(a,b)+c=\max(a+c,b+c)\)
\(\max\) 不能求逆。
矩阵快速幂可以算经过 \(k\) 条边后的最短路。
听不懂。
组合数
总之很抽象。
但是 A+B
二项式定理
\((a+b)^n=\sum_{i=0}^n(n,i)a^ib^{n-i}\)
插板法
problrm 4.1.1
球一样，盒子不一样。
放 \(m-1\) 个挡板，其实就是 \((n+m-1,n)\)，有 \(n+m-1\) 个东西，把其中 \(n\) 个当做球。
容斥
不考虑老师相邻时，可以把老师看做男生。
否则把两个老师看做一个老师。
满足 \(n\) 个限制 \(\rightarrow\) 一些限制不满足，其余限制随意。
硬币购物
总之容斥
概率
离散概率：\(\sum_{omg\in OMG}P(omg)=1\)
期望
发生概率乘上事件的值。
越来越趋近于试验的平均结果。
期望的和=和的期望
P5104
直接看 ppt
小 A 抛硬币
令 \(f_x\) 代表已经连续抛出了 \(x\) 个 \(1\)，期望再抛几次能完成要求，显然答案为 \(f_0\)。
考虑抛下一个硬币，如果抛到正面会转移到 \(f_{x+1}\)，否则转移回 \(f_0\)。
即 \(f_x=\frac{f_{x+1}+f_0}{2}+1\)
边界 \(f_n=0\)
对于递推式子，不把 \(f_0\) 视为常数，解方程，回代。
小 A 抛骰子
听不懂。
标签：day6,定理,矩阵,逆元,times,寒假,2.7,向量,mod From： https://www.cnblogs.com/BYR-KKK/p/18011002