参考文献

• 矩阵笔记——孙小麦
• 省选数学基础——张佳瑞
• 清北学堂笔记——赵化哲
• 学习笔记-矩阵——孙亦泽
• 清北学堂五一数学营笔记——孙亦泽
• 胡家瑞的手写笔记
• 高域卬的手写笔记
• LaTex常用技巧6：矩阵编写总结——“小林up”
• LaTeX 数学公式大全——“Iowa_BattleShip”
  感谢以上内容，对这份笔记的完善做出巨大贡献。

模运算

这个笔记所有的 $\mathrm{\%}$ 均表示模运算。

带余除法

考虑 $a÷b=c...d$。

• $a=bc+d$
• $0\le d<b$
• c=a/b，d=a%b
• $(a+b)\mathrm{\%}c=a\mathrm{\%}c+b\mathrm{\%}c$，减法、乘法同理。
  • 证明：设 $a=k_{1}c+a^{\prime },b=k_{2}c+b^{\prime }$，则左式和右式均可以化为 $(a^{\prime }+b^{\prime })\mathrm{\%}c$。

新手题

1

给定 $a,b,c$，求 $a+b,a-b,a\times b\mathrm{\%}c$ 的值。保证 $a,b,c$ 在 int 范围内。

• 标准错误写法：

#include<iostream>
#define ll long long
using namespace std;
int a,b,c; 
int main(){
	cin>>a>>b>>c;
	cout<<(a+b)%c<<endl;
	cout<<(a-b)%c<<endl;\\(1)
	cout<<(a*b)%c<<endl;\\(2)
	return 0;
}

• 其中 (1) 处 $a-b$ 可能小于 $0$，于是又一种错误的改法出现了：cout<<abs(a-b)%c<<endl;。
  • 这么一改，直接把数给变了，答案能对吗？？！
  • 所以正确的改法为：cout<<((a-b)%c+c)%c<<endl;。
• (2) 处可能会炸 int，这里可以开 long long，也可以先乘上 1ll，还可以直接用上面的规律。

2

给定 $n,p$，求 $n!\mathrm{\%}p$。$n\le 1000$。

• 又一个标准错误写法：

#include<iostream>
#define ll long long
using namespace std;
ll n,p,ans=1; 
int main(){
	cin>>n>>p;
	for(int i=1;i<=n;i++){
		ans*=i;
	}
	cout<<ans%p; 
	return 0;
}

• 此处同上面的 (2)，也会炸 int，而且会炸 long long。于是就只能用规律了。正确代码如下：

#include<iostream>
#define ll long long
using namespace std;
ll n,p,ans=1; 
int main(){
	cin>>n>>p;
	for(int i=1;i<=n;i++){
		ans*=i%p;
		ans%=p;
	}
	cout<<ans; 
	return 0;
}

$\text{gcd}$ 和 $\text{lcm}$

定义：$\text{gcd}$ 就是最大公约数，$\text{lcm}$ 是最小公倍数。

注：$gcd(a,0)=a$。

整除符号

$b|a$ 表示 $a\mathrm{\%}b=0$。

$gcd$ 的性质

$gcd(a,b)=gcd(a\mathrm{\%}b,b)$。

证明：

$gcd(a,b)$
$=gcd(a-b,b)$
$=gcd(a-2b,b)$
$...$
$=gcd(a\mathrm{\%}b,b)$。

于是就有了：

辗转相除法求 $gcd$

使用性质，不断把 $gcd(a,b)$ 变成 $gcd(a\mathrm{\%}b,b)$（$a\ge b$）即可。

代码：

int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}

时间复杂度：$\text{O}(\log a)$

• 原因很简单：
  • $b\le a<2b$ 时，$a\mathrm{\%}b=a-b$，显然小于 $\frac{a}{2}$；
  • $2b\le a$ 时，因为余数小于除数，而除数又不超过$\frac{a}{2}$，所以 $a\mathrm{\%}b<\frac{a}{2}$；
