初等数论及组合数学入门复习概览

ReeChee · 2023-02-14 20:26:45 · 个人记录

同步于 博客园 和 洛谷博客。

由于各网站之间 \LaTeX 及 Markdown 渲染方式的差异，故不保证除博客园外的排版完好，对于排版有明显不正确的地方请以博客园为主。

质数

定义：无法被任何除了 1 及其本身的自然数整除的数。

性质：

判断质数

1. 试除法：

时间复杂度 \mathcal{O}(\sqrt{n})。

bool isPrime(int n){
    if (n<2) return 0;
    int k=sqrt(n);
    F(i,2,k)
        if (!(n%i)) return 0;
    return 1;
}

质数筛

1. 埃氏筛：

对于每个整数，显然其倍数都不是质数。

扫描所有数，每扫到一个没被标记的数，该数即为质数，随后标记该数的倍数为约数。

同时，对于当前的质数 x，因为小于 x^2 的 x 的倍数已经被小于 x 的质数扫描过了，因此只需要从 x^2 开始扫描倍数即可。

时间复杂度 \mathcal{O}(n\log \log n)。

bool vis[N];
void EratosthenesSeive(int n){
    F(i,2,n){
        if (vis[i]) continue;
        F(j,i,n/i) vis[i*j]=1;
    }
    return ;
}

2. 线性筛（欧拉筛）：

埃氏筛依旧会重复标记某些合数，考虑使合数被唯一标记。

设 v_i 为 i 的最小质因子，从前到后扫描所有数，若 v_i=0 则 i 为质数，使 v_i=i 并将 i 加入到质数集 \text{Prime}。

对于每个数，扫描质数集的所有数 x，若 x 相比 v_i 不是最小的质因子或 i\times x 超出筛的范围则终止扫描，反之则 v_{i\times x}=x。

时间复杂度 \mathcal{O}(n)。

vector<int> prime;
int v[N];
void EulerSeive(int n){
    F(i,2,n){
        if (!v[i]) v[i]=i,prime.push_back(i);
        V(x,prime){
            if (x>v[i]||i*x>n) break;
            v[i*x]=x;
        }
    }
    return ;
}

质因数分解

前置知识：

1. 唯一分解定理：任意一个大于 1 的正整数 n 都可被唯一分解为若干个质数的乘积，即 n=p_1^{c_1}p_2^{c_2}\dots p_k^{c_k}，其中 c_i 为正整数，p_i 为质数且 p_1 < p_2 < \dots < p_k。

int p[N],c[N],tot;
void Divide(int n){
    int k=sqrt(n);
    F(i,2,k){
        if(!(n%i)){
            p[++tot]=i,c[tot]=0;
            while(!(n%i)) ++c[tot],n/=i;
        }
    }
    if (n>1) p[++tot]=n,c[tot]=1;
    return ;
}

约数

定义：若 n\bmod d=0，则称 d 为 n 的约数，记作 d\mid n，读作 d 整除 n。

求单个值的正约数集合

1. 试除法：

因为若 d 为 n 的约数，则 \frac{n}{d} 也为 n 的约数，所以除完全平方数的 \sqrt n 之外，约数总是成对出现的。

故从 1\sim \sqrt n 判断 i 是否整除 n 即可，若整除且 i\neq \frac{n}{i} 则 \frac{n}{i} 也为约数。

推论：一个整数 n 至多有 2\sqrt n 个约数。

时间复杂度 \mathcal{O}(\sqrt n)。

vector<int> fac;
void FactorDivision(int n){
    int k=sqrt(n);
    F(i,1,k){
        if (!(n%i)){
            fac.push_back(i);
            if (i!=n/i) fac.push_back(n/i);
        }
    }
    return ;
}

求区间内的正约数集合

1. 暴力+试除法：

时间复杂度 \mathcal{O}(n\sqrt n)，代码见求单个值的正约数集合。

2. 倍数法：

反过来考虑，运用埃氏筛的倍数标记思想，对于每个数 d，d 肯定为其的倍数的约数，故对于每个数，将这个数加入到这个数的倍数的正约数集合里。

