膜拜 zzh 大神。
原链接。
筛质数
-
埃氏筛 较为常用
-
线性筛 可用来求一个数的最小的因子
乘法逆元
求逆元的三种方法
-
模数是质数时：费马小定理 较为好写
-
不是质数时：扩展欧几里得 转化为\(ax+by=1\)的形式
-
线性求逆元 公式:$ inv[i]=\left \lfloor p/i \right \rfloor\times inv[p:mod:i]:mod:p \ $
扩展欧几里得
证明：
\(ax+by=gcd(a,b)\)
\(bx+(a-a/b*b)*y=gcd(b,a\)%\(b )\)
\(ay+b(x-a/b*y)=ax+by\)
\(x=y,y=x-a/b*y\)
其实就是\(gcd(a,b)=gcd(b,a\)%\(b)\)的一个变形 背板子就行
题:青蛙的约会
中国剩余定理
板子 过了
题：P1495
组合数学
较难 常与dp结合
几种求组合数的方法
-
杨辉三角 \(n\),\(m\)较小
$C_{n}^{m} =C_{n-1}^{m} +C_{n-1}^{m-1} $ -
线性递推 n唯一时
\(C_{n}^{m}=\frac{n-m+1}{m}* C_{n}^{m-1}\) -
通项公式
-
质因数分解
-
卢卡斯定理
\(C_{n}^{m}\) \(mod\:p\) = \(C_{n\:mod\:p}^{m\:mod\:p}* C_{n/p}^{m/p} mod\:p\)
一些公式
-
\(\sum_{i=0}^{b} C_{i}^{m} =C_{b+1}^{m+1}\)
-
\(C_{n}^{r} C_{r}^{k} = C_{n}^{k}C_{n-k}^{r-k}\)
-
\(\sum_{i=0}^{k} C_{n}^{i} C_{m}^{k-i}=C_{n+m}^{k}\)
-
\(\sum_{i=0}^{n}iC_{n}^{i}=n* 2^{n-1}\)
......
容斥:
最基本的思想就是 所有方案-不合法的方案=合法方案
例题：Cheerleaders
题目中要求网格图的四个边都至少有一个人
根据容斥的思想 答案即为 第一条边至少有一个人的方案\(+\)第二条......\(-\)第一条和第二条都至少有一个人\(-\)第一条和第三条......以此类推
-
二项式反演
记 \(f_n\) 表示恰好使用 \(n\) 个不同元素形成特定结构的方案数，\(g_n\) 表示从 \(n\) 个不同元素中选出 \(i \geq 0\) 个元素形成特定结构的总方案数。
\(g_n = \sum_{i = 0}^{n} \binom{n}{i} f_i\)
\(f_n = \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} g_i\)
题目中有这些字眼 "恰好"等 且求"至少" "至多" 的方案
比较好求，我们就可以考虑使用二项式反演
题：
组合数：车的放置
CQOI2014数三角形
容斥：HAOI2008硬币购物
二项式反演：已经没有什么好害怕的了