求逆元
给定(a)求(x)使(axequiv1(modspace p))
-
费马小定理（求(a^{p-2})，(p)为质数，快速幂）
-
扩展欧基米德
存在(y)使(ax+by=1)
求方程一组解
((x+kb)\%b,kin Z^+)即为解
-
递推（(inv_i=-(p/i)*inv_(p\%i)(modspace p))）
素数筛
目的：快速求(n)以内的素数情况
埃氏筛
做法其实很简单，首先将(2)到(n)范围内的整数写下来，其中(2)是最小的素数。将表中所有的(2)的倍数划去，表中剩下的最小的数字就是(3)，他不能被更小的数整除，所以(3)是素数。再将表中所有的(3)的倍数划去……以此类推，如果表中剩余的最小的数是(m)，那么(m)就是素数。然后将表中所有(m)的倍数划去，像这样反复操作，就能依次枚举n以内的素数，这样的时间复杂度是(O(ncdot log_2(log_2n)))。
欧拉筛
基本思想 ：在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。
for每个数，枚举(j)将(icdot su[j])标为(0)，如果(i)是(su[j])的倍数就break掉，如果枚举道(i)还是(1)说明(i)为质数（(O(n))复杂度）
打表
不会时打表找规律
递推
1. 线性（参见上讲）
2. 矩阵乘法
前提：矩阵的行数与另一个矩阵的列数相同
一个的矩阵(A)，的矩阵(B)，令(C=AB)，则有(C_{i,j}=sum A_{i,k}B_{k,j})（(k)有实际意义）
矩阵乘法满足结合律，用快速幂压缩时间
例子：斐波那契数列
tip：NOIP几乎不考
组合计数
(A_n^r=frac{n!}{(n-r)!})，特别的，若(r>n)，则(A_n^r=0)
(n)个元素的(r)圈排列的数目为(frac{A_n^r}{r}=frac{n!}{rcdot(n-r)!})，特别的，当(r=n)时，园排列数目为((n-1)!)
(C_n^r=frac{n!}{r!(n-r)!})，特别的，若(r>n)，则(C_n^r=0)
(C_n^r=C_n^{n-r}\A_r^n=r!C_n^r\sum_{i=0}^nC^i_n=2^n\frac{k}{n}C_n^k=C_{n-1}^{k-1}\sum_{m=0}^nC_m^k=C_{n+1}^{k+1}\C_n^rC_r^k=C_n^kC_{n-k}^{r-k}\sum_{k=0}^n(C_n^k)^2=C_{2n}^n\C_{m+n}^r=sum_{k=0}^rC_m^kC_n^{r-k})
(C_n^m=C_{n-1}^m+C_{n-1}^{m-1}= frac{n!}{m!(n-m)!}=C_n^{n-m})
求组合数的方法：(O(n))预处理阶乘及它的逆元，每次(O(1))求组合数
插板法：求方程(sum_{i=1}^mx_i=n)的个数，(x_iin Z^+)
(n-1)个空，(m-1)个板，及求(C_{n-1}^{m-1})
多重集合
令(S={n_1a_1,n_2a_2,cdots,n_ka_k})为多重集合，元素的总个数为(n=sum_{i=1}^kn_i)，其中(a)数列是(k)种不同的元素，(n_i)表示(a_i)在(S)中出现的个数，称为(a_i)的重复度（其中(0<n_i<+infty)）
- (S)的全排列个数是(frac{n!}{Pi_{i=1}^kn_i})
- 若(rle n_i,i=1,2,cdots,k)，那么(S)的(r)排列数是(k^r)，则(S)的(r)组合数是(C_{k+r-1}^r)
Catalan数列
定义(Catalan)数(c_n)表示长度为(2n)的括号序列的个数
( herefore c_n=C_{2n}^n-C_{2n}^{n-1})
概率与期望
其实是个计数题
期望的线性性（AGC006C）
e.g：硬币题（某年西安结论题）
Lucas定理
计算组合数(C_n^mmodspace p(pmbox{为质数}))时有如下定理：
(C^n_mequiv C^{[n/p]}_{[m/p]}cdot C^{n\%p}_{m\%p}(modspace p))
递归(O(plog_pspace n))计算，但要求(p)的范围不能太大，一般是(nle10^5)
例题：洛谷模板题
exlucas
计算组合数(C_n^mmod space p)
把(p)质因数分解，分别求出对应的余数，用中国剩余定理求解
即求(C_n^mmodspace p)
记(v_p(n))为(n)的素因子分解中(p)的幂次，上下拿出因子(p)
勒让德定理：(v_p(n!)=sum_{l=1}^{+infty}[frac{n}{p^t}]=frac{n-s_p(n)}{p-1})
计算(n!,m!,(n-m)!)在模(p^t)意义下的值，把后两个求逆元
前面是以(p^t)为周期，后面余下的不足(p^t)个
(calc(n,p,p^t)=[x^{frac{n}{p}}]cdot restcdot calc(frac{n}{p},p,p^t))
例题：古代猪文、洛谷模板题
筛
-
埃氏筛(O(ncdot log_2(log_2space n)))+欧拉筛(O(n))
欧拉筛伪代码：
for(int i=2; i<=N; i++) { if(!vis[i]) { prime[++prime[0]]=i; } for(int j=1; j<=prime[0]&&i*prime[j]<=N; j++) { vis[i*prime[j]]=1; if(i%prime[j]==0) { break; } } }比较：
欧拉筛 埃氏筛 先枚举筛选底数的倍数，再枚举筛选底数 先枚举筛选底数，再枚举筛选底数的倍数
BSGS
用(O(sqrt{n}))求(x)使得(a^xequiv b(modspace n),gcd(a,n)=1)
设(x=Am-B(1le Ale k,1le Ble m))
则有(a^{Am}equiv ba^B(modspace n))，枚举(B)把(ba^B)并用hash/map存下来
枚举(A)，逐一计算(a^{Am})，寻找是否有相同的(ba^B)
这里(x)由(A,B)的范围确定为(0le xle km-1)要把(0le x<n)包含所以(kmge n)
时间复杂度为(O(max(k,m)))，取(k=m=[sqrt{n}])最优，为(O([sqrt{n}]))
进阶：
求(x)使得(x^aequiv b(modspace p),p)为质数
令(x=g^c)，则(x^aequiv (g^c)^aequiv(g^a)^cequiv b(modspace p),g^a)是固定的数，转换成原来的BSGS
博客：
类欧几里得算法
计算(f(a,b,c,n)=sum_{i=0}^n[frac{ai+b}{c}])
- (age c)或者(bge c)，则(f(a,b,c,n)=f(a\%c,b\%c,c,n)+frac{n(n+1)}{2}[frac{a}{c}]+n[frac{b}{c}])
- 其余情况：(f(a,b,c,n)=n[frac{an+b}{c}]-f(c,c-b-a,a,[frac{an+b}{c}]-1))
拓展：计算(g(a,b,c,n)=sum_{i=0}^ni[frac{ai+b}{c}],h(a,b,c,n)=sum_{i=1}^n[frac{ai+b}{c}]^2)
先取模：
(g(a,b,c,n)=g(a\%c,b\%c,c,n)+[frac{a}{c}frac{n(n+1)(2n+1)}{6}+[frac{b}{c}]frac{n(n+1)}{2}])
(h(a,b,c,n)=h(a\%c,b\%c,c,n)+2[frac{a}{c}]f(a\%c,b\%c,c,n)+2[frac{a}{c}]g(a\%c,b\%c,c,n)+[frac{a}{c}]^2frac{n(n+1)(2n+1)}{6}+[frac{b}{c}]^2(n+1)+[frac{a}{c}][frac{b}{c}]n(n+1))
取不了模时：
(g(a,b,c,n)=frac{mn(n+1)-h(c,c-b-1,a,m-1)-f(c,c-b-1,,m-1)}{2})
(h(a,b,c,n)=nm(m+1)-2g(c,c-b-1,a,m-1)-2f(c,c-b-1,a,m-1)-f(a,b,c,n))
数论分块
求解类似(sum_{i=1}^n[frac{n}{i}])的问题，复杂度为(O(sqrt n))
- (i<sqrt{n})，逐点计算
- (i>sqrt{n})，取区间计算
(f([frac{n}{i}])cdot length)与([frac{n}{i}])相同的(j)有多少个
( herefore[frac{n}{i}]le frac{n}{j}le [frac{n}{i}]+1)
(jle [frac{n}{[frac{n}{i}]}]\frac{n}{[frac{n}{i}]-1}<jle [frac{n}{[frac{n}{i}]}])
莫比乌斯反演
定义莫比乌斯函数(mu(i))如下
(mu(1)=1\mu(i)=(-1)^k,imbox{没有平方因子},kmbox{为i的素因子个数}\mu(i)=0,imbox{有平方因子})
有如下性质：
- (mu(a)mu(b)=mu(ab))（积性函数）
- (sum_{d|n}mu(d)=[n==1])
- (sum_{d|n}mu(d)frac{n}{d}=φ(n))
有函数(F,f)为(N^* ightarrow N^*)的函数，有(F(n)=sum_{d|n}f(d))，求用(F)函数来表示(f)函数
过程略
(ecause f(n)=sum_{d|n}mu(frac{n}{d})F(d))
反推依然（过程略）
( herefore f(n)=sum_{d|n}mu(frac{n}{d})F(d)Leftrightarrow F(n)=sum_{d|n}f(d))
例题
-
小凯的疑惑（裴蜀定理）
考虑(0le x<b)的那组解
凑不出(c)表示(y)为负数，即(x<b\yle-1\c=ax+byle a(b-1)-b=ab-a-b)
且因为((b-1,-1))是一组解，所以(ab-a-b)是凑不出来的。所以它就是答案
-
给定(n,m)，定义合法区间为满足(max{a_l,a_l+1,...,a_r}-min{a_l,a_l+1,...,a_r}=r-l)的区间([l,r])，对所有长度为(n)的排列，求他们合法区间的个数和，对(m)取模
(nle2.5cdot10^5)
-
数列的gcd（Bzoj4305）
给一个数列(a)，对所有(1le ile m)求修改其中恰好(k)个数变成序列(b)使得(gcd{b_j}=i)的方案数
(1le a_i,b_ile mle 3cdot10^5\1le n)
我们先求(g_i)表示(gcd)为(i)的倍数的方案数，再通过(f_i=g_i-f_{2i}-f_{3i}-...)，求出(gcd)为(i)的方案数
那么(i)的倍数一共有([frac{m}{i}])个，(a_i)有一部分是(i)的倍数（可以不用修改），假设有(x)个，有一部分不是（必须用一次修改让它变成(i)的倍数），假设有(y)个
对于不是的那些，每一个能修改成([m/i])个数其中任何一个，所以方案数为([m/i]^y)
对于使得那些，因为一共要修改(k)次，所以要选(k-y)个出来修改，每一个修改成的数有（([m/i]-1)）种方案（不能等于原来的(a_i)），所以方案数为(C_x^{k-y}cdot([m/i]-1)^{k-y})
乘起来即为(g_i)
-
给定一个(ncdot m)的网格，请计算三点都在格点上的三角形共有多少个？
(1le n,mle 1000)
共有(C_{nm}^3)种可能方案
再减去三点共线的数目
设三点为((x_1,y_1),...(x_3,y_3))，不妨设(x_1<x_2<x_3)再不妨设(y_1<y_2<y_3)（否则乘(2)），则它们共线就是((x_2-x_1)/gcd(x_2-x_1,y_2-y_1)=(x_3-x_2)/gcd(x_3-x_2,y_2-y_1)\(y_2-y_1)/gcd(x_2-x_1,y_2-y_1)=(y_3-y_2)/gcd(x_3-x_2,y_3-y_2))
枚举(x_3-x_1,y_3-y_1)即可
-
(cf442B)
有(n)个人，你可以挑出一部分人来向他们要一道题，第(i)个人给你一道题的概率为(p_i)。问在所有的选人方案里，有且仅有一道题的最大概率是多少？
贪心
对(p)数组进行排序选(p_i)最大的人，每多选一个计算一次答案，如果答案增加就继续选
-
(Goodbye) (2019) (E)
有(n)个点，请你把他们分成两个非空集合(A,B)，使得任意两个相同集合的点的欧几里得距离( ot=)任意两个不同的集合的点的欧几里得距离 >
(nle 1000) -
绝世好题(Bzoj4300)
给定一个长度为(n)的数列(a_i)，求(a_i)的子序列(b_i)的最长长度，满足(b_i&b_{i-1} ot=0(2le ile len))
(nle 100000)
法1：
(f_i)表示处理到当前数，第(i)位不为(0)的最优长度。转移很好转。（开始有一个误区：认为一定这个序列的所有数某一位都不为(0)，实际并不是，因为相邻两个数可以是不同位置使得&运算不为(0)）
法2：
(f_i=max{f_j+1}(a_i)和(a_j)第(k)位都是(1))
枚举(k)使(a_i)第(k)位是(1)，(f_i=max{f_j+1}(a_j)第(k)位是(1))
设(g_k=max{f_j+1})，在求完(f_j)之后更新一下所有的(g_k)即可，复杂度为(O(log_2a_i))
-
多组数据，求(sum_{i=x}^nsum_{j=y}^m[gcd(i,j)==k])
(T,n,m,x,yle 5cdot10^4)
使用二维前缀和( herefore)只需求(sum_{i=1}^nsum_{j=1}^m[gcd(i,j)==k])
即求(sum_{i=1}^{[frac{n}{k}]}sum_{j=1}^{[frac{m}{k}]}[gcd(i,j)==1])
又(sum_{d|n}mu(d)=[n==1])
( hereforembox{求}sum_{i=1}^{[frac{n}{k}]}sum_{j=1}^{[frac{m}{k}]}sum_{d|imbox且d|j}mu(d))
即求(sum_{d=1}^{min([frac{n}{k}],[frac{m}{k}])}sum_{d|i}^{ile[frac{n}{k}]}sum_{d|j}^{jle[frac{m}{k}]}mu(d))
( herefore sum_{d=1}^{min(...)}mu(d)sum_{i=1}^{[frac{n}{i}]div d}sum_{j+1}^{[frac{m}{k}div d]}1)
