声明：
本系列博客是《算法竞赛进阶指南》+《算法竞赛入门经典》+《挑战程序设计竞赛》的学习笔记，主要是因为我三本都买了 按照《算法竞赛进阶指南》的目录顺序学习，包含书中的少部分重要知识点、例题解题报告及我个人的学习心得和对该算法的补充拓展，仅用于学习交流和复习，无任何商业用途。博客中部分内容来源于书本和网络（我尽量减少书中引用），由我个人整理总结（习题和代码可全都是我自己敲哒）部分内容由我个人编写而成，如果想要有更好的学习体验或者希望学习到更全面的知识，请于京东搜索购买正版图书：《算法竞赛进阶指南》——作者李煜东，强烈安利，好书不火系列，谢谢配合。

---

下方链接为学习笔记目录链接（中转站）

学习笔记目录链接

---

ACM-ICPC在线模板

---

一、计数原理

1.加法原理

若完成一件事有$n$类，第i类有$a_i$中方法，那么完成这件事共有$a_1+a_2+\cdots +a_n$种方法。

2.乘法原理

若完成一件事$n$个步骤，第$i$个步骤有$a_i$种方法，那么完成这件事共有$a_1\times a_2\times \cdots \times a_n$种方法

3.减法原理

记S为全集，则|A| = |S|−|S\A|

常用于：当直接统计具有一种性质的事物个数较为困难时，考虑统计不 具有这种性质的事物个数，再用总数减去这个值。

例如：班上一共有$n$个同学，老师点名，到了$m$个，则有$n-m$个同学没来。

二、排列组合

1.排列数

从$m$个不同的元素中取出$n(0\le n\le m)$个元素排成一列的方法数。记作$A_m^n$。
我们可以一步一步的考虑这个问题，首先从$m$个小朋友中抽取一个放在第一个有m种方法。之后从剩下的$m-1$个中挑一个放在第二个即有$m-1$中方法。以此类推，根据乘法原理我们可以得到

$$A_m^n=\frac{m!}{(m-n)!}$$
注：$0!=1$

2.组合数

从$m$个不同的元素中取出$n(0\le n\le m)$个元素组成一组的方法数。记作$C_m^m$ 。 注意与排列不同的是不考虑顺序。

$$C_m^n=\frac{m!}{(m-n)!\times n!}$$

性质：

1. $C_n^m=C_n^{n-m}$
2. $C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$
3. $C_n^0+C_n^1+\cdots +C_n^n=2^N$
4. $C_n^0+C_n^2+C_n^4+\cdots =C_n^1+C_n^3+C_n^5\cdots =2^{n-1}$

3.数学题

$$(C_1^{2n})+(C_3^{2n})+\cdot \cdot \cdot +(C_{2n-1}^{2n})$$
$$=(C_0^{2n-1})+(C_1^{2n-1})+(C_2^{2n-1})+(C_3^{2n-1})+\cdot \cdot \cdot +(C_{2n-2}^{2n-1})+(C_{2n-1}^{2n-1})$$

$$=2^{2n-1}$$

三、组合数的计算

1. 加法递推$O(n^2)$

AcWing 885. 求组合数 I

$1\le n\le 100000,1\le b\le a\le 2000$

利用性质2，边界条件 $C_n^0=C_n^n=1$ ，其实就是杨辉三角(帕斯卡三⻆)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define debug(x) cout << x << "ok" << endl
using namespace std;
const int N = 2007, mod = 1e9 + 7;
const double eps = 1e-6;
typedef long long ll;int n, m;
int a[N];
int c[N][N];
//C(n, m) = C(n − 1, m) + C(n − 1, m − 1);
void init()
{for(int i = 0; i < N; ++ i){for(int j = 0; j < N; ++ j){if(!j)c[i][j] = 1;else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;}}
}int main()
{init();scanf("%d", &n);while(n -- ){int a, b;scanf("%d%d", &a, &b);printf("%d\n", c[a][b]);}return 0;
}

2. 乘法递推$O(n)$

$C_n^m=\frac{n-m+1}{n}\times C_n^{m-1}$，边界条件$C_n^0=1$。必须先乘后除，不然可能除不开

可以利用性质$1$，减少部分运算

c[0] = 1;
for( register int i = 1 ; i * 2 <= n ; i ++ ) c[i] = c[n-i] = ( n - i + 1 ) * c[ i - 1 ] / i;

AcWing 886. 求组合数 II

$1\le n\le 10000,1\le b\le a\le 10^5$