• 综上，$a\mathrm{\%}b<\frac{a}{2}$，所以时间复杂度不超过 $\log$。

求多个数的 $gcd$ 复杂度：$\text{O}(n\log max(a_i))$。

$\text{lcm}$ 的性质与求法

性质：如果 $gcd(a,b)=g,\text{lcm}(a,b)=l$，则 $ab=gl$。

所以求法：$\text{lcm}(a,b)=a\times b÷gcd(a,b)$。

但是 $ab$ 容易炸，所以要用 $\text{lcm}(a,b)=a÷gcd(a,b)\times b$。

快速幂

提交的题目

给定 $a,n,p$，求 $a^n\mathrm{\%}p$。$a,b,p\le 2^{31}$。

首先暴力肯定是不行的，$n$ 的复杂度直接升天。

于是我们考虑拆开。例如：

$x^{37}=(x^{18}{)}^2+x=((x^9{)}^2{)}^2+x=(((x^4{)}^2+x{)}^2{)}^2+x=((((x^2{)}^2{)}^2+x{)}^2{)}^2+x=((((x\times x{)}^2{)}^2+x{)}^2{)}^2+x$

于是一波地龟就完事了。代码：

ll ksm(ll x,ll y,ll p){
//x^y%p
	if(y==0)return 1;
	ll z=ksm(x,y/2,p);
	z=1ll*z*z%p;
	if(y%2)z=z*x%p;
	return z;
}

这里我们也可以用相同的思想求大数加法。代码略。

矩阵

定义

一个 $n$ 行 $m$ 列的二维数组。

运算

加减法：对应数字加减。

$\left[\begin{array}{}1& 2\\ 3& 4\end{array}\right]+\left[\begin{array}{}5& 6\\ 7& 8\end{array}\right]=\left[\begin{array}{}1+5& 2+6\\ 3+7& 4+8\end{array}\right]=\left[\begin{array}{}6& 8\\ 10& 12\end{array}\right]$

矩阵乘数字：所有的数字全部乘。

$\left[\begin{array}{}1& 2\\ 3& 4\end{array}\right]\times 6=\left[\begin{array}{}1\times 6& 2\times 6\\ 3\times 6& 4\times 6\end{array}\right]=\left[\begin{array}{}6& 12\\ 18& 24\end{array}\right]$

矩阵乘矩阵

要求第一个矩阵的列数等于第二个矩阵的行数。结果的矩阵行数为第一个的行数，列数为第二个的列数。

算第 $i$ 行第 $j$ 列的数时，取第一个矩阵的第 $i$ 行和第二个矩阵的第 $j$ 列，将对应位置的数字相乘后相加即可。

$\left[\begin{array}{}1& 2\\ 3& 4\end{array}\right]\times \left[\begin{array}{}1& 1& 4\\ 5& 1& 4\end{array}\right]=\left[\begin{array}{}1\times 1+2\times 5& 1\times 1+2\times 1& 1\times 4+2\times 4\\ 3\times 1+4\times 5& 3\times 1+4\times 1& 3\times 4+4\times 4\end{array}\right]=\left[\begin{array}{}11& 3& 12\\ 23& 7& 28\end{array}\right]$

写法

加减法及数乘略。

乘法：这里采用结构体和重载来写。

结构体

struct matrix{
	ll n,m;
	ll a[233][233];
	matrix(){//(1)
		n=m=0;
		memset(a,0,sizeof(a));
	}
};
matrix m1,m2,m3;

代码中 (1) 处是构造函数，无需调用，定义结构体就会自动运行。

重载运算符

matrix operator*(matrix &m1,matrix &m2){
	matrix m3;
	m3.n=m1.n;m3.m=m2.m;
	for(int i=0;i<m3.n;i++){
		for(int j=0;j<m3.m;j++){
			for(int k=0;k<m1.m;k++){
				m3.a[i][j]+=m1.a[i][k]*m2.a[k][j];
			}
		}
	}
	return m3;
}

