【数学】学习笔记

cold_jelly · 2024-11-21 20:04:09 · 算法·理论

Part0 前记

憋了很久，终于下定决心要把【数学】这一部分的知识梳理一遍。本文开始作于 2024.11.19，将从数论、位运算、组合数学、线性代数、概率论、博弈论等板块进行知识的整理，对于例题不过多梳理，定理大都略去证明。

为表达方便，本文中将会采用一些自创符号，将在文中给出解释。

在编写过程中，可能由于作者看百合看傻了，一些笔误还请读者指出。

参考资料：OI wiki、李煜东《算法竞赛进阶指南》。

Part1 数论

数论基础

整除：设 a,b\in \mathbf{Z}，若 \exists q\in \mathbf{Z} 使得 b=aq，则称 b 可被 a 整除，记作 a|b，反之则称 b 不可被 a 整除。

约数：若 a|b，则称 a 是 b 的约数（因数）。

余数：对于带余除法 a\div b=c\text{ reminded }d，称 d 是 a 除以 b 的余数，记作 d=a\mod b。对于上面的式子，我们也可等价转化为一个对于解题更有帮助的式子：d=a-b\left \lfloor \dfrac{a}{b} \right \rfloor。

最大公约数：对于 a,b\in \mathbf{Z}，记 \gcd(a,b) 表示 a,b 两数的最大的公共约数，简称为最大公约数，这一定义也可推广到 n 个数的情形：\gcd(a_1,a_2,...,a_n)。

最小公倍数：类似于最大公约数，我们记 \text{lcm}(a,b) 表示 a,b 两整数的最大的公共倍数，简称为最小公倍数，这一定义也可推广到 n 个数的情形：\text{lcm}(a_1,a_2,...,a_n)。

互质：对于 a,b\in \mathbf{Z}，若 \gcd(a,b)=1，则称它们互质。

质数与合数：记 m(x) 为 x 的除 x 和 1 之外的约数个数，若 m(x)=0，则称 x 为质数，若 m(x)>0，则称 x 为合数。特别地，1 既不是质数又不是合数。

质数的判定法

根据质数的定义，对于数 x(x>2) 的判定，我们很容易想到的一种思路是 2\to x-1 遍历，只要有一个数是 x 的约数，则 x 是合数，否则是质数。这种做法是 O(x) 的。

考虑到一个数的约数集合具有除 x 对称性（即若 a|x，则必有 \left(\dfrac{x}{a}\right)|x），因此我们只需要枚举 2\to \sqrt{x} 即可，时间复杂度为 O(\sqrt{x})。

inline bool isprime(int x)
{
    if(x < 2) return false;//特判1 
    for(int i = 2; i * i <= x; i ++)
        if(x % i == 0) return false;
    return true;
}

质数的筛法

埃氏筛：

埃氏筛的原理基于这样的思想：对于整数 x，2x,3x,... 一定不是质数。

给定一个上界 N，我们从 2\to N，对于每一个数 x，标记 2x,3x,...,\left \lfloor \dfrac{N}{x} \right \rfloor x，用一个数组存下来质数即可。

时间复杂度为 O(N\log\log N)。

const int N = _______;//上界
bool st[N];//标记合数 
int p[N], cnt = 0;//记录质数 
void Eratosthenes(int x)//埃氏筛 
{
    memset(st, 0, sizeof st);
    for(int i = 2; i <= n; i ++)
    {
        if(st[i]) continue;
        p[++ cnt] = i;
        for(int j = i; j <= n / i; j ++)
            st[i * j] = true;
    }
}

欧拉筛（线性筛）：

我们发现埃氏筛仍然会对合数重复标记，所以时间复杂度达不到线性。

线性筛法解决了这一问题，其通过“从大到小累计质因子”的方式标记每个合数。我们用数组 v 记录最小质因子，在筛选过程中维护 v：

1. 依次考虑 2\to N 之间的每一个数 i；
2. 若 v_i=0，则可判定 i\in P（P 表示质数集合，下文用此符号代指）；
3. 扫描不大于 v_i 的每个质数 p，令 v_{i\times p}=p，这也就是在 i 的基础上累积一个质因子 p，因为 p\leq v_i，所以 p 就是 i\times p 的最小质因子。

按照这样的操作，每一个合数只会被其最小的质因子筛一遍，时间复杂度为 O(N)。