时间复杂度 \mathcal{O}(n\log n)。

vector<int> fac[N];
void FactorDivision(int n){
    F(i,1,n)
        F(j,1,n/i)
            fac[i*j].push_back(i);
    return ;
}

数论分块

例题：给定正整数 n，求 \sum_{i=1}^{n}\lfloor \frac{n}{i} \rfloor，其中 1\leq n\leq 10^9。

显然 \frac{n}{i} 在连续的区间内值相等，故可以分成若干块再进行计算。

对于每个块，设 l 为该块的左边界，那么这个块的值为 k=\lfloor \frac{n}{l} \rfloor，那么右边界 r 即为最大的 i，且满足 i\leq \frac{n}{k}，故 r=\lfloor \frac{n}{k} \rfloor，代入 k 得 r=\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor。

时间复杂度 \mathcal{O}(\sqrt n)。

int mathBlock(int n){
    int l=1,r,ans=0;
    while(l<=n){
        r=n/(n/l);
        ans+=(n/l)*(r-l+1);
        l=r+1;
    }
    return ans;
}

题目：

• [AHOI2005]约数研究
• 约数和

最大公约数 最小公倍数

前置知识：

1. 公约数：若 x\mid a 且 x\mid b，则称 x 为 a 和 b 的公约数。

2. 公倍数：若 a\mid x 且 b\mid x，则称 x 为 a 和 b 的公倍数。

显然最大公约数就是公约数中最大的数字，最小公倍数就是公倍数中最小的数字。

求最大公约数

1. 欧几里得算法：

设 a > b 且 a=bk+c，则有 c=a\bmod b。 设 d\mid a,d\mid b，则有：

\begin{aligned} c=a-bk\\ \frac{c}{d}=\frac{a}{d}-\frac{b}{d}k \end{aligned}

由对 d 的定义可知 d\mid c，故 \gcd(a,b)=\gcd(b,a\bmod b)，得证。

时间复杂度 \mathcal{O}(\log n)。

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

2. 更相减损术：

当 a=b 时，显然 \gcd(a,b)=a=b。 设 a\geq b，那么 \forall d\mid a,d\mid b 有 d\mid a-b。 故 a 和 b 的所有公约数都为 a-b 和 b 的公约数，\gcd(a,b)=\gcd(a-b,b)，得证。

时间复杂度 \mathcal{O}(\max(a,b))。

int gcd(int a,int b){
    while(a!=b){
        if (a>b) a-=b;
        else b-=a;
    }
    return a;
}

3. 更相减损术优化：

若 2\mid a 且 2\mid b，则 \gcd(a,b)=2\gcd(\frac{a}{2},\frac{b}{2})。

反之，则若 2\mid a 且 2\nmid b，则 \gcd(a,b)=\gcd(\frac{a}{2},b)。

当 2\nmid a,2\mid b 时同理。

时间复杂度 \mathcal{O}(\log n)。

int gcd(int a,int b){
    int aa=0,bb=0;
    while(!(a&1)) a>>=1,++aa;
    while(!(b&1)) b>>=1,++bb;
    while(1){
        while(!(a&1)) a>>=1;
        while(!(b&1)) b>>=1;
        if (a==b) break;
        if (a<b) swap(a,b);
        a-=b;
    }
    return a<<min(aa,bb);
}

求最小公倍数

由唯一分解定理，可使 a=p_1^{c_{a_1}}p_2^{c_{a_2}}\dots p_k^{c_{a_k}},b=p_1^{c_{b_1}}p_2^{c_{b_2}}\dots p_k^{c_{b_k}}。 则最大公约数为 p_1^{\min(c_{a_1},c_{b_1})}p_2^{\min(c_{a_2},c_{b_2})}\dots p_k^{\min(c_{a_k},c_{b_k})}，最小公倍数为 p_1^{\max(c_{a_1},c_{b_1})}p_2^{\max(c_{a_2},c_{b_2})}\dots p_k^{\max(c_{a_k},c_{b_k})}。 由于 \min(c_a,c_b)+\max(c_a,c_b)=c_a+c_b，所以 \gcd(a,b)\times \operatorname{lcm}(a,b)=a\times b，得证。

