数论家族学习笔记

阅读本文您可能需要一些基本的数学常识，如质数、合数、约数等的定义等。

更新日志

• 2022.03.19 完成数论基础和组合计数的更新
• 2022.03.20 完成 crt 和 BSGS 的更新

可能涵盖的内容

• 目前已有的

数论基础（欧拉筛、乘法逆元和 exgcd、crt 和 excrt、BSGS 和 exBSGS）

组合计数

• 未来可能有的

简单容斥

卡特兰数

斯特林数

欧拉函数

莫比乌斯反演

二项式反演

min-max 容斥

普通型生成函数

指数型生成函数

参考文献

• 基础数论

各个百度百科，在没出地方都有放链接，这里就不放了。

Nickel_Angel's nest 大佬的 [数学]求解一类方程的方法 和 Luogu 日报

WZT 大佬的 题解

阮行止 大佬的 题解

eee_hoho 大佬的 题解

• 组合计数

单凭回忆和之前代码瞎口胡

如有侵权问题，请练习我，我会马上声明或修改。

0 数论基础

我们先学习一些简单的数论基础为后面的学习做铺垫.

0.1 欧拉筛

问题 0.1.1：线性时间内求出 \(n\) 以内所有质数。

首先根据质数的定义，我们可以很容易打出一个 \(O(n\log n)\) 的埃氏筛。

bool flg[N];
int pri[N],tot;
void get_pri(int n){
	flg[1]=1;
    for(int i=2;i<=n;i++){
    	for(int j=i;i*j<=n;j++)flg[i*j]=1;
	}
	for(int i=1;i<=n;i++)if(!flg[i])pri[++tot]=i;
}

然后我们考虑如何优化这个过程。

我们发现中间 flg 的赋值有很多重复，比如 \(12=2\times6=3\times4\)，就被计算了两次。

这样子浪费了很多时间，我们能否构造一种算法使其每个合数只被赋值一次呢？

我们可以把一个合数分解为它的最小质因子乘以另外一个数，

对于每一个 \(i\)，从小到大枚举质数，直到枚举的质数能够整除 \(i\)，然后就停止枚举。

这样的话我们发现每一个数最多只会被乘一次，就可以 \(O(n)\) 筛质数了，这就是欧拉筛。

同时，我们可以再欧拉筛的过程中预处理出一些奇性函数的值，如后面的欧拉函数和莫比乌斯函数。

bool flg[N];
int pri[N],tot;
void get_pri(int n){
	for(int i=2;i<=n;i++){
		if(!flg[i])pri[++tot]=i;
		for(int j=1;j<=tot&&i*pri[j]<=n;j++){
			flg[i*pri[j]]=1;
			if(i%pri[j]==0)break;//这里是break，否则复杂度还是一个log 
		}
	}
}

然后你就可以顺利通过 P3383 【模板】线性筛素数。

评测记录

我们也可以用欧拉筛优化一些过程，比如质因数分解。

我们可以再欧拉筛的过程记录下来每一个数的最小质因子，然后质因数分解的时候时间复杂度就只有 \(O(质因数个数)\) 了。

bool flg[N];
int pri[N],tot,num[N];
void get_pri(int n){
	for(int i=2;i<=n;i++){
		if(!flg[i])pri[++tot]=i,num[i]=i;
		for(int j=1;j<=tot&&i*pri[j]<=n;j++){
			flg[i*pri[j]]=1,num[i*pri[j]]=pri[j];
			if(i%pri[j]==0)break;//这里是break，否则复杂度还是一个log 
		}
	}
}
int p[N],e[N],cnt;
void fen(int x){
	cnt=0;
	while(x!=1){
		p[++cnt]=num[x];
		e[cnt]=0;
		while(x%p[cnt]==0)x/=p[cnt],++e[cnt];
	}
}

0.2 乘法逆元和 exgcd

我们都知道很多题目为了防止精度问题或爆 long long，都会要求我们对某个数 \(p\) 取模。

如果在运算中有除法操作，一般来说 \(p\) 都是质数，那么我们如何执行这个操作呢？

乘法逆元就是用来解决这个问题的。

要学习乘法逆元，我们需要初步了解群论，这里就不介绍基础群论知识了。

乘法逆元的定义（摘自百度百科）：

定义：乘法逆元，是指数学领域群 \(G\) 中任意一个元素 \(a\)，都在 \(G\) 中有唯一的逆元 \(a^{-1}\)，具有性质 \(a\times a^{-1}=a^{-1}\times a=e\)，其中 \(e\) 为该群的单位元。

我们讨论的域是在模素数 \(p\) 域下的。