但此时我们会发现两个 matrix 如果改动的话，就会寄掉，然后被zhx笑一坤年，因此我们需要加个 const，于是就成了：

matrix operator*(const matrix &m1,const matrix &m2){
	matrix m3;
	m3.n=m1.n;m3.m=m2.m;
	for(int i=0;i<m3.n;i++){
		for(int j=0;j<m3.m;j++){
			for(int k=0;k<m1.m;k++){
				m3.a[i][j]+=m1.a[i][k]*m2.a[k][j];
			}
		}
	}
	return m3;
}

加个输入，就大功告成了。

矩阵快速幂

引入——斐波那契

首先都知道斐波那契数列的递推式：$f_n=f_{n-1}+f_{n-2}$。

于是我们准备两个矩阵：

$A=\left[\begin{array}{}{f}_{n-1}& f_{n-2}\end{array}\right],B=\left[\begin{array}{}1& 1\\ 1& 0\end{array}\right]$

于是……

$A\times B=\left[\begin{array}{}{f}_n& f_{n-1}\end{array}\right]$

可这除了更慢，有什么用呢？

我们知道开始的 $A_1=\left[\begin{array}{}1& 0\end{array}\right]$，设结果为 $C$，则 $C_n=\left[\begin{array}{}{f}_n& f_{n-1}\end{array}\right]=A_1\times \stackrel{\text{n-1 个 B}}{\overbrace{B\times B\times ...\times B}}$。

你想到了……

乘法有快速幂，那矩阵乘法呢？

我们只需要把两个板子塞到一个代码里，变成这样：

struct matrix{
	ll n,m;
	ll a[2][2];
	matrix(){//(1)
		n=m=0;
		memset(a,0,sizeof(a));
	}
};
ll n,p;
matrix m1,m2,tmp,ans;
matrix operator*(const matrix &m1,const matrix &m2){
	matrix m3;
	m3.n=m1.n;m3.m=m2.m;
	for(int i=0;i<m3.n;i++){
		for(int j=0;j<m3.m;j++){
			for(int k=0;k<m1.m;k++){
				m3.a[i][j]+=m1.a[i][k]*m2.a[k][j];
				m3.a[i][j]%=p;
			}
		}
	}
	return m3;
}
matrix ksm(matrix x,ll y){
	if(y==0)return tmp;
	matrix z=ksm(x,y/2);
	z=z*z;
	if(y%2)z=z*x;
	return z;
}

然后你就过了一黄一绿。

例题

口胡题：走 $k$ 步到点 $n$，求方案数。$n\le 100,k\le {10}^9$。

用 $z_{i,j}$ 记录 $i,j$ 间有没有边， $1$ 有 $0$ 没有。$fi,j$ 表示走了 $i$ 步到 $j$ 的方案数。先将走 $0$ 步到的点全飙为 $0$ 即 $\mathrm{\forall }1<i\le n{f}_{0,i}=0$，$f_{0,1}=1$，转移时 $f_{i,j}=f_{i-1,p1}+f_{i-1,p2}+...$ 其中 $p$ 是一步能到的点的编号。这样复杂度是 $\text{O}(n^{2}k)$ 的，直接超时。

我们考虑加一个维度 $d$，让其始等于 $1$。将 $f_i$ 看成一个变量则原式等于 $f_i[d][j]=f_{i-1}[i-1][p]\times z[p][j]$。

于是 $f_i=f_{i-1}\times z=f_0\times z^i$ 然后题目就变成了矩阵快速幂。

P1962 斐波那契数列

P3390 【模板】矩阵快速幂

这两个题就是上面说的“一黄一绿”。

P4159 [SCOI2009] 迷路

我们考虑把这个题变成刚才的口胡题，也就是把带权的图，变成一个边权均为 $1$ 的图。但这样的话边数将会超级多，于是又双叒叕超时了。

考虑合并边：

然后就变成了刚才的口胡题。

P1349 广义斐波那契数列

数论基础

素数的判定