时间复杂度为求最大公约数的时间复杂度。

int lcm(int a,int b){
    // 先除后乘可防止爆 int。
    return a/gcd(a,b)*b;
}

欧拉函数

前置知识：

1. 互质：\forall x,y\in \mathbb{N}，若 \gcd(x,y)=1，则称 x 和 y 互质，记作 x\perp y。

2. 积性函数：若 x,y 互质且 f(x)\times f(y)=f(xy)，则称函数 f 为积性函数。

3. 完全积性函数：若 \forall x,y\in \mathbb{R}，f(x)\times f(y)=f(xy)，则称 f 为完全积性函数。

定义：\forall n>1，\sum_{i=1}^{n}[i\perp n]，记作 \varphi(n)，特别地，\varphi(1)=1。

性质：

1. 若 n 为质数，则 \varphi(n)=n-1。

\because \gcd(n,x)=\gcd(n,n-x) $\therefore$ 与 $n$ 互质的数的平均值为 $\frac{n}{2}$，而与 $n$ 互质的数有 $\varphi(n)$ 个，得证。

4. 若 n=p^k，且 p 为质数，则 \varphi(n)=(p-1)\times p^{k-1}。

根据唯一分解定理，可知 n 与 p 的倍数都不互质，与其它数均互质。

5. 若 p 为质数，且 p 为 n 的约数，则 \varphi(np)=\varphi(n)\times p。

因为 p 为质数，所以 np 和 n 的质因子相同，仅 p 的指数不同，故（计算公式见求单个值的欧拉函数）：

\frac{\varphi(np)}{\varphi{(n)}}=\frac{np\times\prod_{i=1}^{k}(1-\frac{1}{p_i})}{n\times \prod_{i=1}^{k}(1-\frac{1}{p_i})}=\frac{np}{n}=p

所以 \varphi(np)=\varphi(n)\times p，得证。

6. 若 p 为质数且 p 不为 n 的约数，则 \varphi(np)=\varphi(n)\times (p-1)。

因为 p 不为 n 的约数，所以 p\perp n。 故 \varphi(np)=\varphi(n)\times \varphi(p)=\varphi(n)\times (p-1)，得证。

7. \sum_{d\mid n}\varphi(d)=n

设 f(x)=\sum_{d\mid n}\varphi(d)，因为 \varphi 为积性函数，所以若 a,b 互质，则 f(ab)=\sum_{d\mid ab}\varphi(d)=(\sum_{d\mid a}\varphi(d))\times (\sum_{d\mid b}\varphi(d))，所以 f 为积性函数。 对于一个质因子 p^k，f(p^k)=\sum_{d\mid p^k}\varphi(d)=\varphi(1)+\varphi(p)+\dots+\varphi(p^k)，结果为等比数列求和加 1，结果为 p^k。 故 f(n)=\prod_{i=1}^{k}f(p_i^{c_i})=\prod_{i=1}^{k}p_i^{c_i}=n，得证。

求单个值的欧拉函数

通过唯一分解定理，使 n=p_1^{c_1}\times p_2^{c_2}\times \dots \times p_k^{c_k}，则：

对于 n 的所有质因子 p_i，在 1\sim n 范围内 p_i 的倍数有 \frac{n}{p_i} 个。 那么对于 n 的两个质因子 p,q，根据容斥，1\sim n 范围内含质因子 p 或 q 的数的个数为 \frac{n}{p}+\frac{n}{q}-\frac{n}{pq}。 不含质因子 p 或 q 的数的个数为 n-\frac{n}{p}-\frac{n}{q}+\frac{n}{pq}=n\times (1-\frac{1}{p}-\frac{1}{q}+\frac{1}{pq})=n(1-\frac{1}{p})(1-\frac{1}{q})，将公式扩展到所有质因子 p_i 即可得证。

故在分解质因数时即可求出 \varphi，时间复杂度 \mathcal O(\sqrt n)。