直接用公式 $C_m^n=\frac{m!}{(m-n)!\times n!}$ 求，把除转化为逆元。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define debug(x) cout << x << "ok" << endl
using namespace std;
const int N = 500007, mod = 1e9 + 7;
const double eps = 1e-6;
typedef long long ll;int fact[N];//阶乘
int infact[N];//阶乘的逆元
int qpow(int a, int b, int mod)
{int res = 1;while(b){if(b & 1)res = ((ll)res * a) % mod;a = ((ll)a * a) % mod;b >>= 1;}return res;
}int n, m;int main()
{fact[0] = infact[0] = 1;for(int i = 1; i < N; ++ i){fact[i] = (ll)fact[i - 1] * i % mod;infact[i] = (ll)infact[i - 1] * qpow(i, mod - 2, mod) % mod;}scanf("%d", &n);while(n -- ){int a, b;scanf("%d%d", &a, &b);printf("%d\n", (ll)fact[a] * infact[b] % mod * infact[a - b] % mod);}return 0;
}

3. Lucas定理

若$p$是质数，则对于任意的整数$1\le m\le n$，有：

$$C_n^m=C_{n\mathrm{m}\mathrm{o}\mathrm{d}p}^{m\mathrm{m}\mathrm{o}\mathrm{d}p}\times C_{n/p}^{m/p}(\mathrm{m}\mathrm{o}\mathrm{d}P)$$

