闲话

数学是OI知识点中学的最差的部分之一。

Part 1:复习

Part 2

Section 1:BSGS

给定质数p,给定a、b,$(a,p)=1$。

求最小非负整数x使得$a^x\equiv b\pmod{p}$。

Section 2:Miller-Rabin

二次探查和费马定理测试

实际应用细节

Section 3:Pollard-Rho

复杂度$O(n^{\frac{1}{4}} poly(n))$。

优化的Pollard-Rho

没讲,可参见edgration的blog。复杂度可以省去一个$log$。

Section 4:Linear-Shaker

线性筛。略。

Section 5:CRT

刑如$x\equiv x_i\pmod{n_i}$的一组方程(其中$n_i$两两互质)。

令$N=\prod n_i,m_i=N/n_i,t_i\equiv m^{-1}\pmod{n_i}$。

则一个可行解即为$$x=\sum x_i m_i t_i\pmod N$$

证明:

Section 6:二次剩余

给定y和奇质数p,求x,使得$x^2=y\pmod p$。

欧拉判别法

定义勒让德符号$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}$即$$\left(\frac{n}{p}\right)=\begin{cases}1&n在模p意义下是二次剩余\\-1&n在模p意义下是非二次剩余\\0&n\equiv 0\pmod p\end{cases}$$

Cipolla's Algorithm

例题

给定长度为n的高精度数字a,请判断a是不是完全平方数。$n\le 1000$

Section 7:积性函数

其他见莫比乌斯反演学习笔记

Section 8:原根

给定n,若a满足$(a,n)=1$且$a^0,a^1,a^2,...,a^{\varphi(n)-1}$在$\pmod n$下都互不相同,则称a是n的一个原根。

性质:

$<a>=x$,阶即是满足$a^x\equiv 1\pmod n$的最小$x$。

如何计算原根

由于原根的个数为$\varphi(\varphi(n))$,约有$\frac{1}{log n}$概率取到,因此直接随机即可在期望$O(log)$复杂度内取到原根。

判断原根

根据第二点性质,验证$a$是否满足原根的定义即可。

具体来说,若存在$x\in [1,\varphi(n)-1]$使得$a^x\equiv 1\pmod n$,则$x$一定为$\varphi(n)$的因子。

并且若$a^x\equiv 1\pmod n$,则有$a^{xb}\equiv 1\pmod n$。

因此将$\varphi(n)$分解为$\varphi(n)=\prod p_i^{r_i}$,分别验证$a^\frac{\varphi(n)}{p_i}\not\equiv 1\pmod n$是否成立即可,若不成立则$a$不为原根,否则即为原根。

Section 9:组合数相关

求$\left (^n_m\right)\pmod {p^k}$

更大数据范围的需要结合$Lucas$定理等。

求$\left (^n_m\right)\pmod {\prod p_i^{k_i}}$

参照上一个问题,中国剩余定理合并即可。

矩阵加速

例题

给定一张n个点m条边的有向图,q次询问图中每个点出发的经过k条边的路径有多少条($n,m\le 100,k\le 100,q\le 10$)。

Section 10:二项式反演

相关问题:

例题

[BZOJ2839]集合计数

Section 11:概率论

期望公式:$E(x)=\sum P(x=a_i)\cdot a_i$($a_i$为价值)

期望的线性性

即使事件A与B不独立,仍然存在$E(A+B)=E(A)+E(B)$

例:求随机排列中逆序对个数的期望。

令$a_{i,j}=\begin{cases}1&x_i和x_j形成逆序对\\0&x_i和x_j不形成逆序对\end{cases}$

$E(x)=E(\sum\limits_{1\le i<j\le n}a_{i,j})$,由期望的线性性可推得$E(x)=\sum\limits_{1\le i<j\le n}E(a_{i,j})$

例题

[JSK1483G] Clear the Room

练习计划

Section 12:行列式

较难并且没时间讲了。

Section 13:矩阵树计数

需要用到行列式。证明复杂。

经典例题[BZOJ1016]最小生成树计数

Section 14:群论

同样没时间讲了。

Section 15:SG函数

同样没时间讲了。

闲谈

keyboard_arrow_up