int Phi(int n){
    int ans=n,k=sqrt(n);
    F(i,2,k){
        if (!(n%i)){
            ans=ans/i*(i-1);
            while (!(n%i)) n/=i;
        }
    }
    if (n>1) ans=ans/n*(n-1);
    return ans;
}

求区间内的欧拉函数

1. 暴力：

代码见求单个数的欧拉函数，时间复杂度 \mathcal O(n\sqrt n)。

2. 埃氏筛：

时间复杂度 \mathcal O(n\log n)。

int phi[N];
void CalculatePhi(int n){
    F(i,1,n) phi[i]=i;
    F(i,2,n){
        if (phi[i]==i)
            for (int j=i;j<=n;j+=i)
                phi[j]=phi[j]/i*(i+1);
    }
    return ;
}

3. 线性筛：

时间复杂度 \mathcal O(n)。

int phi[N],v[N];
vector<int> prime;
void CalculatePhi(int n){
    phi[1]=1;
    F(i,2,n){
        if (!v[i])
            v[i]=i,phi[i]=i-1,prime.push_back(i);
        V(x,prime){
            if (x>v[i]||i*x>n) break;
            v[i*x]=x;
            phi[i*x]=phi[i]*(i%x?x-1:x);
        }
    }
    return ;
}

题目：

• GCD SUM
• [SDOI2008] 仪仗队

莫比乌斯函数

定义：若根据唯一分解定理使正整数 n=p_1^{c_1}p_2^{c_2}\dots p_k^{c_k}，则有：

特别地，\mu(1)=1。

求单个值的莫比乌斯函数

1. 质因数分解：

时间复杂度 \mathcal{O}(\sqrt n)。

int Mobius(int n){
    if (n==1) return 1;
    int k=sqrt(n),cnt=0;
    F(i,2,k){
        if (!(n%i)){
            int ci=0;
            while(!(n/i)) n/=i,++ci;
            if (ci>1) return 0;
            ++cnt;
        }
    }
    if (n>1) ++cnt;
    return cnt&1?-1:1;
}

求区间内的莫比乌斯函数

1. 埃氏筛：

先初始化 \forall i\in [1,n],\mu(i)=1，显然对于质数 n 有 \mu(n)=-1，对于 n 的倍数，若 n^2\mid kn，则说明出现了 c_i > 1 的情况，\mu(kn)=0，反之则 \mu(kn)=-\mu(kn)。

时间复杂度 \mathcal{O}(n\log \log n)。

int mu[N];
bool vis[N];
void Mobius(int n){
    fill(mu+1,mu+1+n,1);
    F(i,2,n){
        if (vis[i]) continue;
        mu[i]=-1;
        for (int j=(i<<1);j<=n;j+=i){
            v[j]=1;
            if (!((j/i)%i)) mu[i]=0;
            else mu[i]*=-1;
        }
    }
    return ;
}

2. 线性筛：

对于质数 n 及每一个被遍历到的合数 n\times v_i，若其出现 c_i > 1，则停止遍历，否则 \mu(n\times v_i)=-\mu(n)。

时间复杂度 \mathcal{O}(n)。

vector<int> prime;
int mu[N];
bool vis[N];
void Mobius(int n){
    mu[1]=1;
    F(i,2,n){
        if (!vis[i]) vis[i]=1,mu[i]=-1,prime.push_back(i);
        V(x,prime){
            if (i*x>n) break;
            vis[i*x]=1;
            if (!(i%x)) break;
            mu[i*x]=-mu[i];
        }
    }
    return ;
}

同余

前置知识：

1. 取模的定义式：

定义：若 x\bmod p=y\bmod p，则称 x,y 模 p 同余，记作 x\equiv y\pmod p。

性质：

1. 自反性：x\equiv x\pmod p。

2. 对称性：若 x\equiv y\pmod p，则 y\equiv x\pmod p。

3. 传递性：若 x\equiv y\pmod p 且 y\equiv z\pmod p，则 x\equiv z\pmod p。

