这是一篇基础数论的笔记,由ny_123457提供

基础数论（第二版）

原作者：luogu ny_123457

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}\)，此公式的代码如下：

1
2
3
4
5
6
7
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\)。

代码实现：

1
2
3
4
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)\)。

代码如下：

1
2
3
4
5
6
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)\)。

代码如下：

1
2
3
4
5
6
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\) 的特殊情况没那么麻烦，至于数据大一点这个代码就可能要跑很久，这里就不给出数据太大的做法）。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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\) 人。何老板想知道，总共有多少种不同的方案？

解析

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

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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;
}

完结撒花！

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