const int N = _______;
int v[N];//记录最小质因子 
int p[N], cnt = 0;//记录质数 
void Euler(int n)//线性筛 
{
    memset(v, 0, sizeof v);
    for(int i = 2; i <= n; i ++)
    {
        if(v[i] == 0)
        {
            v[i] = i;
            p[++ cnt] = i;
        }
        for(int j = 1; j <= cnt; j ++)
        {
            if(p[j] > v[i] || p[j] > n / i)
                break;
            v[i * p[j]] = p[j];
        }
    }
}

质因数分解

算术基本定理：

任何一个大于 1 的正整数 n，唯一分解成有限个质数的乘积，可写作：

其他运算或函数

lowbit 运算：

函数 \text{lowbit}(n) 定义为非负整数 n 在二进制表示下“最低位的 1 及其后边所有的 0”构成的数值。例如，n=(10)_{10} 的二进制表示为 (1010)_2，则 \text{lowbit}(n)=(10)_2=(2)_{10}。

有公式：

代码实现为：

inline int lowbit(int n)
{
    return n & (-n);
}

lowbit 运算在很多问题中有实际应用，特别地，其还是实现树状数组的一个基本运算。

popcount 运算：

函数 \text{popcount}(n) 定义为非负整数 n 在二进制表示下有多少位为 1。例如，n=(10)_{10} 的二进制表示为 (1010)_2，则 \text{popcount}(n)=2。

利用 C++ 内置的库函数 __built_popcount(unsigned int n) 可以求出 \text{popcount}(n)，另一个库函数 __built_popcount(unsigned long long n) 作用相同，只是范围扩大到了 unsigned long long。

手动实现 popcount 运算代码如下：

inline int popcount(int n)
{
    int res = 0;
    while(n)
    {
        if(n & 1) res ++;
        n >>= 1;
    }
    return res;
}

位运算的性质

交换律：a\& b=b\& a，a|b=b|a，a\oplus b=b\oplus a。

结合律：a\& b\& c=a\& (b\& c)，a|b|c=a|(b|c)，a\oplus b\oplus c=a\oplus (b\oplus c)。

恒等律：a|0=a，a\oplus 0=a，a\& a=a，a|a=a。

归零律：a\& 0=0，a\oplus a=0。

自反律：\neg(\neg a)=a，a\oplus a\oplus a=a。

分配律：a\& (b|c)=(a\& b)|(a\& c)，a|(b\& c)=(a|b)\& (a|c)，a\& (b\oplus c)=(a\& b)\oplus (a\& c)。

吸收律：a|(a\& b)=a，a\& (a|b)=a。

摩根定律：\neg (a\& b)=(\neg a)|(\neg b)，\neg (a|b)=(\neg a)\& (\neg b)。

异或展开：a\oplus b=(a\& b)\oplus (a|b)。