因此，我们有 \(\frac ab\equiv\frac ab\times b\times b^{-1}\equiv ab^{-1}\)，然后，我们就可以用乘法逆元代替除法运算了。

我们一般采用费马小定理来求一个数的逆元。

引理 0.2.1（费马小定理）：如果 \(a\) 不是 \(p\) 的倍数，那么 \(a^{p-1}\equiv 1(\bmod p)\)。

证明可以采用剩余系的方法，这里不展开了，如果有兴趣可以去百度百科。

这其实是欧拉定理的一种特殊情况，我们在后面介绍欧拉函数性质的时候会介绍。

既然如此，我们就得到了 \(a\times a^{p-2}\equiv 1\)，所以我们可以通过快速幂计算 \(a^{p-2}\% p\) 来得到 \(a\) 的逆元。

---

接下来我们来学习扩展欧几里得定理。

问题 0.2.2：给定 \(a,b,c\)，求出一组整数解 \(ax+by=c\) 或判无解。

首先，我们先判一组方程是否有解。

引理 0.2.2（裴蜀定理）：若不定方程 \(ax+by=c\) 有整数解，当且仅当 \(\gcd(a,b)|c\)。

证明可以用数学归纳法，这里不过多赘述，若对此感兴趣，可移步百度百科。

然后，我们就可以用递归的方法求解。

令 \(d=\gcd(a,b)\)，则我们先求出 \(ax+by=d\) 的解，然后 \(x,y\) 同时乘以 \(\frac c{d}\) 就可以了。

如果 \(b=0\)，那么 \(a=d\)，其中一组特解是 \(x=1,y=0\)。

否则我们先求出 \(bx+(a\%b)y=d\) 的一组解 \(x',y'\)，然后我们推一下式子：

