二项式反演公式：
这个形式高度对称，它还有一个等价形式比较常用
错排公式
错排问题又称伯努利错装信封问题。这个问题有很多不同的题面，下面是其中一种
伯努利错装信封问题
有一个粗心的邮差让(n)封信从信封中掉了出来，但他并不知道每一封信对应着哪一个信封。不负责任的他随机地把信胡乱塞进信封里。问一共有多少种装信的方案使得信全部装进了不同的信封。
我们记错排数为({D_n}),表示将n封信全部装错方案数量，利用二项式公式可推得
第二类斯特林数
将(n)个不同的球放进(m)个不同的盒子，保证盒子非空，求方案数。
记(n)个不同的球放进(m)个不同的盒子里的方案总数为(Q^m_{n})
同样可以利用二项式反演公式可得
第二类斯特林数指的是将(n)个不同的球放进(m)个无差别的盒子，保证盒子非空，求方案数。
只要将有差别的(Q^m_n)除以盒子的排列数(m!)就是答案，即有第二类斯特林数(S^m_n):
性质
左边表示k个球任意放在n个盒子中，右边枚举非空盒子数量i,把k个球放在i个盒子中（盒子不同），里面再乘上选出i个非空盒子的方案数
贝尔数
定义
第n个贝尔数表示集合{1,2,3,...,n}的划分方案数
(B[0]=1)
性质
递推公式为(B_{n+1}=sum^n_{k=0}C^k_nB_k)
每个贝尔数都是第二类斯特林数的和
(B_n=sum^n_{k=1}S(n,k))
适合Touchard同余，对任意质数p
(B_{p+n}=B_n+B_{n+1}(mod ~~p))
贝尔数的指数母函数
(sum^{infty}_{n=0}frac{B_n}{n!}x^n=e^{e^x-1})
期望线性性
对于任意两个随机事件x,y(x,y不要求相互独立)满足
即两个（或多个）随机变量的和的期望等于期望的和
Min-Max容斥
给定集合(S)，设(max(S))为(S)中的最大值，(min(S))为(S)中的最小值，则我们有一个式子：
如果是k-thMax的话
裴蜀定理（或贝祖定理
(ax+by=c,xin Z^*,yin Z^*)成立的充分条件是({gcd(a,b)|c})
exgcd中会用到
费马小定理
若p为质数,且a,b互质那么(a^{p-1}equiv1(mod p))
那么(a^{p-1}(mod p)就是a在modm下的逆元了)
欧拉定理
当a,p互质时,(a^{varphi(p)}equiv1(mod p))
(a^b=a^{b~mod~phi(p)})
其中(varphi(p))是欧拉函数((1)~(p))与(p)互质的数
那么显然费马小定理就是欧拉定理的特殊情况
求逆元和上面同理
欧拉函数的一些性质
(varphi(1)=1)
对于素数p，(varphi(p)=p-1)
小于n并与n互质的数的和为：(n*varphi(n)/2)
欧拉定理：如果a与n互质，(a^{varphi(n)}mod~p=1~mod~p)
如果m与n互质，(varphi(mn)= varphi(m)*varphi(n))
如果p为素数，(varphi(p^k) = p^k - p^{k-1}= (p-1)*p^{k-1})(除p的倍数外，其他数都与p互质)
(sum_{d|n}varphi(d)=n)
拓展欧拉定理
若 (b<varphi(m)，a^bequiv a^b(mod m))
若 (b≥varphi(m)，a^bequiv a^{bmod varphi(m)+varphi(m)}(mod m))
欧拉降幂
(a^bequiv a^{b\%varphi(m)},gcd(b,m)=1)
(若b,m不互质)
若 (b<varphi(m)，a^bequiv a^b(mod m))
若 (b≥varphi(m)，a^bequiv a^{bmod varphi(m)+varphi(m)}(mod m))
霍尔定理内容
霍尔定理是判断二分图是否满足完美匹配的充要条件,要求(|X|=|Y|),其中(X)是左边的点数,(Y)是右边的点数，
对于任意的(|X|)的子集(a)都有(|a|leq|b|),其中(b)是(a)能匹配的点集的并，即对应(X)中的子集(W)，令(N(W))为(W)的能匹配的点集的并，有(|W|leq|N(W)|)
推论
两边点集为(X,Y),则二分图的最大匹配为(|X|-max{{|W|-|N(W)|}})，其中(W)是(X)的子集
欧拉公式
(e^{ix}=cosx+isinx)
阶（Order)
定义:
若(a,p)为正整数，且(gcd(a,p)=1),称满足(a^requiv1(mod~p))的最小正整数(r)为(a)模(p)的阶，记为(ord_p(a))
常用性质
1.若(a,p)为正整数，且(gcd(a,p)=1)，(r)为(a)模(p)的阶，若有正整数(m)满足(a^mequiv1(mod~p)),则(r|m)。
2.若(a,p)为正整数，且(gcd(a,p)=1)，(r)为(a)模(p)的阶,则(r|phi(p))。
3.若(a,p)为正整数，且(gcd(a,p)=1),(a^iequiv a^j(mod~p))当且仅当(iequiv j(mod~ord_p(a))).
原根（Primitive root）
定义：
若(a,p)为正整数，且(gcd(a,p)=1),称满足(ord_p(a)=phi(p))的叫做模(p)的一个原根。注意：不是任何(p)都存在原根。每个素数都存在原根。
常用性质：
1.当(a)为m的原根时，(a^0,a^1,a^2,....,a^{m-1})构成了(m)的一个简化剩余类。
2.模m有原根的充要条件是(m=2,4,p^n,2p^n),其中(p)为奇素数，(n)为任意正整数
求解原根
我们知道了上述阶的性质2，要判断某数是不是模(m)的原根，可以验证是否存在m-1的一个约数a满足(g^aequiv 1(mod~m))，如果有的话那么g的阶就不是(m-1)，则(g)不是模(m)的原根。一般来说原根不会很大，从2开始枚举并按照上述方法判断就可以得到。
拉格朗日插值法
公式:
(L(x)=sum^{k}_{j=0}y_jp(x))
(p_j(x)=prod^k_{i=0,i
eq j}frac{x-x_i}{x_j-x_i})
一个小性质
(a)与(b)互质,那么((a+b))和(a*b)互质
l cm与gcd的一些性质
(a={p_1} ^ {a_1} *{p_2} ^ {a_2} *..........*{p_n} ^ {a_n})
(b={p_1} ^ {b_1} *{p_2} ^ {b_2} *..........*{p_n} ^ {b_n})
(gcd(a,b)={p_1} ^{min(a_1,b_1)} * {p_2} ^ {min(a_2,b_2)} *..........*{p_n} ^ {min(a_n,b_n)})
(lcm(a,b)={p_1} ^ {max(a_1,b_1)} *{p_2} ^ {max(a_2,b_2)} *..........*{p_n} ^ {max(a_n,b_n)})
斯特林公式
(n!approxsqrt{2pi n}(frac{n}{e})^n)
一些计算几何的公式
三角形外接圆半径(R=frac{a}{2sinA}),由(S=frac{1}{2}bcsinA),(R=frac{abc}{4S})
海伦公式(S=sqrt{p(p-a)(p-b)(p-c)},p=frac{1}{2}(a+b+c))
莫比乌斯反演
(F(n)=sum_{d|n}f(d))
(f(n)=sum_{d|n}mu(d)F(lfloorfrac{n}{d}
floor))
(f(d)=sum_{d|n}mu{(frac{n}{d})}F(n))
莫比乌斯函数的一些性质
(sum_{d|n}mu(d)=[n=1])
(sum_{d|n}frac{mu(d)}{d}=frac{varphi(n)}{n}),这条性质将莫比乌斯函数和欧拉函数结合起来了
杜教筛的套路式
(g(1)S(n)=sum_{i=1}^{n}(f*g)(i)-sum_{d=2}^{n}g(d)cdot S(lfloorfrac{n}{d} floor))
二分图的一些定理
二分图的环只能是偶环
卡特兰数：
(f(n)=sum^{n-1}_{i=0}f(i)f(n-i-1) ,f(0)=f(1)=1)
变形：
(f(n)=C^n_{2n}-C^{n-1}_{2n})
卡特兰数的一些性质：
(C_n=frac{1}{n+1}C^n_{2n}=C^n_{2n}-C^{n-1}_{2n})
(C_n=frac{1}{n+1}sum^n_{i=0}(C^i_n)^2)
递推公式
(C_{n+1}=frac{2(2n+1)}{n+2}C_n,C_0=1)
(C_{n+1}=sum^i_{i=0}C_iC_{n-i},C_0=1)
关于勾股数
假设三个勾股数分别为(x,y,z(z>x,y))
如果(gcd(x,y,z)=1)
那么先假设(gcd(x,y)=g,g
eq1)
那么说明(x=k_1g,y=k_2g,z^2=(k_1^2+k_2^2)g^2,(k_1,k_2in N^+))
那么提出(g,z=sqrt{k_1^2+k^2_1}g)所以(gcd(x,y,z)=g)
所以要满足(gcd(x,y,z)=1)
必须要满足(gcd(x,y)=1)，即(x,y)互质
对于满足这种类型((x,y)互质)的勾股数
有一个通式:(x=m^2-n^2,y=2mn,z=m^2+n^2,(gcd(m,n)=1且m,n必须一奇一偶，否则不满足互质条件，但依然是勾股数))
威尔逊定理
当且仅当(p)为素数时：((p-1)!equiv-1(mod p))
最长反链=最小链覆盖数
链是一个点的集合，这个集合中任意两个元素v、u，要么v能走到u，要么u能走到v。
反链是一个点的集合，这个集合中任意两点谁也不能走到谁。
最长反链是反链中最长的那个。
最小链覆盖。就是用最少的链，经过所有的点至少一次
最长反链长度 = 最小链覆盖数
建立两个n个点的点集X和Y，如果原图中存在一条边A->B，就在X中的A向Y中的B连边，跑最大匹配答案是ans，那么最长反链长度是n-ans
二分图中最小点覆盖等于最大匹配数
最小点覆盖：实质是个点集，点集里面的点能覆盖所有的边，最小点覆盖就是满足这个要求的点集中点数最小的那个
关于网络流跑二分图的复杂度
是(nsqrt{n})的,乱算复杂度算错结果导致不敢写的情况还是别再有了
柯西—施瓦茨不等式
对欧几里得空间有
((sum^n_{i=1}x_iy_i)^2leqslant(sum^n_{i=1}x_i^2)(sum^n_{i=1}y_i^2))
对于平方可积的复值函数，有
([int^a_b f(x)g(x)dx]^2leqslant int^a_b f^2(x)dxint^a_bg^2(x)dx)
Betty定理
如果两个无理数(a,b)满足
(frac{1}{a}+frac{1}{b}=1)
那么对于两个集合A,B
(A={ {lfloor na
floor}},B={ {lfloor nb
floor}},nin{Z})
有两个结论：
(Aigcap B=varnothing)
(Aigcup B=N^+)
类似整数划分的问题可以用该定理解决，如威佐夫博弈即可用此定理解决
算术基本定理
一个大于1的正整数(N)，如果标准分解式为(N=P^{a_1}_1P^{a_2}_2P^{a_3}_3cdots P^{a_n}_n(表示质因数分解))
那么他的正因数个数为((1+a_1)(1+a_2)cdots (1+a_n))
他的全体正因数之和为((1+p_1+p^2_1+cdots+p_1^{a_1})(1+p_2+p^2_2+cdots+p_2^{a_2})cdots(1+p_n+p^2_n+cdots+p_n^{a_n}))