异或和：\displaystyle \bigoplus^{n}_{i=1}i=\left\{\begin{matrix} 1 & n\equiv 1\pmod{4}\\ n+1 & n\equiv 2\pmod{4}\\ 0 & n\equiv 3\pmod{4}\\ n & 4|n \end{matrix}\right.

加法展开：a+b=(a\& b)+(a|b)，a+b=2(a\& b)+(a\oplus b)。

异或等价：a\oplus b=0\Longrightarrow a=b。

成对变换：n\oplus 1=\left\{\begin{matrix} n+1 & 2|n\\ n-1 & \text{otherwise} \end{matrix}\right.。

位运算不等式： 1.a\& b\le \max(a,b)； 2.a\oplus b\ge a-b，当且仅当 a\& b=b 时取等。

奇偶性：n\& 1=\left\{\begin{matrix} 0 & 2|n\\ 1 & \text{otherwise} \end{matrix}\right.。

lowbit 相关：1.a|(-a)=-\text{lowbit}(a)；2.a\oplus (-a)=-\text{lowbit}(a)<<1。

二进制数与 bitset

bitset 是 C++ 内置的一种 STL 容器，可看作一个多位二进制数，每 8 位占用 1 字节，相当于采用了状态压缩的二进制数组，并支持基本的位运算。n 位 bitset 执行一次位运算的复杂度可视为 \dfrac{n}{32}，效率较高。

bitset 的声明：

const int N = _______;
bitset<N> s;

表示声明一个 N 位二进制数 s。

操作符：

代码 s[k] 表示访问 s 的第 k 位。

对于 bitset 的位运算，与变量的位运算的写法一致。

方法函数：

s.count()：返回 s 有多少位为 1；

s.any()：若 s 所有位都为 0，则返回 false，否则返回 true；

s.none()：若 s 所有位都为 0，则返回 true，否则返回 false；

s.set()：把 s 的所有位变为 1；

s.reset()：把 s 的所有位变为 0。

Part3 组合数学

加法原理和乘法原理

加法原理：对于“分类”计数，若每一类方法之间互不重合，则总方案数为子方法数之和。

乘法原理：对于“分步”计数，若每一类方法之间互相独立，则总方案数为子方法数之积。

排列数

从 n 个不同元素中依次取出 m 个元素排成一列，产生的不同排列的数量为：

其中 \text{A}^{m}_{n}（\text{P}^{m}_{n}）叫做排列数。

阶乘：

上述式子中我们采用了形如 n! 的符号，它表示 n 的阶乘，阶乘的计算公式为：n!=\displaystyle \prod^{n}_{i=1}i。特别地，规定 0!=1。

全排列：

在排列数的计算公式中，如果 n=m，即从 n 个不同元素中依次取出 n 个元素排成一列的方案数，此时我们将其称为 n 的一个全排列，有公式 \text{A}^{n}_{n}=n!。递归求一个数的全排列的代码如下（例题：link）：

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> path;
void dg(int u, int state)
{
    if(u == n)
    {
        for(auto x : path) printf("%d ", x);
        printf("\n");
        return;
    }
    for(int i = 0; i < n; i ++)
        if(!(state >> i & 1))
        {
            path.push_back(i + 1);
            dg(u + 1, state | (1 << i));
            path.pop_back();
        }
}
int f(int n)//记录方案总数，即n!
{
    int sum = 1;
    for(int i = 1; i <= n; i ++)
        sum *= i;
    return sum;
}
int main()
{
    scanf("%d", &n);
    dg(0, 0);
    cout << f(n);
    return 0;
}

组合数及其性质

从 n 个元素中取出 m 个元素组成一个集合（不考虑顺序），产生不同的集合数量为：

其中 \displaystyle \binom{n}{m} 叫做组合数，读作「n 选 m」。

组合数的部分性质：

2. 递推公式：\displaystyle \binom{n}{m}=\displaystyle \binom{n-1}{m}+\displaystyle \binom{n-1}{m-1}；
7. 范德蒙德卷积：\displaystyle \sum^{m}_{i=0}\binom{n}{i}\binom{m}{k-i}=\binom{m+n}{k}；
8. 上指标求和：\displaystyle \sum_{l=0}^n\binom{l}{k}=\binom{n+1}{k+1}；
10. 吸收公式：\displaystyle r\binom{r-1}{k-1}=k\binom{r}{k}。

组合数的求法

如何代码实现求组合数 \displaystyle \binom{n}{m} 呢？

朴素暴力：

int C(int n, int m)
{
    int res = 1;
    for(int i = 1; i <= m; i ++)
        res = res * (a - i + 1) / i;
    return res;
}

预处理阶乘：

根据公式 \displaystyle \binom{n}{m}=\dfrac{n!}{m!(n-m)!}，一种直接的方法是先预处理阶乘数组 fac，直接代入公式计算。

const int N = _______;
int fac[N];//i!
int C(int n, int m)
{
    return fac[n] / fac[n - m] / fac[m];
}

绝大多数组合数的计算结果都很大，所以题目中往往需要我们求组合数对一个大质数取模（例如 10^9+7）的值，这时我们可以先预处理阶乘的逆元数组，通过乘法逆元求得组合数取模的值。

首先同样地，预处理一个阶乘数组 fac（注意，在此处 fac_n=n!\mod p，其中 p 表示题干中给出的大质数）。

但是除法并不具有加法和乘法那样的模运算性质，即 \dfrac{a}{b}\mod p\neq \dfrac{a\mod p}{b\mod p}，我们需要通过乘法逆元将除法转化为乘法。

预处理逆元数组 facinv，计算公式为 facinv_n=(n!)^{-1}\mod p。此时有公式：

求逆元，由于 p\in P，那么可以采用快速幂和费马小定理，时间复杂度为 O(n\log n)。

const int N = _______;
const int mod = _______;//p
int fac[N], facinv[N];
int qp(int a, int b)//quick_power: a^b mod p
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void init()//预处理fac[]与facinv[] 
{
    fac[0] = facinv[0] = 1;
    for(int i = 1; i < N; i ++)
    {
        fac[i] = fac[i - 1] * i % mod;
        facinv[i] = facinv[i - 1] * qp(i, mod - 2) % mod;
    }
}
int C(int n, int m)
{
    return fac[n] * facinv[n - m] % mod * facinv[m] % mod;
}

需要注意的是，预处理过程以及组合数的计算过程中的数字运算通常很巨大，因此最好提前将 int 类型替换为 long long 或 __int128 以避免溢出，本文为方便起见，统一采用 int。

Lucas 定理：

组合数的计算过程与上面一样，只是对于取模过程用到了 Lucas 定理（详见 Part1 数论）：

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

递推预处理组合数：

依据：\displaystyle \binom{n}{m}=\displaystyle \binom{n-1}{m}+\displaystyle \binom{n-1}{m-1}。

根据此递推式，我们可以通过两层循环预处理二维数组 C，用于记录组合数的值，时间复杂度 O(n^2)。

const int N = _______, M = _______;
const int mod = _______;
int C[N][M];//C[i][j]: i选j 
void init()
{
    for(int i = 0; i < N; i ++)
        for(int j = 0; j <= i; j ++)
            if(j == 0) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}

二项式定理与杨辉三角

二项式定理：

证明：当 n=1 时，原式显然成立。

假设当 n=m 时命题成立，当 n=m+1 时：

由数学归纳法可知定理成立。

杨辉三角：

每行第一个数和最后一个数都为 1，内部的数等于其左上角与右上角的两个数之和。这样递推定义所画出来的三角形被称为杨辉三角。

许多组合恒等式可以在杨辉三角图上形象地呈现出来，便于我们记忆。

排列组合中的计算技巧

推荐视频链接：link，讲的很仔细。

捆绑法：

设想这样一个问题，假设有编号为 1\to 5 的五个人要排成一排拍照，问排队方式有多少种。

在不加任何限制的前提下，我们很容易想到这是一个全排列问题，总的方案数就是 \text{A}^5_5=5!=120。

现在我们加上一条限制：由于 1 和 2 的关系很好，必须站在一起，问排队方式有多少种。此时我们仿佛不能直接求解了，加上这一限制后如果要用常规方式计算就很麻烦。

不妨考虑这样一个操作：既然 1 和 2 必须站在一起，那我们可以把他俩看成一个整体，把他俩“捆起来”，就像下图，此时我们就可以把 1 和 2 看作一个人。

此时问题就转化为了 4 个人的全排列问题了，方案数为 \text{A}^4_4=4!=24。

注意，我们在一开始就将 1 和 2 绑了起来，现在还要给它们“松绑”，这时 1 和 2 之间也可以进行排列，所以还需要乘上 2 的全排列，即总方案数为 24\times 2!=48。

这种思想被称为捆绑法。

插空法：

还是举上面那个例子，5 个人排排站，但由于 3 和 4 有矛盾，不能站在一起，此时问总的排队方式有多少种。

我们可以有这样的考虑：3 和 4 他俩事儿多，把他俩踢出去，先把 1、2、5 给排了，就像这样：

如图所示，在排好 1、2、5 之后，自动地就在 3 个人之间形成了 4 个空。我们要满足 3 和 4 不能站在一起，不就可以将他俩安置在这些空中吗？这种思想被称作插空法。此时相当于将 3 和 4 分置在两个不同的空中，方案数为 \displaystyle \text{A}^{2}_{4}=12。完了吗？我们在一开始就安排好了 1、2、5，但是这三个人之间也有顺序之分呀，所以对于总方案数，根据乘法原理（分步），还需要乘上 3 的全排列，即总方案数为 12\times 3!=72。这是插空法的一大坑点，一定要格外注意。

隔板法：

（名额分配问题）假设现在有 10 个 NOIP 名额，要分配给 3 个竞赛班，要保证每个班至少分配 1 个名额，求分配方案数。

不妨假设这 10 个 NOIP 名额是 10 个没有差异的小球，现在我们要将其分为 3 堆，保证每堆至少有 1 个小球，问方案数。

由于这些小球之间没有差异，我们可以将其排为一排：

我们要将其划分为 3 组，不妨考虑就是用两个“隔板”（图中黄色线条）分割序列，我们要做的就是把这两个隔板插入 10 个小球之间的 9 个空中，总方案数就为 \displaystyle \binom{9}{2}=36。这种方法我们称作隔板法。

这题还有个变式：如果我们需要保证每个班至少分配 2 个名额呢？此时我们可以提前将 3 个名额分配给 3 个班，问题就转化为 7 个名额的问题了，通过类似的方法即可求解，总方案数为 \displaystyle \binom{7-1}{2}=15。

由此我们可以总结出一个公式：若名额有 n 个，要分为 k 组，且保证每组的名额至少为 a，则总分配方式共有 \displaystyle \binom{n-k(a-1)}{k-1}=\binom{n-ka+k}{k-1} 种。

多重集的排列数与组合数

多重集是指包含重复元素的广义集合。设 S=\{n_1\times a_1,n_2\times a_2,...,n_k\times a_k\} 是由 n_1 个 a_1，n_2 个 a_2，...，n_k 个 a_k 组成的多重集，记 \displaystyle n=\sum^{k}_{i=1}n_i，则 S 的全排列个数为：

这个数被称为多重集 S 的排列数。

设整数 r\leq n_i（\forall i\in [1,k]）。从 S 中取出 r 个元素组成一个多重集（不考虑元素的顺序），根据隔板法可求出产生的不同多重集的数量为：

这个数被称为多重集 S 的组合数。

对于更一般的 r，我们可使用容斥原理求出对应的多重集的组合数。

圆排列

直线排列与圆排列：

一般的排列数都是对于直线上的元素进行排列，我们把这种排列叫做直线排列。如图所示即为一个直线排列的例子。

而圆排列简单来说，就是排列的数围成了一个圆圈，如下图所示：

对于圆排列，也有类似于直线排列的排列数，叫做圆排列数，n 个数的全部圆排列数（即圆排列中的全排列）记作 \text{Q}^{n}_{n}，部分圆排列数可记作 \text{Q}^{m}_{n}。

圆排列数的计算公式：

如何计算圆排列数呢？首先对于 n 个数直线排列，那么其排列数为 \text{A}^{n}_{n}。如果我们对于一个相同的圆排列通过断链做出不同的剖分，可以将其剖分成不同的直线排列：

由图可知，对于 n 个数的圆排列，我们可以将其剖分为 n 种不同的直线排列，即这两个排列数之间有这样的关系：\text{A}^{n}_{n}=n\text{Q}^{n}_{n}，因此我们可以推出全部圆排列数的计算公式：

类似地，我们可以推导出部分圆排列数的计算公式：

鸽巢原理

内容：将 n 个物品划分为 k 组，那么至少存在一组含有的物品数大于等于 \left \lceil \dfrac{n}{k} \right \rceil。

证明：考虑反证法。假设每组含有的物品数 n_i<\left \lceil \dfrac{n}{k} \right \rceil，那么总数 \displaystyle \sum^{k}_{i=1}n_i\leq k\times \left( \left \lceil \dfrac{n}{k} \right \rceil -1 \right)=k\times \left \lceil \dfrac{n}{k} \right \rceil -k<k\left( \dfrac{n}{k}+1 \right) -k=n，矛盾，故原命题得证。

鸽巢原理通常常被用于证明存在性和求最坏情况下的解。

容斥原理

集合中元素的个数：

对于一个集合 A，我们用符号 \text{card}(A) 或 \left| A \right| 表示集合 A 中含有的元素个数。例如：\left| \{1,6,3,4\} \right|=4。本文统一采用后者。

容斥原理：

设 S_1,S_2,...,S_n 为有限集合，则有：

这就是容斥原理。

\mathbf{Venn} 图：

例子（用 \text{Venn} 图表示集合 A,B,C）：

利用 \text{Venn} 图可以形象直观地表示抽象的集合概念。

补集：

对于全集 U 下集合的并可以采用容斥原理计算，而集合的交则用全集减去补集的并集得到：

对右边使用容斥原理即可。其中符号 \overline{A} 表示集合 A 在给定的全集 U 意义下的补集，等价于 \complement_U A，本文统一采用前者。

错位排列

定义：错位排列是指没有任何元素出现在其有序位置的排列。即对于一个 1\to n 的排列 P，如果满足 \forall i\in [1,n],P_i\neq i，则称 P 是 n 的一个错位排列。

例如，\{2,3,1\} 和 \{3,1,2\} 是当 n=3 时的错位排列。

错位排列数及其通项公式：