\(\color{red}{（一）组合数学}\)
排列组合
排列
从\(n\)个不同的元素中取出\(m\)个的方案数，记为\(A(n,m)\)或\(P(n,m)\)
\[P(n,m)=\frac{n!}{(n-m)!}\]组合
从\(n\)个相同的元素中取出\(m\)个的方案数，记为\(C(n,m)\)
\[C(n,m)=\frac{n!}{m!(n-m)!}\]\[C(n,m)=C(n-1,m)+C(n-1,m-1)\]隔板法
用\(m-1\)个相同隔板把\(n\)个相同元素分成\(m\)部分或在\(n\)个相同元素所形成的\(n+1\)个空隙中插入\(m\)个相同隔板（可以有两个隔板插在同一个空隙）
方案数：\[C(n+m-1,m-1)=C(n+m-1,n)\]卡特兰数
一个序列有n个0和n个1，保证每个1之前必有1个0的方案数为C(n)
递推式：（注意：括号里只有一个元素的是Catalan数，有两个元素的是组合数）\[C(n)=C(0)*C(n-1)+C(1)*C(n-2)+...+C(n-1)*C(0)\]\[C(n)=C(n-1)*(4*n-2)/(n+1)\]\[C(n)=C(2n,n)/(n+1)\]\[C(n)=C(2n,n)-C(2n,n-1)\]
第一类斯特林数
把\(n\)个元素摆成\(m\)个圆排列的方案数，记为\[s(n,m)\]
递推式：\[s(n,m)=s(n-1,m-1)+(n-1)*s(n-1,m)\]第二类斯特林数
把\(n\)不同的球放在\(m\)个相同的盒子（无空盒）里的方案数，记为\[S(n,m)\]
递推式：\[S(n,m)=S(n-1,m-1)+m*S(n-1,m)\]母函数
引入：砝码称重问题
有1g砝码5个，2g砝码3个，5g砝码2个。相同质量的砝码完全相同。问有多少种能称出15g的方案？
解：
很容易想到暴力枚举每一种可能的称量方案，但是时间复杂度为\(O(n^n)\)级别，计算机无法承受。于是我们引入母函数的概念。设\(G(x)\)为母函数，对于1g的砝码能称出的不同重量，我们用多项式表示为\[(x^1+x^2+...+x^{15})\]同理，2g砝码能表示为\[(x^2+x^4+...+x^{14})\]5g砝码能表示为\[(x^5+x^{10}+x^{15})\] 于是\[G(x)=(x^1+x^2+...+x^{15})(x^2+x^4+...+x^{14})(x^5+x^{10}+x^{15})\] 经过化简，求出\(x^{15}\)的系数，即为答案。由于只需化简多项式，母函数的时间复杂度仅为\(O(n^3)\)，空间复杂度为\(O(n)\)，得到巨大提升。
错位排列
递推式：\[f[n]=(n-1)\times (f[n-1]+f[n-2])\]
证明：- \(n-1\) 个人已经完成错排，第 \(n\) 个人和任意一个人交换
- \(n-2\) 个人已经完成错排，第 \(n\) 个人和第 \(n-1\) 个人交换
经典的放球问题
为方便表达，我们设方案数为\(N\)，\(n\)个球，\(m\)个盒
1. 球不同，盒不同，有空盒
\[N=m^n\]
根据乘法原理可得。2. 球不同，盒不同，无空盒
(1) \(n>=m\)
\[N=m!*S(n,m)\] 球不同，盒相同的方案数\(\times m!\)(2) \(n<m\)
\[N=0\]3. 球不同，盒同，有空盒
\[N=S(n,1)+S(n,2)+...+S(n,m)\]
因为允许空盒，所以球可以只放在\(m\)个盒中的\(1\)个或\(2\)个或...或\(m-1\)个盒中4. 球不同，盒同，无空盒
(1) \(n>=m\)
\[N=S(n,m)\] 由第二类斯特林数的定义。(2) \(n<m\)
\[N=0\]5. 球同，盒不同，有空盒
\[N=C(m+n-1,n)\]
插板法，即把\(n\)个球用\(m-1\)个隔板分成\(m\)部分。6. 球同，盒不同，无空盒
(1) \(n>=m\)
\[N=C(n-1,m-1)\] 先在每个盒子里放一个球，方案数为\(1\)；再对剩下的\(n-m\)个球用隔板法，即把\(n-m\)个球用\(m-1\)个隔板分成\(m\)部分。(2) \(n<m\)
\[N=0\]7. 球同，盒同，有空盒
(1) \(n>=m\)
我们发现，当\(n=5,m=3\)时的方案为：
5 0 0
4 1 0
3 2 0
3 1 1
2 2 1
共\(5\)种方案。
我们发现，问题可以转化为：把正整数\(n\)分解成不超过\(m\)个自然数的方案数。如果暴力dfs，时间复杂度为\(O(\)爆炸\()\)。竟然还有70分
有一个重要结论：把正整数\(n\)分解成不超过\(m\)个自然数的方案数，等于把正整数\(n\)分解成若干个\(\le m\)的自然数的方案数。这个定理的证明方法，请自行百度。（我也不会）
我们考虑使用母函数：对于分解出的每个\(\le m\)的整数\(i\)，我们用多项式表示为\[(x^i+x^{2i}+...+x^{floor(\frac{n}{i})*i})\]
此处\(floor(x)\)表示\(x\)向下取整。
于是，母函数\(G(x)\)：\[G(x)=\sum_{i=1}^{m}(x^i+x^{2i}+...+x^{floor(\frac{n}{i})*i})\]
求出\(x^n\)的系数即可。
(2) \(n<m\)
\[\color{white}???\]
8. 球同，盒同，无空盒
(1) \(n>=m\)
母函数\[G(x)=\sum_{i=1}^{m}(x^i+x^{2i}+...+x^{floor(\frac{n}{i})*i})\]
中\(x^{n-m}\)的系数。
(2) \(n<m\)
\[N=0\]\(\color{red}{（二）数论}\)
gcd and lcm
Code
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}int lcm(int a,int b){return a/gcd(a,b)*b;} gcd的几条性质
\[\gcd(x^a-1,x^b-1)=x^{\gcd(a,b)}-1\]
证明：\(\gcd(x^a-1,x^b-1)\)\(=\gcd(x^b-1,x^a-x^b)\)\(=\gcd(x^b-1,x^b(x^{a-b}-1))\)\(=\gcd(x^b-1,x^{a-b}-1)\)\[\gcd(fib[i],fib[j])=fib[\gcd(i,j)]\] （ \(fib[]\) 为广义斐波那契数列）
证明：\(\gcd(fib[i+j],fib[j])\)\(=\gcd(fib[j],fib[i+j]-fib[j])\)\(=\gcd(fib[j],fib[i-1]*fib[j]+fib[i]*fib[j+1]-fib[j])\)\(=\gcd(fib[j],fib[i]*fib[j+1])\)\(=\gcd(fib[j],fib[i])\)线性筛
int pr[maxn],tot;bool check[maxn];void init(int n){ check[1]=1; for(int i=2;i<=n;i++){ if(!check[i]){ pr[++tot]=i; } for(int j=1;j<=tot&&i*pr[j]<=n;j++){ check[i*pr[j]]=1; if(i%pr[j]==0)break; } }} 理论上来讲 \(n\) 以内的质数个数大约在 \(n/\ln(n)\) 个左右
欧拉函数
定义
欧拉函数 \(φ(n)\) 是小于或等于 \(n\) 的正整数中与 \(n\) 互质的数的数目。
性质
\[φ(p)=p-1(p\;is\;prime)\]
显然，除了它本身以外的数都和该质数互质。
\[φ(p^k)=p^k-p^{k-1}(p\;is\;prime)\]
与 \(p^k\) 不互质的数就是 \(p\) 的倍数，有 \(\frac{p^k}{p}=p^{k-1}\) 个。
\[φ(a*b)=φ(a)*φ(b)(\gcd(a,b)=1)\]
设 \(S_x=\{\) 所有与 \(x\) 互质且 \(\le x\) 的数 \(\}\) 。显然 \(|S_x|=φ(x)\) 。
\(\because \gcd(a,b)=1,\)\(\therefore S_{a*b}\) 与 \(S_a,S_b\) 一一对应。\(\therefore |S_{a*b}|=|S_a|*|S_b|,\) 即 \(φ(a*b)=φ(a)*φ(b)\)\[φ(2*n)=φ(n)(n\% 2=1)\]
\(φ(2)=1\) ，易证。
\[φ(n)=φ(\frac{n}{p})*p(p|\frac{n}{p})\]
\(φ(\frac{n}{p})=\frac{n}{p}*\Pi (1-\frac{1}{p_i})\)
\(φ(n)=p*\frac{n}{p}*\Pi (1-\frac{1}{p_i})=p*φ(\frac{n}{p})\)\[φ(n)=φ(\frac{n}{p})*(p-1)(p\;is\;prime,\gcd(n,p)=1)\]
\(φ(p)=p-1\) ，易证。
\[\sum_{d|n}φ(d)=n\]
设 \(f(n)=\sum_{d|n}φ(d)\)
当 \(\gcd(x,y)=1\) 时， \(f(x)*f(y)=x\Pi_{p_i是x的质因子}(1-\frac{1}{p_i})*y\Pi_{p_i是y的质因子}(1-\frac{1}{p_i})=x*y\Pi_{p_i是x*y的质因子}(1-\frac{1}{p_i})=f(x*y)\)\(\therefore f(n)\) 是积性函数。\(f(p^k)=\sum_{i=0}^k φ(p^i)=p^k\) 于是我们把 \(n\) 分解质因数：\(n=\Pi p_i^{k_i}\)\(f(n)=\Pi f(p_i^{k_i})=\Pi p_i^{k_i}=n\)公式
\(φ(x)=x\Pi (1-\frac{1}{p_i})\)
\(p_i\) 为 \(x\) 的第 \(i\) 个质因子， \(x≥2\) 。 \(φ(1)=1\) 。 根据唯一分解定理， \(x=\Pi p_i^{k_i}\) 。\(\therefore φ(x)=\Pi φ(p_i^{k_i})=\Pi (p_i^{k_i}-p_i^{k_i-1})=x\Pi (1-\frac{1}{p_i})\)欧拉定理
\[a^{φ(n)}≡1(\% n)(\gcd(a,n)=1)\]
设 \(S=\{x_1,x_2,...,x_{φ(n)}\}\) 为所有与 \(n\) 互质且 \(\le n\) 的数。
显然 \(x_i≡x_j(i≠j)(\% n)\) 不成立。 再设 \(T=\{a*x_1,a*x_2,...,a*x_{φ(n)}\}\)\(\because \gcd(a,n)=1\)\(\therefore a*x_i≡a*x_j(i≠j)(\% n)\) 不成立\(\therefore S=T\)\(\therefore \Pi_{i=1}^{φ(n)}a*x_i≡\Pi_{i=1}^{φ(n)}x_i(\% n)\)\(\therefore a^{φ(n)}≡1(\% n)\)费马小定理
\(a^{p-1}≡1(\% p)(p\;is\;prime)\)
Code
\(O(n)\) 求 \(1-n\) 的欧拉函数
void init(int n){ phi[1]=1; for(int i=2;i<=n;i++){ if(!check[i]){ pr[++tot]=i; phi[i]=i-1; } for(int j=1;j<=tot&&i*pr[j]<=n;j++){ check[i*pr[j]]=1; if(i%pr[j]==0){ phi[i*pr[j]]=phi[i]*pr[j]; break; } else phi[i*pr[j]]=phi[i]*phi[pr[j]]; } }} \(O(\sqrt{n})\) 求 \(n\) 的欧拉函数
int phi(int n){ int x=n,ret=n; for(int i=2;i*i<=n&&x>1;i++){ if(x%i==0){ ret=ret/i*(i-1); while(x%i==0)x/=i; } } if(x>1)ret=ret/x*(x-1); return ret;} 逆元
逆元的引入
在做组合数取模的时候，常常要求\((a/b)\%p^{[1]}\)，然而不同于加减乘，除法取模没有\((a/b)\%p=(a\%p/b\%p)\%p\)的性质。因此，我们引入乘法逆元的概念。
若\(a* b≡1(\%p)\)，则设\(b=inv(a)\)，称\(b\)是\(a\)的逆元，满足\((a* b)\%p=(a\%p* b\%p)\%p\)。这样，除法转换为乘法，就可以了。但前提是对于两个整数\(A,B\)，要计算\(A/B\)时，\(A\)必须能够被\(B\)整除。
对于两个取模过的数，逆元是怎么输出商的？它实际上是在对给定的取模过的数\(a,b\)，找最小的两个\(A,B\)，满足\(A=x* p+a,B=y* p+b,A\%B=0\)，并返回\(A/B\)。
求逆元的几种常用方法
1. 扩展欧几里得
欧几里得定理
想必都知道\[gcd(a,b)=gcd(b,a\%b)\]
解关于\(x,y\)的方程\(ax+by=gcd(a,b)\)
首先，我们先解出方程的一个特解，再通过特解推出其余的通解即可。
如何求特解
我们来看下面两个方程：
\[ax_1+by_1=gcd(a,b)\]\[bx_2+(a\%b)y_2=gcd(b,a\%b)\]\(\because gcd(a,b)=gcd(b,a\%b),\)\(\therefore ax_1+by_1=bx_2+(a\%b)y_2\)
\(\because a\%b=a-floor(a/b)* b^{[2]}\)
\(\therefore ax_1+by_1=ay_2+b(x_2-floor(a/b)* y_2)\)
由等式两边的系数关系得\[x_1=y_2\]\[y_1=x_2-floor(a/b)* y_2\]
于是形成了一种递归关系，可用递归解决。递归终止状态
我们知道在计算最大公约数的过程中，\(b\)最终会等于\(0\)，此时\(a=gcd(A,B)\)，因此，这时方程化为\(a* x=gcd(A,B)\)，解得\(x=1,y=0\)。
如何求通解
求得一组特解之后，我们发现，对于方程\(ax+by=gcd(a,b)\)，当\(x\)增加\(b/gcd\)，\(y\)减少\(a/gcd\)时，等式仍成立。
证明
\(ax\)项增加\(a* b/gcd\)，\(by\)项减少\(a* b/gcd\)。
于是可求得所有通解。
如何求最小非负整数解
此处以\(x\)为例，\(y\)同理。我们让\(x\)一直减\(B/gcd\)直至求出最小解，即让\(x\%(B/gcd)\)即可。
解关于\(x,y\)的方程\(Ax+By=C\)
我们发现，当\(C\)不能整除\(gcd(A,B)\)时，方程就不能化为\(ax+by=gcd(a,b)\)的形式，因此就无解。否则有无数解，将方程两边同时除以\(gcd(A,B)\)求解即可。
Code
typedef long long D;D egcd(D a,D b,D &x,D &y){ if(b==0){ x=1; y=0; return a; } D ans=egcd(b,a%b,x,y),tmp=x; x=y; y=tmp-a/b*y; return ans;}D cal(D a,D b,D c){ D x,y,g=egcd(a,b,x,y); if(c%g!=0)return -1; b=abs(b/g); x=(x*(c/g)%b+b)%b; return x;} 利用扩展欧几里得求乘法逆元
因为\[a* x≡1(\%p)\]
所以\[a* x+b* y=1\] 此时，若\(1\%gcd(a,b)≠1\)，即\(gcd(a,b)≠1\)，则该方程无解。 否则，设特解为\(x_0\)，最小非负整数解\(x=x_0\%m\)。当\(m<0\)时，由于计算机取模一个负数与数学上的意义不同，所以应把模数取绝对值。当\(x_0<0\)时，取模的结果是一个负数，所以把答案加上\(m\)即可。复杂度为\(\log\)级。
Code
typedef long long D;D egcd(D a,D b,D &x,D &y){ if(b==0){ x=1; y=0; return a; } D ans=egcd(b,a%b,x,y),tmp=x; x=y; y=tmp-a/b*y; return ans;}D cal(D a,D m){ D x,y,g=egcd(a,m,x,y); if(g!=1)return -1; m=abs(m/g); x=(x%m+m)%m; return x;} 2. 利用费马小定理
当\(p\)为质数时， \(a^{p-1}≡1(\%p)\) ，对\(a* x≡1(\%p)\)有\(x=a^{p-2}\%p\)。
复杂度为\(\log\)级。
Code
typedef long long D;D qpow(D x,D y,D p){ D ans=1; while(y){ if(y&1)ans=ans*x%p; x=x*x%p; y>>=1; } return ans;}D cal(D a,D p){ return qpow(a,p-2,p);} 组合数取模
由于题目中给的\(p\)一般都是质数，所以下面我们默认\(p\)为质数。
1. 错误方法
由上面的结论，我们得出\[C(n,m)=\frac{n!}{m!(n-m)!}=n!* inv(m!)* inv((n-m)!)\]
此方法的错误之处在于，对\(a* x≡1(\%p),a\)有逆元的前提条件时\(a,p\)互质。当\(a,p\)不互质，即\(a\)是\(p\)的倍数时，不存在逆元，也就无法计算。
比如计算\(C(7,5)\%5\)，正确答案应该是\(\frac{7* 6}{1* 2}\%5=21\%5=1\)，但计算过程中出现了\(5\)的倍数，取模\(5\)之后就变为\(0\)，因此最后答案输出了\(0\)。
2. lucas定理
lucas定理可避免上述情况。
递归式：
设\(lucas(n,m,p)\)为\(C(n,m)\%p\)（\(p\)为质数），则
\[lucas(n,m,p)=C(n\%p,m\%p,p)* lucas(n/p,m/p,p)\] 此处的\(C(n,m,p)\)可直接通过逆元计算。复杂度为\(\log\)级。
Code
typedef long long D;D fac[100001];void preparefac(D n,D p){ fac[0]=1; for(D i=1;i<=n;i++){ fac[i]=i*fac[i-1]%p; }}D qpow(D x,D y,D p){ D ans=1; while(y>0){ if(y%2)ans=ans*x%p; x=x*x%p; y/=2; } return ans;}D cal(D x,D y){ return qpow(x,y-2,y);}D Div(D x,D y,D p){ return x*cal(y,p)%p;}D C_(D n,D m,D p){ if(m>n)return 0; return Div(Div(fac[n],fac[m],p),fac[n-m],p);}D C(D n,D m,D p){ if(!m)return 1; return C_(n%p,m%p,p)*C(n/p,m/p,p)%p;} 线性递推求逆元
首先 \(1^{-1}≡1(\%p)\)
设 \(p=k* i+r\) 则 \(k* i+r≡0(\%p)\) 等式两边乘 \(i^{-1}* r^{-1}\) 得 \(k* r^{-1}+i^{-1}≡0(\%p)\)\(\therefore i^{-1}≡-k* r^{-1}(\%p)\)\(\therefore i^{-1}≡-floor(\frac{p}{i})* (p\%i)^{-1}(\%p)\)Code
inv[1]=1;inv[i]=(p-p/i)*inv[p%i]%p;
阶乘逆元
\(i\) 的阶乘逆元等于 \(i-1\) 的阶乘逆元乘以 \(i\) 的逆元。
Code
facinv[i]=facinv[i-1]*inv[i]%p;