基础数论（第二版）

· · 算法·理论

Part 1.排列组合

排列

将 n 个不同的东西排成一排，问有多少种排法？

这是一个经典的排列问题，通常我们用 A^m_n 表示从 n 个物品中选 m 个的不同的排列方案，像上面那个问题的答案就是 A_n^n。

计算公式为 A_n^m=\frac{n!}{(n-m)!}=n \cdot (n-1) \cdot (n-2) \cdot \dots \cdot (n-m+1)。

特别地，当 m>n 时，A_n^m=0。

组合

在 n 个物品中选出 m 个物品，问有多少种选法？

这是一个经典的求组合数的问题，我们可以用 C^m_n 来表示在 n 个物品中选出 m 个物品的方案数，即上面那个问题的答案。

计算公式为 C^m_n=\frac{A_n^m}{m!}=\frac{n!}{m! \cdot(n-m)! }。当然，组合数也有递推公式，C_i^j=C_{i-1}^{j-1}+C_{i-1}^{j}，此公式的代码如下：

c[0][0]=1;
    for(int i=1;i<=n;i++)c[i][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
        }
    }

Part 2.隔板法

有 n 个物品，现在要将这 n 个物品分成 m 组，每组至少有一个物品，问有多少种方案？

对于上面那个问题，我们可以设这 n 个物品排成一行，每相邻两个物品中间都有一个空隙，然后我们有 m-1 个板子，将这些板子插入空隙，每个空隙都只能插一个板子，板子一共有 C^{m-1}_{n-1} 种插法，上面那个问题的答案也是如此。

一个很重要的变式

假设现在有一个点在数轴的原点上，它要走到点 x 上，但它必需走 n(x \leq n) 步，每步能向左或向右走且只能走一个单位长度，问它有多少种方案能使它走到点 x 上？

这个问题我们暂且可以称它为乱窜的点，如果这个点一直向终点方向走那么只需要走 x 步，也就是说一共有 x-1 个空隙，但没规定第一步只能向右走，也没规定走到终点时步数没用完就不能动，所以一共有 x+1 个空隙。同时可以发现一个性质，这个点向左走一步之后又向右走一步相当于没有走，但剩余步数减少了两步，利用这个性质我们就可以知道板子的数量为 \frac{n-x}{2}。

最后这个问题的答案为 C_n^{\frac{n-x}{2}}。

Part 3.卢卡斯定理（lucas）

卢卡斯定理用于求解大组合数取模的问题，其中模数必须为质数。正常的组合数运算可以通过递推公式求解，但当问题规模很大，而模数是一个不大的质数的时候，就不能简单地通过递推求解来得到答案，需要用到卢卡斯定理。

卢卡斯定理的具体内容是对于所有的质数 p 有 C_n^m \bmod p=C_{n/p}^{m/p} \cdot C_{n \bmod p}^{m \bmod p} \bmod p。注意：p 是个质数且范围不能太大。

特别地，当 m=0 时返回 1。

代码实现：

long long Lucas(long long n, long long m, long long p) {
  if (m == 0) return 1;
  return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;
}

Part 4.杨辉三角

杨辉三角又称帕斯卡三角，它的每一个数都是组合数，每一个数都等于上一行中这个位置左右两边的数之和，没有的就记为 0。

这张图片中所呈现的就是杨辉三角。

杨辉三角的性质

  1. 杨辉三角中第 i 行 j 列的数就是 C(i,j)。
  2. 杨辉三角有一定的对称性，即 C(i,j)=C(i,i-j)。
  3. 杨辉三角的每一行对应于二项式展开的系数。例如 (a+b)^n 的展开式中各项的系数就是杨辉三角的第 n 行。

    Part 5.斯特林数

    第二类斯特林数

    （先别急着问为什么先讲第二类）

第二类斯特林数表示讲 n 个两两不同的元素，划分为 k 个互不区分的非空子集的方案数，可记作 S(n,k)。