不说了，很简单。重点在为什么可以循环到 $\sqrt{x}$：因为如果一个因数大于 $\sqrt{x}$，那 $\frac{x}{\text{这个因数}}<\sqrt{x}$。

常见死法：

for(int i=2;i<=sqrt(x);i++)

死因很明显：每跑一次都要算一次 $\sqrt{x}$，于是复杂度无端乘了个 $\log x$。但这玩意一般不致命。一个关于字符串的更加常见也更加致命的死法是：

for(int i=1;i<=strlen(s);i++)

我求 $|s|$ 遍 $|s|$，直接变成 $|s{|}^2$，T 飞了。

逆元

PAY ATTENTION

只有 $a,p$ 互质，才有逆元。——张家瑞

引入——取模

$(3+4)\mathrm{\%}5=2$

$(3-4)\mathrm{\%}5=-1+5=4$

$(3\times 4)\mathrm{\%}5=2$

$(3÷4)\mathrm{\%}5=???$

对于 $(a÷b)$，我们要找到一个数 $c$，使得原式 $=ac$，此时 $c$ 就是 $b$ 的逆元。

费马小定理

内容：当 $p$ 是质数，$gcd(a,p)=1$ 时有 $a^{p-1}\equiv 1(\mathrm{mod}p)$。

证明：

• 两边同除以 $a$ 得到 $a^{p-2}\equiv \frac{1}{a}(\mathrm{mod}p)$。
• 于是原来的 $(a÷b)$ 便成了 $a{b}^{p-2}\mathrm{\%}p$。一波快速幂就结束了。

欧拉定理

内容：当 $gcd(a,p)=1$ 时有 $a^{\varphi (p)}\equiv 1(\mathrm{mod}p)$。

证明：

• 将费马小定理进行拓展，现在没有 $n$ 是质数，只有 $a,n$ 互质。

欧拉函数 $\varphi$

$\varphi (p)$ 即 $[1,p]$ 中与 $p$ 互质的数的个数。定义式为 $\varphi (n)=\sum _{i=1}^n[gcd(n,i)=1]$。

计算式：

• $\varphi (n)=n\prod \frac{p_i-1}{p_i}$
  • 如果 $n$ 有 $1$ 个质因子：
    • $n=p_1$ 时 $\varphi (n)=p_1-1$；
    • $n=p_1^2$ 时所有 $p_1$ 的倍数全都不互质，即 $\varphi (n)=p_1^2-p_1-1$。
    • 以此类推，当 $n=p_1^k$ 时，$\varphi (n)=n·{\displaystyle \frac{p_1-1}{p_1}}$。
  • 如果 $n$ 有 $2$ 个质因子：
    • 一波容斥，$\varphi (n)=n-\frac{n}{p_1}-\frac{n}{p_2}+\frac{n}{p_1{p}_2}=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})$。
  • 从上面的规律中可以推出计算式。

线性求逆(I)

1. 算出 $[1,n]!$；
2. 再求出每一个阶乘的逆元 $ifa{c}_i=ifa{c}_{i+1}\times (i+1)\mathrm{\%}p$；
3. 最后求本数的逆元 $in{v}_i=fa{c}_{i-1}\times ifa{c}_i\mathrm{\%}p$ 即可。

咕咕咕

线性求逆(II)

咕咕咕

Exgcd

求解方程 $ax+by=c$。显然有解的条件为 $c$ 是 $gcd(a,b)$ 的倍数。

两边同除以 $gcd(a,b)$ 得到一个方程 $a^{\prime }x+b^{\prime }y=c^{\prime }$。因为 $c^{\prime }$ 可能是任意整数，所以我们要证 $a^{\prime }x+b^{\prime }y$ 也能取遍任意整数。又因为 $gcd(a^{\prime },b^{\prime })=1$，$c^{\prime }$ 是 $gcd(a^{\prime },b^{\prime })$ 的倍数（也就是 $c^{\prime }$ 可以取任意整数），所以显然成立。