\[bx'+(a\%b)y'=bx'+(a-b\lfloor\frac ab\rfloor)y'\\ =ay'+b(x'-\lfloor\frac ab\rfloor y') \]

所以，我们让 \(x=y',y=x'-\lfloor\frac ab\rfloor 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 tmp=x;
	x=y,y=tmp-a/b*y;
	return d;
}

然后，根据这组特解，我们可以解决很多问题，如正整数解个数等。

我们就可以顺利通过 P5656 【模板】二元一次不定方程 (exgcd)。

评测记录

---

exgcd 还可以求解线性同余方程的问题：

问题 0.2.3 给定 \(a,b,m\)，求解 \(ax\equiv b(\bmod m)\) 或判无解。

我们转化一下问题的式子：\(ax+my=b\)，其中 \(y\) 可以是任意整数，这样就满足了同余的条件了。

我们发现，当 \(b=1\)时，我们就可以用这种方法求出 \(a\) 的逆元。

int inv(int a,int p){
    int x,y;
    int d=exgcd(a,p,x,y);
    if(d!=1)return -1;
    return (x%p+p)%p;
}

这种求逆方法在 \(p\) 不为质数时也适用。

根据这个，我们可以推出一种 \(p\) 为质数是的线性递推求逆的方法。

首先，我们有 \(1^{-1}=1\)，

然后，对于一个数 \(i\)，我们假设 \(p=ki+r\)，那么就有：

\[ki+r\equiv 0 \]

\[i^{-1}r^{-1}(ki+r)\equiv0 \]

\[i^{-1}r^{-1}ki+i^{-1}r^{-1}r\equiv0 \]

\[r^{-1}k+i^{-1}\equiv0 \]

\[i^{-1}\equiv -r^{-1}k \]

然后我们就可以愉快递推了。

int inv[N];
inv[1]=1;
for(int i=2;i<=n;i++)inv[i]=inv[i%p]*(p-p/i)%p;

---

因为这个笔者比较懒问题较简单，所以就不放例题了，直接放练习。

P1082 [NOIP2012 提高组] 同余方程

P1292 倒酒

P1516 青蛙的约会

0.3 crt 和 excrt

crt，又称中国剩余定理，解决如下的问题：

问题 0.3.1：\(\begin{cases}x\equiv a_1(\bmod m_1)\\x\equiv a_2(\bmod m_2)\\\dots\\x\equiv a_n(\bmod m_n)\end{cases}\)

求出以上同余方程的最小非负整数解（保证 \(m_i\) 两两互质）。

我们假设 \(M=\prod m_i,M_i=\frac{M}{m_i}，t_i\equiv M_i^{-1}(\bmod m_i)\)，

\(M\) 是所有模数的乘积，\(M_i\) 时所有模数除了当前模数的乘积，\(t_i\) 是在模 \(m_i\) 的意义下 \(M_i\) 的逆元。

我们可以发现能够构造出一组特解 \(x'=\sum a_iM_it_i\)，我们发现每方程的 \(a_iM_it_i\) 在模其他模数的意义下都是 \(0\)，所以全部加起来这个式子仍然成立。

所以，我们能够得到方程通解：\(x=x'+kM\)，其中 \(k\) 可以是任意整数，所以我们就能很轻松的求出最小非负整数解。

然后，结合上面 0.2 的求逆方法，我们就能轻松过掉 P1495 【模板】中国剩余定理(CRT)/曹冲养猪。

signed main(){
	scanf("%lld",&n);
    M=1;
    for(int i=1;i<=n;i++){
    	scanf("%lld%lld",&m[i],&a[i]);
        M*=m[i];
    }
    for(int i=1;i<=n;i++){
        Mi[i]=M/m[i];
        int x=0,y=0;
        exgcd(Mi[i],m[i],x,y);
        ans+=a[i]*Mi[i]*x; 
    }
}

评测记录

---

接下来，我们考虑扩展到 \(m_i\) 不一定互质的情况，这个时候，我们发现 \(M_i\) 不一定存在逆元，所以中国剩余定理不再适用。

对于一组方程：

问题 0.3.2：\(\begin{cases}x\equiv a_1(\bmod m_1)\\x\equiv a_2(\bmod m_2)\\\dots\\x\equiv a_n(\bmod m_n)\end{cases}\)

我们可以考虑合并两个线性同余方程，直到最后 \(x\equiv A(\bmod M)\)，就能够得出答案。

对于两个同余方程：\(\begin{cases}x\equiv a_1(\bmod m_1)\\x\equiv a_2(\bmod m_2)\end{cases}\)，我们发现可以这样表示：

\[x=k_1m_1+a_1=k_2m_2+a_2 \]

\[k_1m_1-k_2m_2=a_2-a_1 \]

我们发现这个东西有点眼熟，乍一看，不就是前面的不定方程吗，直接上 exgcd，当然，根据裴蜀定理，也有可能无解！

然后假设我们得出了一个特解 \(x'\)，通解是什么，又如何转化成同余方程的形式继续和别的方程合并呢？

我们发现，对 \(x\) 增减若干个 \(t=\text{lcm}(m_1,m_2)\)，是不会影响两个同余方程的结果的，

所以，我们可以把 \(x\) 满足的要求写成这样： \(x\equiv x'(\bmod \text{lcm}(m_1,m_2))\)，然后我们就能继续合并了。

这就是扩展中国剩余定理（excrt）的大致思路了，至此，我们能够顺利通过P4777 【模板】扩展中国剩余定理（EXCRT）。

signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld%lld",&s[i],&r[i]);
    M=s[1],X=r[1];
    for(int i=2;i<=n;i++){
        int d=exgcd(M,s[i],x,y),c=(r[i]-X%s[i]+s[i])%s[i];
        if(c%d!=0)return puts("No solution"),0;//并没卵用的特判 
        x=mul(x,c/d,s[i]);//注意可能爆long long，要写龟速乘 
        X+=x*M;
        M=M/d*s[i];
        X%=M;
    }
    printf("%lld\n",(X%M+M)%M);
}

评测记录

几道练习：

P5481 [BJOI2015] 糖果

P4774 [NOI2018] 屠龙勇士

Oiclass 1791 数学题

Oiclass 2912 小A的字母游戏

0.4 BSGS 和 exBSGS

BSGS（Baby Step Giant Step，中文名叫大步小步法），用于解决高次同余方程的问题：

问题 0.4.1（P3846 [TJOI2007] 可爱的质数/【模板】BSGS）：给出 \(a,b,p\)，求最小的 \(x\) 满足 \(a^x\equiv b(\bmod p)\)，或判无解（满足 \(p\in prime\)）。

本题 \(p<2^{31}\)，可以用 BSGS。

整体思路大概就是一个分块和哈希表。要满足的条件不一定是 \(p\in prime\)，只要满足 \(\gcd(a,p)=1\) 即可。

设 \(t=\lfloor\sqrt p\rfloor,x=it-j,(0\le j，那么，我们有

\[a^{it-j}\equiv b(\bmod p)\\ (a^t)^i\equiv b\times a^j(\bmod p) \]

然后我们把所有 \(0\le j 的 \(a^jb\) 放到一个 hash 里，然后对于所有 \((a^t)^i\)，看看有没有符合条件的 \(a^jb\) 即可。

然后你就可以顺利通过这道题了。

因为这题我是用 exBSGS 写的，就不放代码了。

---

问题 0.4.2（P4195 【模板】扩展 BSGS/exBSGS）：在问题 0.4.1 的基础上，扩展到 \(\gcd(a,p)\not=1\) 的情况。

我们发现可能到某一步 \(a^k\) 就变成了 \(0\)，无法除过去。

我们设 \(d=\gcd(a,p),a=a'd,p=p'd\)，

那么原来的方程等价于 \(a^{x-1}a'\equiv \frac bd(\bmod p')\)，

容易发现，当 \(d?b\) 的时候，方程无解。

这个时候，\(a'\) 是有逆元的，我们把它移项，然后方程变成：\(a^{x-1}\equiv \frac bda'^{-1}(\bmod p')\)，然后继续循环，直到满足 \(\gcd(a,p')=1\)位置，然后就可以用 BSGS了。

因为 exBSGS 代码复杂度不高，但范围比 BSGS 大，所以笔者一半都写 exBSGS。

struct HashTable{
    const int mod=1e6+7;
    int mp[1000700],hs[1000700];
    int find(int x){
        int t=x%mod;
        for(;mp[t]!=x&&mp[t]!=-1;)t=(t+107)%mod;
        return t;
    }
    void insert(int x,int y){
        int f=find(x);
        mp[f]=x,hs[f]=y;
    }
    bool check(int x){
        int f=find(x);
        return mp[f]==x;
    }
    int query(int x){
        int f=find(x);
        return hs[f];
    }
    void clear(){
        memset(hs,-1,sizeof hs);
        memset(mp,-1,sizeof mp);
    }
}ha;
int exBSGS(int a,int b,int m){
    if(b%m==1)return 0;
    int tmp=1,d=gcd(a,m),k=0;
    while(d!=1){
        if(b%d!=0)return -1;
        b/=d,m/=d,++k;
        tmp=tmp*(a/d)%m;
        if(tmp==b)return k;
        d=gcd(a,m);
    }
    ha.clear();
    int t=ceil(sqrt(m));
    ha.insert(b,0);
    for(int i=1;i<=t;i++)b=b*a%m,ha.insert(b,i);
    a=qpow(a,t,m);
    for(int i=1;i<=t;i++){
        tmp=tmp*a%m;
        int j=ha.query(tmp);
        if(j!=-1)return i*t+k-j;
    }
    return -1;
}

BSGS 评测记录

exBSGS 评测记录

BSGS 和 exBSGS 的用途还有很多，可以求模意义下的二次剩余等，这里不展开吸收。

几道练习：

三倍经验 SP3105 MOD

四倍经验 UVA10225

五倍经验 P2485 [SDOI2011]计算器

1 组合计数

1.1 加法原理和乘法原理

我们先通过一个例子来简单介绍一下加法原理和乘法原理。

例 1.1.1：奶牛从广州到浙江有 \(3\) 种高铁路线，\(3\) 种动车路线，\(2\) 种飞机路线，求总共有多少种方式从广州到浙江。

很显然，总共有 \(3+3+2=8\) 种方式。

像这样，选项之间互相不干预，或者说是互相独立的，并列事件的选择（也就是我们常说的分类计算），我们应该在它们之间使用加号统计，我们把这称为加法原理。

例 1.1.2：奶牛从广州到浙江有 \(3\) 条路径，从浙江到北京有 \(2\) 条路径，求总共有多少种方式从广州到北京。

很显然，总共由 \(3\times 2=6\) 种方式。

像这样，选项之间互相独立的，不同时进行的选择（也就是我们常说的分步计算），我们应该用乘号统计，因为可以理解为每一个前一种选择就对应后一种选择，我们把这称为乘法原理。

现在，如果你已经掌握了使用加法原理和乘法原理来计算方案数的方法，那就尝试做做下面的简单练习把！

练 1.1.1：奶牛从广东到浙江有 \(3\) 条路径，从浙江到北京有 \(4\) 条路径；不经过浙江，直接从广州到达北京有 \(3\) 条路径。求总共有多少条路径从广州到北京。

答案：\(3\times 4+3=15\)，加乘原理的混合运用。

接下来，我们开始将问题升级。

1.2 排列组合

我们考虑经典照相问题：

例 1.2.1：有 \(n\) 个人，选 \(m\) 个人出来排成一排，从左到右依次站好，然后对着 \(m\) 个人拍照，求最后的照片有多少种不同的结果。

注意：每个人互不相同。

我们这样考虑，首先我们给 \(n\) 个人标号 \(1,2,\dots,n\)，\(m\) 个位置标号 \(1,2,\dots,m\)。

先选择一个人去 \(1\) 号位置，有 \(n\) 种选择，此时这个被选中的人已经选定了位置，不能参与接下来的选择，剩下 \(n-1\) 个人。

再选择一个人去 \(2\) 号位置，有 \(n-1\) 种选择，此时这个被选中的人已经选定了位置，不能参与接下来的选择，剩下 \(n-2\) 个人。

以此类推，最后 \(m\) 号位置，有 \(n-m+1\) 种选择。

我们发现这个过程是分步计算的，适用乘法原理，所以最后有 \(n\times (n-1)\times \dots \times (n-m+1)\) 种不同结果。

我们发现这个式子可以写简单一点，如果对于一个非负整数 \(n\)，记 \(n!=n\times(n-1)\times(n-2)\times\dots\times 1\)，（特殊地，\(0!=1\)）（阶乘，则这个答案可以写作 \(\frac{n!}{(n-m)!}\)。

我们习惯把这样的问题叫做排列，我们可以这样描述 1.2.1 中的问题：

例 1.2.1'：形式化地，从 \(n\) 个互不相同的元素中，有序地选出 \(m\) 个的方案数 \(A_n^m=\frac{n!}{(n-m)!}\)。

特殊地，如果 \(m=n\)，那么我们把这个问题称为全排列，答案就是 \(n!\)。

例 1.2.2：有 \(n\) 个人，要选出 \(m\) 个人参加比赛，请问有多少中不同的方案数。

这一题的区别在于选出来的人是无序的，也就是说，对于 1 2 3 和 1 3 2，这两种选法我们认为它们是相同的。

我们先假设它们不同，那么方案数就是 \(A_n^m\)，但是每一种原来的选法会对应有 \(A_m^m\) 种原本是相同但是被认为是不同的方案，所以我们计算出的答案是真实的答案的 \(A_m^m\) 倍，除掉就可以了。

我们把这样的问题乘做组合，我们可以这样描述 1.2.2 中的问题。

例 1.2.2'：形式化地，从 \(n\) 个互不相同的元素中，无序地选出 \(m\) 个的方案数 \(C_n^m=\frac{n!}{m!(n-m)!}\)。

当然，组合数也可以写成二项式系数的形式：

\[C_n^m=\dbinom{n}{m}=\frac{n!}{m!(n-m)!} \]

1.3 组合数的性质

我们已经初步认识了排列数与组合数，接下来我们来探究一下与组合数有关的性质。

性质 1.3.1：若 \(n，则 \(\dbinom{n}{m}=0\)。

很显然，这个可以从组合数的定义入手，如果 \(n，我们无法选出一个合法方案，方案数为 \(0\)。

性质 1.3.2：\(\forall n\ge 0,\dbinom n0=\dbinom nn=1\)。

显然，两者一个是全选，一个是全部选，用 1.2 的式子也可以得出同样的结果。

性质 1.3.3：\(\dbinom nm=\dbinom {n-1}m+\dbinom{n-1}{m-1}\)。

这个性质可以直接暴力拆开式子通分得证，但我们还可以从组合意义入手。

解答 1.3.3：我们从 \(n\) 个学生选出 \(m\) 个学生，相当于不选班长，从其它 \(n-1\) 个学生种选 \(m\) 个，也可以选班长，从剩下 \(n-1\) 个学生种选择 \(m-1\) 个。式子得证。

我们发现这个式子非常眼熟，乍一看，不就是杨辉三角嘛。

我们可以根据这个式子做很多事情，这些我们以后再谈，先继续发觉组合数的性质。

性质 1.3.4：\(\sum_{i=0}^n \dbinom ni=2^{n}\)。

当然暴力拆式子也是可证的，但这不就太无趣了嘛。

解答 1.3.4：左边的式子相当于从 \(n\) 个元素中任意分成两组的方案数，相当于我们对于每一个元素可以选择第一组，也可以选择第二组，根据乘法原理，方案数是 \(2^n\)。

性质 1.3.5：\(\dbinom nm=\dbinom n{n-m}\)。

这个也很好理解，就是我们选择 \(m\) 个取出，相当于选择 \(n-m\) 个保留。

性质 1.3.6：\(\sum_{i=0}^n (-1)^i\dbinom ni=0\)。

这个的组合意义就没这么好考虑了，所以我们从杨辉三角入手。

解答 1.3.6：我们发现 \(i\) 是奇数的时候式子刚好覆盖了第 \(n-1\) 行的杨辉三角，是偶数的时候也一样，所以两者恰好相等，可以自行画图理解，也可以暴力拆式子。

性质 1.3.7（二项式定理）：\((x+1)^n=\sum_{i=0}^n \dbinom ni x^i\)。

对于每一项考虑，对于第 \(i\) 项，我们相当于从 \(i\) 个 \((x+1)\) 项里面选 \(x\)，其它选 \(1\) 全部加起来。

当然如果你会生成函数，可以用性质 1.3.4 入手。

设第 \(i\) 行的组合数对应的普通型生成函数 \(C_i(x)=\sum_{i=0}^n\dbinom ni x^i\)，则根据性质 1.3.4 \(C_i(x)=C_{i-1}(x)\times(x+1)\)，因此性质 1.3.7 得证。

看不懂没关系，以后就懂了。

性质 1.3.8（Lucas 定理）：\(\dbinom nm \equiv \dbinom {n\%p}{m\%p}\dbinom {\lfloor\frac np\rfloor}{\lfloor\frac mp\rfloor}(\bmod p)\)，其中 \(p\) 是质数。

这个式子非常重要，如果不会证明背结论就行了。

再证明这个式子之前我们需要做一点准备工作，在此之中我们默认 \(\equiv\) 操作是在 \(\bmod p\) 意义下进行的。

性质 1.3.8.1：\(\forall i\in[1,p-1],\dbinom pi\equiv 0\)。

证明：\(\dbinom pi=\frac {p!}{i!(p-i)!}\)，因为 \(p\) 是质数，所以分母中肯定不含因子 \(p\)，所以这个数肯定是 \(p\) 的倍数，所以 \(\bmod p=0\)。

性质 1.3.8.2：\((x+1)^p\equiv 1+x^p\)。

我们把左侧用二项式定理展开，发现说了首尾两项其它全部系数都是 \(p\) 的倍数。

回归性质 1.3.8，

我们令 \(a=\lfloor\frac np\rfloor\)，\(b=\lfloor\frac mp \rfloor\)，\(l=n\%p\)，\(r=m\%p\)，

那么 \(n=ap+l,m=bp+r\)，也就是说，我们要证明 \(\dbinom nm\equiv \dbinom ab \dbinom lr\)。

我们继续考虑二项式定理：

\[(1+x)^n=(1+x)^{ap}(1+x)^l\\ (1+x)^n\equiv (1+x^p)^a(1+x)^l\\ \]

然后我们观察 \(x^m\) 项系数。

左边：\(\dbinom nmx^m\)，

我们发现右边的左边（也就是 \((1+x^p)^a\)）只能得到指数是 \(p\) 的倍数的，而 \((1+x)^l\) 只能得到指数 \(\le p-1\) 的。

所以右边：\(\dbinom ab\dbinom lrx^{bp+r}=\dbinom ab\dbinom lrx^m\)。

定理得证。

1.4 多种方法求组合数

如何求组合数的方法有很多，因为组合数数字是呈指数级增长的，所以一半会模个什么数，不然就老老实实打高精度吧。

对于不同的数据范围，我们可以应用不同的方法。

为了方便，在这里我们讨论的问题都是求 \(\dbinom nm\%p\)。

范围 1.4.1：\(n,m\le 1000\)。

根据性质 1.3.4，打个杨辉三角的表即可做到 \(O(n^2)\) 预处理，\(O(1)\) 查询。

范围 1.4.2：\(n,m\le 10^6,p\in prime\)。

我们直接从组合数最初在 1.2 里的公式。

我们预处理出 \(n\) 的阶乘，阶乘的逆元，然后就可以做到 \(O(n)\) 预处理，\(O(1)\) 查询。

范围 1.4.3：\(n,m\le10^{18},p\le10^5,p\in prime\)。

可以考虑使用 Lucas 定理，对于 \(n，用 1.4.2 的方法或者直接暴力计算，否则用 Lucas 定理递归处理。

单次时间复杂度 \(O(\log_p n)\)。

至此，你可以用这种方法同过 P3807 【模板】卢卡斯定理/Lucas 定理。

int C(int n,int m,int p){
    int x=1,y=1;
    for(int i=1;i<=m;i++){//因为懒得打表，直接暴力计算
        x=x*(n-i+1)%p;
        y=y*i%p;
    }
//    printf("%lld %lld\n",x,y);
    return x*qpow(y,p-2,p)%p;
}
int lucas(int n,int m,int p){
	if(!m)return 1;
	return C(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
}

评测记录

范围 1.4.4：\(n,m\le10^6,p\le10^5\)。

我们发现 Lucas 定理不适用了，所以可以上扩展 Lucas 定理。

吐槽：感觉两者算法上并没有多大的关系。

因为 \(p\) 可能不是质数，所以上述方法全部废了。（1.4.1 时间复杂度显然不能接受,1.4.2 有可能出现没有逆元的情况,1.4.3 Lucas 定理不适用）

我们考虑转化问题：

设 \(p=p_1^{e_1}p_2^{e_2}\dots p_k^{e_k},(p_i\in prime)\)

那么我们只需要分别求出 \(C_n^m\) 对 \(p_1^{e_1},p_2^{e_2},\dots,p_k^{e_k}\)，然后 excrt 就好了。

那么我们如何求 \(C_n^m\%p^e\) 呢？

也就是 \(\frac{n!}{m!(n-m)!}\% p^e\)。

我们发现还是无法直接求，所以我们可以考虑把 \(p\) 的因子提出来单独算，其它的就可以求逆元了。

也就是说，问题转化成我们需要知道 \(n!\) 种含 \(p\) 的因子数量，以及其它因子的乘积。

我们可以这样算：对于某个阶乘

\[假设\ \ kp\le n<(k+1p\\ n!=1\times2\times\dots\times (p-1)\times (p+1)\times(p+2)\times\dots\times n\times p\times 2p\dots\times kp \]

我们发现前面的部分已经剔除了 \(p\) 的因子，可以求逆元了。而后面的可以每一项提一个 \(p\) 出来，这样我们获得了 \(k\) 个因子 \(p\)，剩下的就是 \(k!\)，可以递归下去。

那么这个问题就被解决了。

至此，你就可以拿下 P4720 【模板】扩展卢卡斯定理/exLucas。

int fac(int n,int p,int k){
   	if(!n)return 1;
   	int ans=1;
	for(int i=2;i<=k;i++)
		if(i%p)ans=ans*i%k;
	ans=qpow(ans,n/k,k);
	for(int i=2;i<=n%k;i++)
		if(i%p)ans=ans*i%k;
	return ans*fac(n/p,p,k)%k;
}
int C(int n,int m,int p,int k){
   	if(n1)ans=(ans+crt(C(n,m,t,t),t))%p;
	return ans%p;
}

如果模数 \(p\) 固定的话，可以把求阶乘的部分提前预处理一下，这样会更快一些。

评测记录

1.5 简单组合计数问题

组合计数是信息学数论中笔者认为比较困难的一个板块了。

我们先从一些经典问题入手吧。

问题 1.5.1（圆排列问题）：\(n\) 个人选 \(m\) 个人站成一圈的方案数。

我们发现这个一个环我们可以选择 \(n\) 个地方断开，也就是会在总排列中重复计算 \(n\) 次，所以答案为 \(\frac{A_n^m}n\)。

问题 1.5.2（插板法）：有 \(n\) 个完全相同的球，放进 \(m\) 个互不相同的盒子里，每个盒子至少放一个的方案数。

我们可以把 \(n\) 个球排成一排，然后会形成 \(n-1\) 个缝隙。

我们发现我们可以把 \(m-1\) 个隔板放进去，然后 \(m-1\) 个隔板就对应 \(m\) 个有序的箱子，相邻两个隔板中间的球放进一个箱子，每个箱子至少有一个球。（因为不能在一个缝隙放两个隔板）

发现两个事情是等价的，而放隔板的方案是 \(C_{n-1}^{m-1}\)，所以问题 1.5.2 的答案也是这个。

问题 1.5.2'（插板法）：有 \(n\) 个完全相同的球，放进 \(m\) 个互不相同的盒子里的方案数。

我们发现我们没有办法计算盒子不加限制的方案数，所以我们可以给每个盒子强制放一个球，分配完之后再拿走，这样就可以很好的处理这个限制了，答案就是 \(C_{n+m-1}^{m-1}\).

问题 1.5.2''（插板法）：有 \(n\) 个完全相同的球，放进 \(m\) 个互不相同的盒子里，每个盒子至少放 \(k\) 个的方案数。

同理，如果至少放 \(k\) 个，我们先每个箱子都拿出 \(k-1\) 个，分配完再放回去即可。（如果 \(k=0\)，就是问题 1.5.2'，每个箱子先放一个，分配完再拿走）所以答案为 \(C_{n-(k-1)m-1}^{m-1}\)。

问题 1.5.3（捆绑法）：\(n\) 个人拍照，排成一排坐着，但是有 \(m\) 对情侣 \((2m\le n)\)，每一对情侣都要求坐在一起拍照，求方案数。

我们把每一对情侣捆绑在一起，拍完之后一对情侣 AB 坐在了一起，但是他们两个可以换座位，所以每一对情侣会让答案乘以一个 \(2\)（乘法原理），所以答案就是 \((n-m)!2^m\)。

问题 1.5.4 （容斥）：\(n\) 个人拍照，排成一排坐着，有一对死对头，他们不能坐在一起，求方案数。

我们考虑容斥，答案等于总方案数减去死对头坐在一块的方案数，即 \(n!-2(n-1)!=(n-2)\times(n-1)!\)。

还有很多与组合数有关的容斥问题，不过比较复杂，我们再后面会见到的。

问题 1.5.5（Oiclass 大包子的算式）：有一个长度为 \(n\) 的数字串，里面放 \(k\) 个加号，算式两遍不允许有加号，求所有合法表达式的值的和对 \(1000000009\) 取模的结果，\(0\le k。

组合数入手好题，多种做法，这里介绍笔者想到的做法。

如果 \(k=0\) 直接判掉，接下来考虑 \(k\not=0\) 的情况。

我们把问题转化一下，求每一段数字的值乘上它出现次数。

对于一个长度为 \(i\) 的子串，如果它靠边，那么它的出现次数为 \(C_{n-i-1}^{k-1}\)，因为这一段中间不能填加号，边上要填一个，其他地方随意；

同理，如果不靠边，那它两遍都要放加号，出现次数为 \(C_{n-i-2}^{k-2}\)。

对于靠边的，靠左边或右边可以 \(O(n)\) 算出来，不靠边的，要对一样长度的子串一起考虑。

也就是我们要快速算出 \(\sum_{l=1}^{n-i+1}num[l,l+i-1]\)，我们可以考虑增量，假设我们已经求出了 \(i-1\) 对应的 \(s'\)，那么 \(s\) 相当于先扔掉最后面的一个，然后每一个剩下的再后面加一位。

预处理出前缀和，然后随便统计一下就好了。

signed main(){
	scanf("%lld%lld%s",&n,&k,s+1);
	if(k==0){
		int sum=0;
		for(int i=1;i<=n;i++)sum=(sum*10+s[i]-'0')%p;
		printf("%lld\n",sum);
		return 0;
	}
	fac[0]=ifac[0]=t[0]=1;
	for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%p;
	ifac[n]=qpow(fac[n]);
	for(int i=n-1;i>=1;i--)ifac[i]=ifac[i+1]*(i+1)%p;
	for(int i=1;i<=n;i++)t[i]=(t[i-1]*10)%p;
	for(int i=1;i<=n;i++)sum[i]=(sum[i-1]*10+s[i]-'0')%p;
	for(int i=1;i<=n;i++)sum2[i]=(sum2[i-1]+s[i]-'0')%p;
	int ans=0,S=0;
	for(int i=1;i1;i--){
		ans=(ans+(sum[n]-sum[i-1]*t[n-i+1]%p+p)%p*C(i-2,k-1))%p;
	}
	printf("%lld\n",ans);
}

评测记录

问题1.5.6（数位dp，P6669 [清华集训2016] 组合数问题），给出 \(n,m,k\)，求有多少 \(0\le i\le n,0\le j\le\min(i,m)\) 满足 \(C_i^j\) 是 \(k\) 的倍数，答案对 \(1000000009\) 取模。共 \(t\) 组数据，\(k\) 不变，题目保证 \(k\) 是质数，\(1\le n,m\le10^{18},1\le t,k\le 100\)。

其实就是 \(C_i^j\equiv 0(\bmod k)\) 的个数。

然后用 Lucas 定理拆开：\(C_n^m\equiv \prod C_{a_i}^{b_i}\)。

我们发现满足条件必须要这些组合数中必须要有某个 \(C_{a_i}^{b_i}=0\)，因为每个 \(a_i,b_i。

所以要有 \(a_i。

我们发现问题可以转化成两个 \(p\) 进制数 \(i,j\)，两个有上限，要求 \(i\ge j\)，某一位 \(a_l，然后跑数位 dp 就行了。

后面有机会讲 dp 的时候可能也会有这道题。

int n,m,t,k,f[N][2][2][2][2];
int an[N],am[N],t1,t2;
void add(int &x,int y){x=(x+y)%p;}
int dfs(int len,bool isok,bool tpn,bool tpm,bool tpij){
	if(!len)return isok;
	if(f[len][isok][tpn][tpm][tpij]!=-1)return f[len][isok][tpn][tpm][tpij];
	int res=0;
	int upn=tpn?an[len]:k-1,upm=tpm?am[len]:k-1;
	for(int i=0;i<=upn;i++)
		for(int j=min(upm,(tpij?i:upm));j>=0;j--)
			add(res,dfs(len-1,isok|(i

评测记录