其递推表达式为：S(n,k)=S(n-1,k-1)+k \cdot S(n-1,k)。

代码如下：

f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=(f[i-1][j]*j+f[i-1][j-1])%mod;
        }
    }

第一类斯特林数

第一类斯特林数是在第二类斯特林数的基础上加了一个条件：每个子集除了非空之外轮换也算作一种方案，即 [A,B,C,D] 等价于 [D,C,B,A] 但不等价于 [A,C,B,D]，第一类斯特林数可以表示为 s(n,k)。

其递推表达式为：s(n,k)=s(n-1,k-1)+(n-1) \cdot s(n-1,k)。

代码如下：

s[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i&&j<=m;j++){
            s[i][j]=s[i-1][j-1]+(i-1)*s[i-1][j]%mod;
        }
    }

Part 6.例题

例题 1

题目描述

计算 C(n,m) \bmod p，其中 p 是质数且 1<p<10^6，1 \le m \le n \le 10^6。

解析

从题目描述中很容易就能看出是卢卡斯定理，但是这里让我们计算 C(n,m) 就可以知道需要用到快速幂，而且这个题需要计算多个组合数，所以就可以直接公式套出组合数，然后就是直接套卢卡斯定理的公式了（这里数据范围不是很大，因此处理一些像 n=p 的特殊情况没那么麻烦，至于数据大一点这个代码就可能要跑很久，这里就不给出数据太大的做法）。

参考代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,p;
int ksm(int x,int y,int mod){
    int res=1;
    while(y){
        if(y&1ll)res=res*x%mod;
        x=x*x%mod;
        y>>=1ll;
    }
    return res;
}
int get_comb(int x,int y){
    int a=1,b=1,c=1;
    for(int i=1;i<=x;i++){
        a=a*i%p;
        if(i==y)b=a;
        if(i==x-y)c=a;
    }
    b=ksm(b,p-2,p);
    c=ksm(c,p-2,p);
    return a*b%p*c%p;
}
int lucas(int x,int y){
    if(x<y||x<0||y<0)return 0;
    else if(x<p)return get_comb(x,y);
    else return lucas(x%p,y%p)*lucas(x/p,y/p)%p;
}
signed main(){
    cin>>n>>m>>p;
    cout<<lucas(n,m);
    return 0;
}

例题 2

题目描述

何老板打算在 NK 食堂办酒席，宴请信竞队队员。信竞队共有 n 名队员，编号 1 到 n，大家都很想参加宴会。但何老板只邀请其中 r 个队员。他要你帮他选出 r 名队员，要求选出的这些队员的编号差必须大于等于 k（任意两人都要大于等于 k）。
然后由你来预订酒桌和安排队员们就座。何老板要求酒桌的数量不超过 m，每桌至少坐 1 人。何老板想知道，总共有多少种不同的方案？

解析

从题目不难看出是第二类斯特林数加动态规划，具体的解请看代码里的注释，这里就不再多说了。

参考代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int n,m,r,k,ans,f[1005][1005],dp[1005][1005];
//$dp_{i,j}$ 表示前 $i$ 个人中选 $j$ 个人的情况。
//$f_{i,j}$ 表示第一类斯特林数 
signed main(){
    cin>>n>>r>>k>>m;
    for(int i=1;i<=n;i++){
        dp[i][1]=i;//只选一个人有 $i$ 种情况 
        dp[i][0]=1;//一个人也不选也是一种情况 
    }//初始化 
    for(int i=k+1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=(dp[i-k][j-1]+dp[i-1][j])%mod;
        }
    }
    f[0][0]=1;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=(f[i-1][j]*j%mod+f[i-1][j-1]%mod)%mod;
            //左:选,右:不选  
        }
    }
    for(int j=1;j<=m;j++){
        ans=ans+f[r][j];//$1$ 到 $m$ 的桌子情况数 
        ans=ans%mod;
    }
    cout<<ans*dp[n][r]%mod;
    return 0;
}

完结撒花！

最后致敬那个天天请客的何老板。