Day4 上午——数学
一、BSGS
给定质数$p$，给定$a$和$b$，$(a,p)=1$。
求最小的非负整数$x$，使得$a^x\equiv b(mod\;p)$。
解法
首先根据欧拉定理$a^{\phi(p)}\equiv1(mod\;p)$，当$a^x\equiv b(mod\;p)$有解，最小非负整数解一定在$[0,\phi(p))$中。
令$m=\sqrt{\phi(p)}$，任意$x\in [0,\phi(p))$都可以分解成$im+j$的形式，其中$0\le i \le m,0 \le j <m$。
枚举$i$的值，$a^x\equiv b(mod\;p)\Leftrightarrow a^j\equiv a^{-im}b(mod\;p)$。
将$a^0,a^1,a^2…$放到$hash$表中查询就可以了。
复杂度：$O(\sqrt{\phi(p)})$
另外，如果要解决$p$不为素数的情况，需要用到$exBSGS$
模板
1 |
|
exBSGS
1 |
|
二、Miller-Rabin
给定$n$，判定$n$是否为素数。
解法
首先筛去偶数，我们只考虑奇数的情况。
显然$\forall x\in[1,p-1],x^p\equiv x(mod\;p)$，但是有些合数也满足这个性质，所以不能直接用这个性质来判断一个数是不是素数。
考虑$x^2\equiv 1(mod\;n)$的根，若$n$是奇素数，则只有$1$和$n-1$(即$-1$两根)，因为原式可以改写成$(x+1)(x-1)\equiv 0(mod\;n)$。
设$n-1\equiv 2^r\times d$，其中$d$是奇数。$n$是合数当且仅当存在$0\le k< r,a^{2^k\times d}\not\equiv1,-1(mod\;n)$，且$a^{2^{k+1}\times d}\equiv1(mod\;n)$。
选取多个$a$进行二次探查，减小错误率。
模板（int64）
1 |
|
实践结论
对于$int32$范围内的数，我们选取$2,7,61$探测即可。
对于$int64$范围内的数，我们选取前十个素数探测即可。
三、Pollard-rho
给定$n$，将$n$质因数分解。
解法
如果用Miller-Rabin测试出来$n$是素数，直接停止算法。
随机基底$a$和$c$，，生成序列$x_0=a,x^2_{i-1}+c(mod\;n)$，可以说序列${x_i}$是一个随机序列。
如果出现$(x_i-x_{2i+1},n)\not=1$，停止算法。令$d=(x_i-x_{2i+1},n)$，若$d\not=n$，那么$d$就是$n$的一个非平凡因子，$n$可以被分为$\dfrac{n}{d}$和$d$相乘的结果，递归下去对$\dfrac{n}{d}$和$d$分别求解。
复杂度$O(N^{\dfrac{1}{4}})$
四、Linear-Shaker
给定$n$，筛出$n$以内的所有素数。
解法
见线性筛模板P3383。
五、Chinese Reminder Thereom
$x\;mod\;n_1=x_1$
$x\;mod\;n_2=x_2$
$x\;mod\;n_3=x_3$
…
其中$n_1,n_2,…,n_k$两两互质，求$x$的一个合法解。
解法
令$N=\prod\limits_{i=1}^{k}n_i$，$m_i=\dfrac{N}{n_i}$，$t_i=m_i^{-1}(mod\;n)$。
$x=\sum\limits_i x_im_it_i(mod\;n)$
我们容易发现，当$j=i$时，$m_it_i\equiv1(mod\;n_j)$，当$j\not=i$时，$m_it_i\equiv0(mod\;n_j)$，因此$x$一定是方程组的一组解。
模板（UVA756）
1 |
|
exCRT模板（POJ2891）
1 | //#pragma GCC optimize("fast-math,unroll-loops") |
六、Quadratic residue
给定$y$和奇素数$p$，求$x$，使得$x^2\equiv y(mod\;p)$。
欧拉判别法
若$y^{\dfrac{p-1}{2}}\equiv1(mod\;p)$，则$y$在模奇素数$p$下有二次剩余
若$y^{\dfrac{p-1}{2}}\equiv-1(mod\;p)$，则$y$在模奇素数$p$下没有二次剩余
勒让德符号$(\dfrac{a}{p})\equiv a^{\dfrac{p-1}{2}}$
$1,…,p-1$中有$\dfrac{p-1}{2}$个数的勒让德符号为$1$，另外$\dfrac{p-1}{2}$个数的勒让德符号为$-1$。
解法
不断随机$a$，使得$(\dfrac{a^2-y}{p})=-1$
令$\omega=\sqrt{a^2-y},x=(a+\omega)^{\dfrac{(p+1)}{2}}$
由于$x^2\equiv(a+\omega)^p\times(a+\omega)\equiv(a+\omega)\sum\limits_{j}C^j_p\omega^{p-j}$
$\equiv(a^p+\omega^p)(a+\omega)\equiv(a-\omega)(a+\omega)\equiv a^2-\omega^2\equiv y(mod\;p)$
所以最终答案就是$(a+\sqrt{a^2-y})^{\dfrac{p+1}{2}}$
例题
给定长度为$n$的整数$a$，判断$a$是否是完全平方数。
$n\le1000$
思路
选多组素数进行判别，考虑$x^2\equiv a(mod\;p)$成立，随机一些素数$p$判别就行了。
七、Multiplicative function
狄利克雷卷积
$(fg)(n)=\sum_{d|n}f(d)g(n/d)$
积性函数
积性函数的性质：
- $\forall (a,b)=1,f(ab)=f(a)f(b)$
- 积性函数的卷积仍然是积性函数
所以其实我们可以把$n$看成$n=p_1^{k_1}p_2^{k_2}…p_m^{k_m}$
常见的积性函数：
- 普通函数:$I(n)=1,id(n)=n,e(n)=[n=1]$
- 除数函数:$\sigma_k(n)=\sum\limits_{d|n}d^k$
- 欧拉函数:$\phi(n)=n\times\dfrac{p_1-1}{p_1}\times…\times\dfrac{p_m-1}{p_m}$
- 莫比乌斯函数:$\mu(n)=[k_1\le1][k_2\le1]…k_m\le1^m$
$\sum\limits_{d|n}\mu(d)=[n=1]\Rightarrow\mu\times1=e$
$\sum\limits_{d|n}\phi(d)=n\Rightarrow\phi\times1=id$
$\phi$和$\mu$的前$n$项与前缀和
前$n$项可以在做线性筛的过程中求出，前缀和用杜教筛或者min25等算法解决
Day4 下午
八、Primitive root（原根）
给定$n$，若$a$满足$(a,n)=1$且$1,a,a^2,a^3,…,a^{\phi(n)-1}$在$mod\;n$下都互不相同，则称$a$是$n$的一个原根。
原根的性质
- $2,4,p^n,2p^n$有原根，$p$是奇素数。
- 若$n$有原根，则原根数量为$\phi(\phi(n))$个。
阶
最小的非零$x$使得$a^x\equiv 1(mod\;p)$，记为$$
有关阶的定理
①若$p>1$且$(a,p)=1$，又满足$a^n\equiv1(mod\;p)$，则$|n$
②$|\phi(p)$
求法
将$\phi(p)$质因数分解，$\phi(p)=p_1^{w_1}p_2^{w_2}…p_k^{w_k}$
枚举$g$，如果恒满足$g^{\dfrac{\phi(m)}{p_i}} \not =1$，其中$i=1,2,…,k$
则$g$是$m$的一个原根
九、Combination（组合数）
求法：
杨辉三角
预处理阶乘及逆元
十、Recurrence relation（递推关系）
矩阵乘法：$C_{i,j}=\sum A_{i,k}\times B_{k,j}$。
例题
给定一张$N$个点$M$条边的有向图，$Q$次询问图中从每个点出发的长度为$K$的路径各有多少条。
$N\le100,Q\le10,K\le100$
思路
分块矩乘。
十一、Principle of inclusion-exclusion（容斥原理）
容斥原理
$F(A\bigcup B\bigcup C)=F(A)+F(B)+F(C)-F(A\bigcap B)-F(B\bigcap C)-F(A\bigcap C)+F(A\bigcap B\bigcap C)$
十二、Binomial inversion(二项式反演)
$f_n=\sum\limits_{i=0}^{n}(-1)^iC^i_ng_i\Leftrightarrow g_n=\sum\limits_{i=0}^{n}(-1)^iC^i_nf_i$
$f_n=\sum\limits_{i=0}^{n}C^i_ng_i\Leftrightarrow g_n=\sum\limits_{i=0}^{n}(-1)^{n-i}C^i_nf_i$
例题、集合计数
$n$个元素有$2^n$种不同的子集，现从$2^n$个子集中选取若干子集，求有多少种方案，使得选出集合的交元素个数为$K$。
$n,k\le 10^6$，对$10^9+7$取模
思路
令$g_k$表示选出集合的集合交为$k$时的方案数，$f_k$表示选出集合的集合交至少为$k$时的方案数。
$f_i=C^i_n(2^{2^{n-i}}-1)$
$f_i=\sum\limits_{j=i}^{n}g_jC^i_j$
推出$g_i=\sum\limits_{j=i}^{n}C^j_n(2^{2^{n-j}}-1)(-1)^{j-k}C^k_j$
十三、Probability Thereom（概率论）
期望：$E(x)=\sum\limits_{i=1}^{n}a_iP(x=a_i)$
期望具有线性性
例题、求逆序对
长度为$n$的序列，求逆序对的期望个数。
令$a_{i,j}$表示$i,j$是否逆序，逆序则为1，否则为0。
例题、Clear the room
给定一个$n\times m$的网格，$(i,j)$中有物品价值$w_{i,j}$。现取$K$次，每次取走一个矩形内所有物品，问$K$次操作后拿走物品价值和期望。
$n,m\le500,K\le10^9$
思路
求出每一个点被选中的概率$p$，
不难想到我们要想选中一个点$(x,y)$，必须要使得选中的矩形包含$(x,y)$，也就是$x_1\le x\le x_2,y_1\le y \le y_2$，那么推出结论：选中一点$(x,y)$的概率$p=\dfrac{x\times(n-x+1)\times y\times(m-y+1)}{n^2\times m^2}$，答案就等于$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}w_{i,j}p_{i,j}^k$
十四、Gaussian（高斯消元）
模板。