4. 同余式相加性：若 x\equiv y\pmod p 且 a\equiv b\pmod p，则 (x\pm a)\equiv (y\pm b)\pmod p。

5. 同余式相乘性：若 x\equiv y\pmod p 且 a\equiv b\pmod p，则 ax\equiv by\pmod p。

乘法逆元

前置知识：

1. 费马小定理：若 p 为质数且 a\perp p，则 a^p\equiv a\pmod p。

定义：若 a\perp p 且 x 为 ax\equiv 1\pmod p 的解，则称 x 为 a 模 p 的乘法逆元，记作 a^{-1}\pmod p。

求单个值的乘法逆元

若 a\not \perp p，则不存在 a 模 p 的乘法逆元。

1. 快速幂：若 p 为质数，且 a\perp p，根据费马小定理，可知 a 模 p 的乘法逆元为 a^{p-2}\bmod p。

由费马小定理可知 a^{p-1}\equiv 1\pmod p。 而我们要求 ax\equiv 1\pmod p 的解，由传递性可得：

\begin{aligned} ax\equiv a^{p-1}\pmod p\\ x\equiv a^{p-2}\pmod p \end{aligned}

得证。

2. 扩展欧几里得算法：将方程改写为 ax+py=1，使用扩展欧几里得算法求出 x 即可。

题目：

• [NOIP2012 提高组] 同余方程

求区间内的乘法逆元

1. 暴力+快速幂：

仅适用于 p 为质数且 a\perp p 的情况，时间复杂度 \mathcal{O}(n\log p)。

2. 暴力+扩展欧几里得算法：

代码见扩展欧几里得算法，时间复杂度 \mathcal{O}(n\log p)。

3. 线性递推：

\therefore facinv_{i+1}\times (i+1)=\frac{1}{i!}=facinv_i

得证。

时间复杂度 \mathcal{O}(n)。

欧拉定理

前置知识：

1. 同余类：\forall a\in[0,m-1]，集合 \{a+km\}(k\in \mathbb{Z}) 的所有数模 m 同余，余数均为 a，则称该集合为一个模 m 的同余类，记为 \overline{a}。

2. 完全剩余系：m 个模 m 的同余类 \overline{i} (i\in[0,m-1]) 所构成的集合称为完全剩余系。

3. 简化剩余系：\varphi(m) 个与 m 互质的数的同余类所构成的集合称为简化剩余系。

4. 费马小定理：见乘法逆元。

定义：若 a\perp p，则 a^{\varphi(p)}\equiv 1\pmod p。

扩展欧拉定理

题目：

• 【模板】扩展欧拉定理

• [六省联考 2017] 相逢是问候

扩展欧几里得算法

前置知识：

1. 欧几里得算法：见求最大公约数。

2. 裴蜀定理（Bézout 定理）：\forall a,b\in \mathbb{Z},\exists x,y\in \mathbb{Z},ax+by=\gcd(a,b)。

在欧几里得算法的最后一步，即 b=0 时，显然存在 x=1,y=0 使 a\times 1+0\times 0=\gcd(a,0)。 考虑当 b>0 时，\gcd(a,b)=\gcd(b,a\bmod b)，设存在一对整数 x,y 使得 \gcd(b,a\bmod b)=bx+(a\bmod b)y。 由取模的定义式，可转化 bx+(a\bmod b)y=bx+(a-b\lfloor \frac{a}{b} \rfloor)y=ay+b(x-\lfloor \frac{a}{b} \rfloor y)。 故当 x^{\prime}=y,y^{\prime}=x-\lfloor \frac{a}{b} \rfloor y 时，有 ax^{\prime}+by^{\prime}=\gcd(a,b)，对递归过程使用数学归纳法即可得证。

对于求 ax+by=\gcd(a,b) 中 x,y 的值，由裴蜀定理的证明中可知仅需要在欧几里得算法中保存 x,y 即可。