$1\le n\le 20,1\le b\le a\le 10^{18},1\le p\le 10^5$

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>using namespace std;
typedef long long ll;
typedef pair<int , int> PII;
const int N = 10007, M = 500007, T = 1000, Mod = 1000003, INF = 0x3f3f3f3f;ll n, m, p;ll qpow(ll a, ll b, ll mod)
{ll res = 1;while(b) {if(b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}ll C(ll a, ll b, ll p)
{if(a < b)return 0;ll down = 1, up = 1;for(int i = a, j = 1; j <= b; i -- , ++ j) {up = up * i % p;down = down * j % p;}return up * qpow(down, p - 2, p) % p;
}ll lucas(ll a, ll b, ll p)
{if(a < p && b < p) return C(a, b, p);return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}int t;int main()
{scanf("%d", &t);while (t -- ) {//C(down, up) % p;//C(大, 小) % p;scanf("%lld%lld%lld", &n, &m, &p);printf("%lld\n", lucas(n, m, p) % p);}return 0;
}

4. 扩展卢卡斯

P4720 【模板】扩展卢卡斯

求 $C_m^{n}modp$，其中p不一定是质数

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define gc getchar
void exgcd(ll a, ll b, ll &x, ll &y) {if (!b)return (void)(x = 1, y = 0);exgcd(b, a % b, x, y);ll tmp = x;x = y;y = tmp - a / b * y;
}
ll gcd(ll a, ll b) {if (b == 0)return a;return gcd(b, a % b);
}
inline ll INV(ll a, ll p) {ll x, y;exgcd(a, p, x, y);return (x + p) % p;
}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;
}
inline ll mabs(ll x) {return (x > 0 ? x : -x);
}
inline ll fast_mul(ll a, ll b, ll p) {ll t = 0;a %= p;b %= p;while (b) {if (b & 1LL)t = (t + a) % p;b >>= 1LL;a = (a + a) % p;}return t;
}
inline ll fast_pow(ll a, ll b, ll p) {ll t = 1;a %= p;while (b) {if (b & 1LL)t = (t * a) % p;b >>= 1LL;a = (a * a) % p;}return t;
}
inline ll read() {ll x = 0, f = 1;char ch = gc();while (!isdigit(ch)) {if (ch == '-')f = -1;ch = gc();}while (isdigit(ch))x = x * 10 + ch - '0', ch = gc();return x * f;
}
inline ll F(ll n, ll P, ll PK) {if (n == 0)return 1;ll rou = 1; //循环节ll rem = 1; //余项for (ll i = 1; i <= PK; i++) {if (i % P)rou = rou * i % PK;}rou = fast_pow(rou, n / PK, PK);for (ll i = PK * (n / PK); i <= n; i++) {if (i % P)rem = rem * (i % PK) % PK;}return F(n / P, P, PK) * rou % PK * rem % PK;
}
inline ll G(ll n, ll P) {if (n < P)return 0;return G(n / P, P) + (n / P);
}
inline ll C_PK(ll n, ll m, ll P, ll PK) {ll fz = F(n, P, PK), fm1 = INV(F(m, P, PK), PK), fm2 = INV(F(n - m, P, PK), PK);ll mi = fast_pow(P, G(n, P) - G(m, P) - G(n - m, P), PK);return fz * fm1 % PK * fm2 % PK * mi % PK;
}
ll A[1001], B[1001];
//x=B(mod A)
inline ll exLucas(ll n, ll m, ll P) {ll ljc = P, tot = 0;for (ll tmp = 2; tmp * tmp <= P; tmp++) {if (!(ljc % tmp)) {ll PK = 1;while (!(ljc % tmp)) {PK *= tmp;ljc /= tmp;}A[++tot] = PK;B[tot] = C_PK(n, m, tmp, PK);}}if (ljc != 1) {A[++tot] = ljc;B[tot] = C_PK(n, m, ljc, ljc);}ll ans = 0;for (ll i = 1; i <= tot; i++) {ll M = P / A[i], T = INV(M, A[i]);ans = (ans + B[i] * M % P * T % P) % P;}return ans;
}
signed main() {ll n = read(), m = read(), P = read();printf("%lld\n", exLucas(n, m, P));return 0;
}

5. 大组合数（高精）

如果不让你膜，那么答案就会非常的大，需要用到高精算法。并且我们在求阶乘的时候可以将阶乘分解质因数再乘。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 5010;
int primes[N], cnt;
int sum[N];
bool st[N];
//线性筛素数；
void get_primes(int n)
{for (int i = 2; i <= n; i ++) {if (!st[i]) primes[cnt ++] = i;for(int j = 0; primes[j] <= n / i; j ++) {st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}
//得到n！中p的次数；
int get(int n, int p)
{int res = 0;while(n) {res += n / p;n /= p;//n每次除以p;}return res;
}
//高精度乘法；
vector<int> mul(vector<int> a, int b)
{vector<int> c;int t = 0;for(int i = 0; i < a.size(); i ++) {t += a[i] * b;c.push_back(t % 10);t /= 10;}while(t) {c.push_back(t % 10);t /= 10;}return c;
}
int main() {int a, b;cin >> a >> b;get_primes(a);for (int i = 0; i < cnt; i ++) {int p = primes[i];sum[i] = get(a, p) - get(b, p) - get(a - b, p);//得到C[a][b]中p的次数，因为是幂的形式，所以是减；}vector<int> res;res.push_back(1);//要先放进去一个1；for(int i = 0; i < cnt; i ++)for(int j = 0; j < sum[i]; j ++)res = mul(res, primes[i]);for(int i = res.size() - 1; i >= 0; i --) printf("%d", res[i]);return 0;}

6. 生成全排列

一些题目可能会给定一串数字，要求找到其中的某一个顺序，暴力的做法就是生存这个序列的全排列，然后暴力判断

这里提供一个$STL$来生成全排列next_permutation

next_permutation是生成当前序列的下一个序列，直到整个序列单调递减

int a[3];do
{for( register int i = 0 ; i < 3 ; i ++ ) cout << a[i] << ' ';cout << endl;
}while( next_permutation( a , a + 3 ) );

当然next_permutation也可以只针对某一段生成排列，修改参数即可，同时也支持自定义排序方式，类似sort

注意next_permutation操作的序列必须是单调递增，不然只能生成当前序列的下一个序列，无法生成所有的序列

7.枚举子集

将一个集合与一个二进制数对应,再将二进制数与十进制数对应.为了方便操作,单词的编号也可以从$1\dots N,改成0\dots N-1$比如：集合$[1,4,5]->$集合$[0,3,4]->11001(2)->2^0+2^3+2^4=25$.这样操作不但节省了空间,而且在进行集合操作时可以用位操作,又节省了时间.
这样用一个数的二进制来表示一个集合，可以用下面的方法生成当前集合的所有子集，并能做到不重不漏

for(int i = s ; i ; i = ( i - 1 ) & s );

出自JSOJ 2003论文《浅谈记忆化搜索》 - 吴景岳

四 、二项式定理

$$(a+b{)}^n=\sum _{k=0}^n{C}_n^k{a}^k{b}^{n-k}$$

NOIP2011计算系数

来自y总的代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#define ls (p<<1)
#define rs (p<<1|1)
//#pragma GCC optimize (2)
//#pragma G++ optimize (2)
#define over(i,s,t) for(register int i = s;i <= t;++i)
#define lver(i,t,s) for(register int i = t;i >= s;--i)
//#define int __int128
#define lowbit(p) p&(-p)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;const int N = 1007;
const int mod = 1e4+7;
const double EPS = 1e-10;
const int base = 131;
int qpow(int a,int b){a %= mod;int res = 1;while(b){if(b&1)res = (res*a) % mod;a = (a*a)%mod;b >>=1;}return res ;
}int a,b,k,n,m;
int main()
{scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);int res = qpow(a,n)*qpow(b,m)%mod;for(int i = 1,j = k;i<=n;++i,--j){res = res * j %mod;res = res *qpow(i,mod - 2) %mod;}printf("%d\n",res);return 0;
}

五、多重集

设多重集合 S = { n 1 ∗ a 1 , n 2 ∗ a 2 , . . . , n k ∗ a k } , n = n 1 + n 2 + . . . + n k S = \{ n1 * a1, n2 * a2, ..., nk * ak \},n = n_1 + n_2 + ... + n_k S={n1∗a1,n2∗a2,...,nk∗ak},n=n1​+n2​+...+nk​,

即集合 S 中含有$n_1$个元素$a_1$， $n_2$个元素$a_2$，…，$n_k$个元素$a_k$，$n_i$被称为元素$a_i$的重数，$k$成为多重集合的类别数

在 S 中任选 r 个元素的排列称为S的r排列，当$r=n$时，有公式$$\frac{n!}{n_1!\ast n_2!\ast ...\ast n_k!}$$

在 S 中任选 r 个元素的组合称为S的r组合，当r<=任意ni时，有公式$$C_{k+r-1}^{k-1}$$

由公式可以看出多重集合的组合只与类别数k 和选取的元素r 有关，与总数无关

多重集合的排列和组合问题

AcWing 212. 计数交换

六、Catalan数列

给定$n$个$0$和$n$个$1$,他们按照某种顺序排列成长度为$2n$的序列，满足任意前缀中$0$的个数都不少于$1$的个数的序列的数量为

$$Ca{t}_n=\frac{C_{2n}^n}{n+1}$$

推论：
以下问题都与Catalan数有关

1. $n$个左括号和$n$个右括号组成的合法序列的数量为$Ca{t}_n$
2. $1,2,3,\cdots ,n$经过一个栈形成的合法出栈顺序的数量为$Ca{t}_n$
3. $n$个节点构成不同的二叉树的数量为$Ca{t}_n$
4. 在平面直角坐标系上，每一步只能向上走或向右走，从$(0,0)$走到$(n,n)$并且除两个端点外不接触直线$y=x$的路线数量为$2Ca{t}_{n-1}$

AcWing 889. 满足条件的01序列

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define debug(x) cout << x << "ok" << endl
using namespace std;
const int N = 200007, mod = 1e9 + 7;
const double eps = 1e-6;
typedef long long ll;int n, m;
int fact[N], infact[N];int qpow(int a, int b, int mod)
{int res = 1;while(b){if(b & 1)res = (ll)res * a % mod;a = (ll)a * a % mod;b >>= 1;}return res;
}void init()
{fact[0] = infact[0] = 1;for(int i = 1; i < N; ++ i){fact[i] = (ll)fact[i - 1] * i % mod;infact[i] = (ll)infact[i - 1] * qpow(i, mod - 2, mod) % mod;}  
}int main()
{init();scanf("%d", &n);int res = (ll)fact[2 * n] * infact[n] % mod * infact[n] % mod * qpow(n + 1, mod - 2, mod) % mod;printf("%d\n", res);return 0;
}

七、计数技巧

等价替代

当我们需要计算一些带特殊条件的方案数时，可以用一些等价替代的方 法。具体来讲，我们构造一个双射（一一映射），将每一种原问题的方案 映射为新问题的一种方案，并使答案更容易计算。 常用的有捆绑法、插空法、隔板法等。

1.捆绑法

也称整体法，在计数时，如果要求若干物品相邻，则可以将它们作为一 个整体来进行计数。

例如：ABCDE五个人要排队，A和B要相邻，C和D要相邻，求有 多少种排列方法。 首先将AB、CD分别看成一个整体，然后变成3个元素的排列问题， 方案数为$3!=6$，然后考虑AB、CD内部的相对顺序，共有4种情况， 最终答案为$6\times 4=24$。

2.插空法

如果要求若干物品两两不相邻，可以先将其他物品放好，然后将这些物 品插入空当中，进行计数。

例如：ABCDEFG七个人要排队，ABC三个人两两不相邻，求方案数。 先将剩下四个人排好，有4! = 24种方案；然后将ABC三个人插入5 个空当中，有$5\times 4\times 3=60$种方案，最终答案为$24\times 60=1440$。

3.隔板法

将不可区分物品分配问题/不定方程整数解问题转化为插板组合问题。

例如：把n个相同的苹果分给k个人，要求每个人至少分到一个，求方 案数。 我们把这n个苹果摆成一排，从左往右依次插入$k-1$块隔板，代表每 个人分到的部分，而每种插板的方案和原来的每一种分配方案是一一对 应的，$k-1$块隔板插入n−1个空当中（不能插在最左和最右），所以 最终答案为 $C_{k-1}^{n-1}$

如果改一改原问题，允许有人分到0个，那么答案应该怎么改呢？ 刚才的问题可以抽象为数学模型：求方程 $x1+x2+\cdot \cdot \cdot +xk=n$ 的整数解，满足xi ≥ 1。 如果限制改成xi ≥ 0，我们可以设k个新变量$yi=xi+1\ge 1$，转化为 求方程 $y1+y2+\cdot \cdot \cdot +yk=n+k$ 的整数解，结合刚才的结论，得到答案 $C_{k-1}^{n+k-1}$