Miller-Rabin 素性测试

靠脸吃饭的素数判定算法。

如果 $n$ 为素数，取 $a<n$，设 $n-1=d\times 2^r$，则要么 $a^d\equiv 1(\mathrm{mod}n)$，要么存在 $0\le i<r$ 满足 $s·t·a^{d\times 2^i}$。

只需要找几十个数字，挨个跑一遍判定就可以了。如果跑 $k$ 个复杂度就是 $k\log n$。代码如下：

int n;
const int NUM=50;
int ksm(int a,int b,int mod){
    if(b==1)return a;
    int t=ksm(a,b/2);
    if(b%2==1)return ((t*t)%mod*a)%mod;
    else return (t*t)%mod;
}
bool Miller_Rabin(int n,int a){
    int d=n-1,r=0;
    while(d%2==0)d/=2,r++;
    int t=ksm(a,d,n);
    if(t==1)return 1;
    for(int i=0;i<r;i++){
        if(t==n-1)return 1;
        t=(t*t)%n;
    }
    return 0;
}
bool check(int n){
    if(n<2)return 0;
    for(int i=1;i<=NUM;i++){
        int a=rand()%(n-1)+1;
        if(!Miller_Rabin(n,a))return 0;
    }
    return 1;
}

中国剩余定理

引入——韩信点兵

韩信点兵，三三数之余一，五五数之亦余一，七七数之仍余一，问兵几何？

做法

考虑下面的方程组：