int exgcd(int a,int b,int &x,int &y){
    if (!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int z=x;
    x=y;
    y=z-y*(a/b);
    return d;
}

题目：

• 【模板】二元一次不定方程 (exgcd)

中国剩余定理

前置知识：

1. 乘法逆元：见乘法逆元。

若 p_1,p_2,\dots,p_n 两两互质，求解方程组：

设 m=\prod_{i=1}^{n}{p_i}，M_i=\frac{m}{p_i}，t_i 为 M_i 模 p_i 的乘法逆元，则 x=\sum_{i=1}^{n}{a_iM_it_i}\bmod m。

$\therefore \forall k\neq i,a_kM_kt_k\equiv 0\pmod {p_k} \because t_i\equiv(M_i)^{-1}\pmod {p_i} \therefore a_iM_it_i\equiv a_i\pmod {p_i}

由同余式相加性且 m=\prod_{i=1}^{n}{p_i} 可知 x 在展开之后即为 \sum_{i=1}^{n}{a_iM_it_i}\bmod m，得证。

时间复杂度 \mathcal{O}(n\log p)。

int CRT(int n){
    F(i,1,n){
        exgcd(M/p[i],p[i],x,y);
        x=(x%p[i]+p[i])%p[i];
        ans+=x*a[i]*(M/p[i]),ans%=M;
    }
    return ans;
}

题目：

• 【模板】中国剩余定理（CRT）/ 曹冲养猪

扩展中国剩余定理

前置知识：

1. 扩展欧几里得算法：见扩展欧几里得算法。

若 p_1,p_2,\dots,p_n 不保证两两互质，则上述结论不成立，需要另外一种解法。

考虑 n=2 的情况，可转化为不定方程 x=kp_1+a_1=bp_2+a_2,k,b\in \mathbb{Z}，则有 kp_1-bp_2=a_2-a_1。

若 a_2-a_1 \nmid \gcd(p_1,p_2)，则无解，反之可用扩展欧几里得算法求出一组解 (k,b)。

则 x\equiv kp_1+a_1\pmod {\operatorname{lcm} (p_1,p_2)}。

扩展到 n\neq 2 的情况，仅需要依次求解即可。

时间复杂度 \mathcal{O}(n\log n)。

int exCRT(int n){
    int ret=a[1],cur=p[1],x,y;
    F(i,2,n){
        int gcd=exgcd(cur,p[i],x,y),c=((a[i]-ret)%p[i]+p[i])%p[i];
        if (c%gcd) return -1;
        x=quick_mul(x,c/gcd,p[i]/gcd);
        ret+=x*cur;
        cur=cur/gcd*p[i];
        ret=(ret%cur+cur)%cur;
    }
    return (ret%cur+cur)%cur;
}

题目：

• 【模板】扩展中国剩余定理（EXCRT）

组合

加法原理 乘法原理

加法原理（分类）：一个问题有 n 类方法，每个类别有 a_i 个不同的方法，那么解决此问题有 a_1+a_2+\dots+a_n 个方法。

乘法原理（分布）：一个问题有 n 个方法，每个方法有 a_i 个不同的方式，那么解决此问题的方式个数为 a_1\times a_2\times \dots \times a_n。

容斥原理

当 n=2 时，|A\cup B|=|A|+|B|-|A\cap B|

当 n=3 时，|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|

通项式：|\bigcup_{i=1}^{n}A_i|=\sum_{\varnothing \neq J=\subseteq\{1,2,\dots,n\}}(-1)^{|J|-1}|\bigcap_{j\in J}A_j|

德摩根定律

简记：交之补等于补之并，并之补等于补之交。

推论：|\bigcap_{i=1}^{n}\overline{A_i}|=\sum_{\varnothing \neq J\subseteq \{1,2,\dots,n\}}(-1)^{|J|}|\bigcap_{j\in J} A_j|

\begin{aligned} |\bigcup_{i=1}^{n}A_i|=\sum_{\varnothing \neq J=\subseteq\{1,2,\dots,n\}}(-1)^{|J|-1}|\bigcap_{j\in J}A_j|\\ |\bigcap_{i=1}^{n}\overline{A_i}|=\sum_{\varnothing \neq J\subseteq \{1,2,\dots,n\}}(-1)^{|J|}|\bigcap_{j\in J} A_j|\\ |\bigcap_{i=1}^{n}{A_i}|=\sum_{\varnothing \neq J\subseteq \{1,2,\dots,n\}}(-1)^{|J|}|\bigcap_{j\in J} \overline{A_j}| \end{aligned}

排列数 组合数

排列数：A_{n}^{k}=\frac{n!}{(n-k)!}

组合数：C_{n}^{k}=\binom{n}{k}=\frac{A_{n}^{k}}{k!}=\frac{n!}{(n-k)!k!}=\frac{n\times(n-1)\times \dots \times (n-k+1)}{k!}=\frac{\prod_{i=0}^{k-1}{(n-i)}}{k!}

特别地，若 k>n 则 A_{n}^{k}=C_{n}^{k}=0。

性质：

1. C_{n}^{0}=1$，$C_{n}^{1}=n$，$C_{n}^{2}=\frac{n(n-1)}{2}
2. C_{n}^{k}=C_{n}^{n-k}
3. C_{n}^{k}=C_{n-1}^{k}+C_{n-1}^{k-1}
4. \sum_{i=0}^{n}C_{n}^{i}=2^n

求组合数

1. 暴力：

int C(int n,int k,int p){
    int a=1,b=1;
    F(i,0,k-1) a*=(n-i);
    F(i,1,k) b*=i;
    return (a/b)%p;
}

时间复杂度 \mathcal{O}(Tn)，但适用性极差（易爆 long long）。

2. 递推预处理：

由性质 3 得证。

void InitC(int n,int p){
    F(i,0,n){
        C[i][0]=1;
        F(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
    }
    return ;
}

时间复杂度 \mathcal{O}(n^2+T)。

3. 预处理阶乘+逆元：

这里使用了快速幂求逆元。

int C(int n,int k,int p){
    if (!k) return 1;
    return (fac[n]*ksm(fac[n-k],p-2,p)%p*ksm(fac[k],p-2,p)%p)%p;
}

时间复杂度 \mathcal{O}(n+T\log p)。

4. 卢卡斯定理：

见卢卡斯定理，仅限 p 为质数时适用，时间复杂度 \mathcal{O}(p+T\times \log n)。

5. 扩展卢卡斯定理：

当 p 不为质数时也适用，时间复杂度 \mathcal{O}(p+T\log p)。

二项式定理

对于每一个 (x+y)，显然要么选 x，要么选 y。 若有 k 个 (x+y) 选择 y，则有 n-k 个选择 x，由于要选取 k 个 (x+y)，故系数为 C_{n}^{k}。 因为 k 为分类，所以利用加法原理，得证。

计数技巧

等价替代

对于某些计数题，正面解决可能会很困难，这时可以用一些方法将问题转化为另一种更为容易计算的问题。

捆绑法

若要求某些物品相邻，则可将所需相邻的物品看做一个整体，然后计算排列，再分别计算每个整体内的排列相乘。

例题：有 \text{ABCDE} 五种物品，其中要求 \text{AB} 相邻，\text{CD} 相邻，求排列方案数。

可先将 \text{AB} 和 \text{CD} 看作一个整体，然后对剩下的 3 个物品进行排列，有 A_{3}^{3}=6 种排列方案。 然后再计算各个整体内的排列，A_{2}^{2}=2 种。 故共有 2\times A_{2}^{2}\times A_{3}^{3}=24 种排列方案。

插空法

若要求某些物品两两不相邻，则可先将其它的物品排好，然后再从空当中插入，分别计算排列后相乘。

例题：有 \text{ABCDEFG} 其中物品，其中要求 \text{ABC} 两两不相邻，求排列方案数。

先对其它 4 种物品进行排列，有 A_{4}^{4}=24 种方案。 然后将剩下 3 种物品插入到其中的 5 个空当中，有 A_{5}^{3}=60 种方案，故共有 A_{4}^{4}\times A_{5}^{3}=1440 种排列方案。

隔板法

至少分配问题和不定方程整数解问题可转化为关于插板的组合问题。

例题 1：将 n 个物品分给 k 个人，要求每个人至少被分配到一个，求方案数。

将 n 件物品排成一行，中间有 k-1 个隔板，表示每个人分到的部分，而 k-1 个隔板只能插入到 n-1 个空当中，故方案数为 C_{n-1}^{k-1}。

例题 2：将例题 1 的限制改为“允许有人被分配到 0 个”，求方案数。

可将题意抽象为数学模型，求方程 \sum_{i=1}^{k}x_i=n 的解，其中 x_i\geq 1。 若改限制为 x\geq 0，则设 y_i=x_i+1，转化为 \sum_{i=1}^{k}=n+k。 再结合上题的解，即可求出方案数为 C_{n+k-1}^{k-1}。

改变计数目标

对于某些计数题，直接解决可能会很困难，可以用减法原理或容斥原理等内容转化为容易求的问题。

改变枚举顺序

对于某些计数题，直接枚举只能拿到暴力分，可以改变枚举顺序使其更容易计算。

例题：求 \sum_{i=1}^{n}\sum_{j=1}^{n}\max(i,j)。

\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{n}\max(i,j)\\ =\sum_{k=1}^{n}k\sum_{i=1}^{n}\sum_{j=1}^{n}[\max(i,j)=k]\\ =\sum_{k=1}^{n}k(2k-1)\\ =2\sum_{k=1}^{n} k^2 -\frac{(n+1)n}{2}\\ =\frac{4n^3+3n^2-n}{6} \end{aligned}

多重集的排列组合数

多重集：指包含重复元素的广义集合。

多重集的排列数

设 S=\{n_1a_1,n_2a_2,\dots,n_ka_k\} 为多重集，则 S 的全排列个数为 \frac{(\sum_{i=1}^{k} i)!}{\prod_{i=1}^{k}n_i!}

多重集的组合数

设 S=\{n_1a_1,n_2a_2,\dots,n_ka_k\} 为多重集，从 S 中取出 r(r\leq \min(n_i)) 个元素组成一个多重集，不考虑元素顺序，产生不同的多重集的数量为 C_{k+r-1}^{k-1}

设对于每一个 a_i 选取 x_i 个，则问题可转化为 \sum_{i=1}^{k}x_i=r(x_i\geq 0) 的不定方程。 用隔板法求解即可。

卢卡斯定理

模数 p 必须为质数。

其中对于左半部分进行递归，右半部分直接进行计算，因为 n\bmod p,m\bmod p\in [0,p-1]。

时间复杂度 \mathcal{O}(p+T\times \log n)。

int fac[N],facinv[N];
void Init(int n,int p){
    fac[0]=1;
    F(i,1,n) fac[i]=fac[i-1]*i,fac[i]%=p;
    facinv[n]=ksm(fac[n],p-2,p);
    FJ(i,n-1,0) facinv[i]=facinv[i+1]*(i+1),facinv[i]%=p;
    return ;
}
int C(int n,int m,int p){
    if (m>n) return 0;
    return ((fac[n]*facinv[m])%p*facinv[n-m])%p;
}
int Lucas(int n,int m,int p){
    if (!m||n==m) return 1;
    return (Lucas(n/p,m/p,p)*C(n%p,m%p,p))%p;
}
int Solve(int n,int m,int p){
    Init(p-1,p);
    return Lucas(n,m,p);
}

卡特兰数

定义：一种常出现于各种计数问题的数列，记作 H_n，特别地，H_0=H_1=1。

卡特兰数列：

常见题型

2. 入栈序列为 1,2,\dots,n 的合法出栈序列数量？H_n。
4. 只能向上或向右走，能从 (0,0) 走到 (n,n) 且不接触直线 y=x 的路线的数量？2H_{n-1}。
5. 只能向上或向右走，能从 (0,0) 走到 (n,n) 且不穿过直线 y=x 的路线的数量？H_{n+1}。

求卡特兰数

以下所有公式均有 i\geq 2。

1. 递推：

2. 组合通式：