$\{\begin{array}{l}x\mathrm{\%}{a}_1=m_1\\ x\mathrm{\%}{a}_2=m_2\\ ...\\ x\mathrm{\%}{a}_n=m_n\end{array}$

• 我们要解的话，有一种很简单的方法：所有的两两分组解一下；解完之后的再分组解一次，直到就剩一个方程了。于是问题转化为解两个同余方程。
  • 枚举：$a_1,a_1+m_1,a_1+2m_1,...,a_1+p_1{p}_2$，直到枚举的值满足第二个方程。最多枚举 $p_2$ 次（没解）。
  • 卡常小大妙招：当 $p_1<p_2$ 时交换两个方程，于是这种方法就有个名字：大数翻倍法。
  • 时间复杂度：$\text{O}(min(p_1,p_2))$。
    • 但值得注意的一点是：答案一般不会炸 long long$({10}^{18})$。
    • 但是答案是所有 $p$ 的 $\text{lcm}$。而为了好做，一般 $p$ 都是互质的。
    • 这意味着，$\mathrm{\Pi }{p}_i\le {10}^{18},\mathrm{\forall }{p}_i\ge {10}^9$，也就是 $n$ 必须小于 $3$。
    • 所以你是死不掉的。
    • 于是你就过了一个蓝题（注：由于数据水，下文提及的紫题也能过，但其正常情况下显然不对）。
  • 代码：

• 正统做法
  • 这个做法可以过紫题。

筛法

引入——那次模拟赛

一个夜晚的模拟赛中，你看到了一个题目：

给定一个 $n$，请找出 $[1,n]$ 中的所有质数。

你的脑中浮现了两个思路：

• 暴力：复杂度是 $n\sqrt{n}$ 的。
• 想到之前学的 Miller-Rabin，复杂度提升到了 $n\log n$。

你往下滚动着页面，直到看到……

数据规模与约定
对于 $20\mathrm{\%}$ 的数据，$1\le n\le {10}^4$。
对于 $50\mathrm{\%}$ 的数据，$1\le n\le {10}^5$。
对于 $80\mathrm{\%}$ 的数据，$1\le n\le 2\times {10}^6$。
对于 $100\mathrm{\%}$ 的数据，$1\le n\le {10}^7$。

“这么厉害的 Miller-Rabin，居然才能得 $50$ 分？？！”你不由得喊了出来，“这出题人是喝 DDV 了吗？”

于是，你打开了百度……

埃氏筛

显然对于每一个质数，其倍数全都不是质数。所以我们考虑开一个 bool 数组 $a$，$a_i$ 表示 $i$ 是不是质数。只要还没被标记的就是质数（因为它不是比它小的所有质数的倍数），比它大的所有倍数全部应标记为非质数。时间复杂度是 $\text{O}(n\log \log n)$。

“啊？这都只有 $80$ 分？这题想满分到底多难？”

欧拉（线性）筛

埃氏筛的 $\log \log n$ 是哪里来的呢？能优化掉吗？

很显然，尽管是埃氏筛，其还是有可能出现一个数被筛多次的情况，例如 $210=2\times 3\times 5\times 7$。埃氏筛的 $\log \log n$ 就来自这里。所以优化的核心就是让每个数字只会被其最小的因数筛一次。

核心代码：

for(int i=2;i<n;i++){
	if(not_prime[i]==false){
		cnt++;
		prime[cnt]=i;
	}
	for(int j=1;j<=cnt;j++){
		int x=prime[j]*i;
		if(x>n)break;
		not_prime[x]=1;
		if(i%prime[j]==0)break;
	}
}

你长舒了一口气。这 $100$ 分真是来之不易啊。你望着排名，得意的笑了。

全剧终。

拓展：积性函数和完全积性函数

定义

积性函数：当 $gcd(a,b)=1$ 时 $f(a)=f(b)$ 的函数。

完全积性函数：对于定义域内任意 $a,b$ 均满足 $f(a)=f(b)$ 的函数。

为什么 $\varphi$ 是积性函数？

证法一：由计算式即可得到。这里不再赘述。

证法二：

如何求一组连续的 $\varphi$？

咕咕咕

Baby Step Giant Step（也叫 BSGS、北上广深、拔山盖世、小步大步）算法

引入——小破题

给定 $a,b,p$，其中 $p$ 为质数，解方程 $a^x\equiv b(\mathrm{mod}p)$。

一波暴力：从 $1$ 开始枚举 $x$，然后算完 $$ 就可以了。复杂度 $\text{O}(\text{答案})$，原地升天。

由 $p$ 为质数联想到费马小定理，所以极端复杂度是 $\text{O}(p)$ 的，还是有亿点点慢。

更加聪明的做法？

考虑把 $a_0,a_1,a_2,...,a_{p-2},a_{p-1}$ 分组。假设每组有 $s$ 个数。

$\{\begin{array}{l}\text{1:}{a}_1,a_2,...,a_s\\ \text{2:}{a}_{s+1},a_{s+2},...,a_{2s}\\ ...\text{k:}{a}_{(k-1)s+1},a_{(k-1)s+2},...,a_{ks}\end{array}$

将第一组每个数字遍历一遍。如果 $b$ 在其中则结束，否则下一组。

但这不与上面的一样吗？

发现第二组每一项等于第一组对应项 $\times a_s$，移项得第一组等于第二组 $\times a^{-s}$。

若第 $k$ 组中存在 $b$，就可以转换为 $b\times a^{-ks}$，则本题转换为一个数 $b$ 经过转换是否存在于第一组中。

也就是说，如果第 $i$ 组存在 $b$，那第一组肯定有 \(\dfrac{b}{a^{s(i-1)}\)。

这样我们就只需要把第一组扫一遍，然后枚举出现 $p$ 的组即可。第一个操作是 $\text{O}(s)$ 的，第二个是 ${\displaystyle \frac{p}{s}}$ 的，相当于复杂度为 $min(s,{\displaystyle \frac{p}{s}})$ 的。所以 $s={\displaystyle \frac{p}{s}}$ 即 $s=\sqrt{p}$ 时最优。代码：

ll a,b,p;
ll ksm(ll a,ll b,ll p){
    ll res=1;
    a%=p;
    while(b){
        if(b&1)res=res*a%p;
        a=a*a%p,b>>=1;
    }
    return res;
}
ll solve(ll a,ll b,ll p){
    // 求解 a^x % p = b
    ll s=sqrt(p),val=1;
    set<ll>S;
    for(int i=0;i<s;++i){
        S.insert(val);
        val=val*a%p;
    }
    for(int i=0;1ll*i*s<=p;++i){
        // 查找第 i 组（从 0 开始，这样就查找 b/a^si 即可）
        ll inv=ksm(a,i*s,p);
        ll tmp=b*ksm(inv,p-2,p)%p;
        if(S.count(tmp)){
            // inv 就是第 i 行的第一个数
            for(int j=i*s;;++j){
                // 暴力查找第 i 组中满足条件的数
                if(inv==b)return j;
                inv=inv*a%p;
            }
        }
    }
    return -1;
}

组合数学

加法原理与乘法原理

引入——走路

(1) 从甲地到乙地，有两班飞机和三班火车，有几种走法？

解：$2+3=5\text{（种）}$。

(2) 从甲地到乙地，有两班飞机；从乙地到丙地，有三班火车；一共有几种走法？

解：$2\times 3=6\text{（种）}$。

为什么 (1) 用加法而 (2) 用乘法捏？

一般地，像 (1) 中同时只能选一个的，使用加法原理；像 (2) 中能同时选两个的，使用乘法原理。

排列与组合

引入——选人排队

（1）从 $n$ 个人中选 $m$ 个人，有多少种选法？

答：$C_n^m$ 种。

（2）从 $n$ 个人中选 $m$ 个人排成一队，有多少种排法？

答：$P_n^m$ 种。

所以 $C_n^m$ 咋求呢？

$C_n^m={\displaystyle \frac{P_n^m}{m!}}={\displaystyle \frac{n!}{m!(n-m)!}}$。这个式子叫做组合数的定义式。

$={\displaystyle \frac{P_n^m}{m!}}$ 这一步很好理解，因为 $m$ 种的全排列是 $m!$ 种，而我们不考虑顺序，于是就是 ${\displaystyle \frac{\text{排列的种数}}{m!}}$。

一些东西

定义式

在引入部分都有了。

$C_n^m={\displaystyle \frac{n!}{m!(n-m)!}}$，$P_n^m={\displaystyle \frac{n!}{(n-m)!}}$。

组合数的性质

• $C_n^m=C_n^{n-m}$。同样不难理解，选 $m$ 个就相当于选 $n-m$ 个不选。
• $\stackrel{\mathrm{选}\mathrm{任}\mathrm{意}\mathrm{多}\mathrm{个}\mathrm{东}\mathrm{西}}{\overbrace{C_n^0+C_n^1+C_n^2+...+c_n^n}}=2^n$。显然每个东西都有选和不选两种情况，而每个东西之间相互独立。于是就是 $2^n$ 了。同理，我们发现：杨辉三角中第 $i$ 行之和等于 $2^{n-1}$。
• 当 $n\ge 1$ 时，$C_n^0-C_n^1+C_n^2+...C_n^n=0$。
  • $n$ 为偶数时，显然可以直接抵消。
  • $n$ 为奇数时，我们考虑杨辉三角：
  • 
    • 杨辉三角的每个数字等于上一行左右两个数字之和。
    • 当 $n$ 为奇数时，第 $n$ 行所有奇数位置（红色）之和等于第 $n-1$ 行所有数字之和；所有偶数位置（绿色）之和也等于上一行的数字之和。于是一减全没了。

组合数递推式

$C_n^m=C_{n-1}^{m-1}+C_{n-1}^m$。

理解：考虑第一个选或者不选。如果选就是在其余 $n-1$ 个里选 $m-1$ 个；不选就是在这 $n-1$ 个里选 $m$ 个。

二项式定理

$(x+y{)}^n=C_n^0{x}^n{y}^0+C_n^1{x}^{n-1}{y}^1+C_n^2{x}^{n-2}{y}^2+...+C_n^n{x}^0{y}^n=\sum _{i=0}^n{C}_n^i{x}^{n-i}{y}^i$。很好理解，不再赘述。

例题

数学题

$[1,n]$ 中选 $m$ 个数（不计顺序），每个数可以选任意多次。求方案数？

• $n^m$？
  • 显然不对，这叫不计顺序？
• $C_{nm}^m$？
  • 此时同一个数字被复制多次，但同一个数字被复制到不同的位置时会当成不同的数字，所以还是不对。
• 正解
  • 考虑选 $m$ 个数字并排序。
    • 如果不能重复，那选出来的 $a_1,a_2,a_3,...,a_m$ 就应满足不等式 $1\le a_1<a_2<...<a_m\le n$，而我们知道这个不等式的解有 $C_n^m$ 组。
    • 而加上能重复的条件之后，不等式就成了 $1\le b_1\le b_2\le ...\le b_m\le n$。我们希望将其转化为上面的不等式。
    • 考虑一组数字 $c_1,c_2,c_3,...,c_m$，其中 $c_1=b_1,c_2=b_2+1,c_3=b_3+2,...,c_m=b_m+m-1$。
    • 于是我们也可以列出一个不等式：$1\le c_1<c_2<c_3<...<c_m\le n+m-1$。
    • 然后用与关于 $a$ 的不等式相同的方法得到这个不等式的解有 $C_{n+m-1}^m$ 组，而这个不等式每一组解就对应了 $b$ 的不等式的一组解，所以答案就是 $C_{n+m-1}^m$。

编程题

• 求 $C_n^m\mathrm{\%}p$。
  • $n,m\le {10}^{18},p=1$
    • 弱智，直接输出 $0$。
  • $n,m\le 1000$
    • 递推式他不香吗？
  • $n,m\le {10}^6,p$ 为质数。
    • 可以使用上面提到的线性求逆（I）。
• 给定 $x,k$，将 $x$ 拆成 $k$ 个组合数的和。只要 $n_1,n_2$ 不同或 $m_1,m_2$ 不同就叫不同的组合数。
  • 《电信诈骗》
  • 把 $x$ 拆成 $k-1$ 个 $1$ 和一个 $x-k+1$，于是 $x=C_1^0+C_2^0+C_3^0+...+C_{k-1}^0+C_{x-k+1}^1$。
• 给定 $n_1,m_1,n_2,m_2$，比较 $C_{n_1}^{m_1}$ 与 $C_{n_2}^{m_2}$ 的大小。
  • $\log$ 的性质：$\log ab=\log a+\log b$

抽屉原理

引入——还是引入一下吧

一共 $n+1$ 个物品，放入 $n$ 个抽屉，显然至少有 $1$ 个抽屉有两个物品。

题目

• 给定 $n$ 个数，要求从中选任意多个数，使得它们的和为 $c$ 的倍数。$c\le n\le {10}^5$。
  • 史诗级巨坑：《任意多个数》
  • 我们加个条件，让选的数必须连续。此时我们可以直接前缀和，得到 $n+1$ 个数。
  • 按 $\mathrm{\%}c$ 的值构造抽屉，由于 $c\le n$，而我们会构造 $c+1$ 个抽屉，所以肯定有一个抽屉有至少两个前缀和 $s_i,s_j$，那么 $a_{i+1}+a_{i+2}+...+a_j$ 就是 $c$ 的倍数。
• 平面上有 $n$ 个点，用 $3$ 个 $L\times L$ 的各边平行于坐标轴的正方形来覆盖所有的点，求最小的 $L$。
  • 找出这些点的四至点，并画出相应的长方形（红色）。如图：
  • 
  • 因为只有三个正方形，所以我们必须让某一个正方形覆盖其中的两个点（绿色）。显然放在角上最优。比如这样：
  • 
  • 此时红色正方形就变成了剩余点的四至点。同理，我们再用另一个正方形（蓝色）再次覆盖两个四至点：
  • 
  • 最后用一个正方形（橙色）覆盖最后剩的点。
  • 
  • 当然上图显然不是最优的。我们把所有可能的情况全部枚举，计算最小值即可。