「数学基础知识」

老年选手的康复计划之一,整理一波简单的数学公式,备忘,大部分知识来自《具体数学》。

0x00 记号注释

记号 名称
$\lfloor x\rfloor$
$\lceil x\rceil$
$x \%y$ 余数:$x - \lfloor x/y\rfloor\times y$
$x \setminus y$ 表示 $x$ 是 $y$ 的因子
$gcd(x,y)$ $x,y$ 的最大公约数
$lcm(x,y)$ $x,y$ 的最小公倍数
$\binom{n}{m}$ $n$ 选取 $m$ 的方案数
$\{_m^{n}\}$ $n$ 划分 $m$ 的方案数

0x01 $gcd$

函数 $gcd(a,b)$ 表示整数 $a,b$ 的最大公约数,即 $gcd(a,b)=max(c|c\setminus a~and~c\setminus b )$

$gcd$存在一个性质,即$gcd(a,b)=gcd(b,a\%b)$

这个递归式可以帮助我们快速求得两个数的$gcd$

1
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

对偶的,有一个函数叫做 $lcm(a,b)$ ,表示整数 $a,b$ 的最小公倍数

1
int lcm(int a, int b) { return a / gcd(a, b) * b; }

如果我们想求得一组关于方程 $ax+by=gcd(a,b)$的整数解,可以用到该算法的扩展

显然:
$$
ax+by=gcd(a,b)=gcd(b,a\%b)=bx’+a\%by’
$$
所以 $x=y’,y=x’-\lfloor a/b\rfloor y’$

1
2
3
4
5
int exgcd(int a, int b, int &x, int &y) {
if (!b) { x = 1; y = 0; return a; }
int d = exgcd(b, a % b, y, x);
y -= a / b * x; return d;
}

0x02 逆元

定义运算 $a \circ b = e$ 在数域 $F$ 下成立,那么 $a$ 和 $b$ 对与该运算互为逆元

模意义下的乘法逆元

$a \times b = 1 (mod~p)$

在 $p$ 是素数的前提下,运用费马小定理 $a^{p-1}=1(mod~p)$,可以知道 $b = a^{-1} = a^{p-2}(mod~p)$

对于一般情况而言,$a^{-1}$ 的存在,当且仅当 $gcd(a,p)=1$,

方法1:我们可以利用扩展的欧几里得算法解决

$$
a\times a^{-1} = 1 (mod~p) \leftrightarrow a\times a^{-1} + p\times k=1
$$
我们解这个方程,就可以得到 $a^{-1}$ 和 $k$ ,不难发现,$k$ 就是 $p^{-1} (mod~a)$

方法2:我们可以利用欧拉定理解决

$$
a^{\varphi(p)}=1(mod~p)\leftrightarrow a^{-1}=a^{\varphi(p)-1}(mod~p)
$$
所以还是可以利用快速幂解决

方法3:我们可以线性递推

考虑到 $p=ki+r$,得到 $ki+r=0(mod~p)$

移项:$r=-ki(mod~p)$

同乘$r^{-1}i^{-1}$:$i^{-1}=-kr^{-1}$

其中:$k = \lfloor p/i\rfloor,r = p\%i$

0x03 中国剩余定理

有一组模方程组
$$
\left\{\begin{array}{lr}
x=a_1(mod~m_1)\\
x=a_2(mod~m_2)\\
\cdots\\
x=a_n(mod~m_n)
\end{array}\right.
$$
求 $x$ 的最小非负整数解

$m_i$ 两两互素

定义 $M = \prod m_i,$ 相当于要构造求一个 $A=x(mod~M)$

再定义$M_i=M/m_i$,$M_i^{-1}$是$M_i$在模$m_i$意义下的逆元。显然,对于任何数 $a$ ,有以下等式:
$$
\begin{array}{lr}
a\times M_i\times M_i^{-1}=a ~(mod~m_i)\\
a\times M_i\times M_i^{-1}=0~ (mod~M_i)\
\end{array}
$$
所以我们可以构造出一个解$A = \sum a_i\times M_i\times M_i^{-1}$

可以证明,解 $A$ 满足模方程组中的所有方程

1
2
3
4
5
6
7
8
9
10
int china(int *a, int *m, int n) {
int M = 1, ans = 0, tmp;
for (int i = 1; i <= n; i++) M *= m[i];
for (int i = 1; i <= n; i++) {
int Mi = M / m[i], iMi;
exgcd(Mi, m[i], iMi, tmp);
ans = (ans + a[i] * Mi * iMi) % M;
}
return (M + ans % M) % M;
}

$m_i$ 没有限制

以上的分析不管用了,因为不互素的话逆元可能不存在,甚至可能无解,这都是需要判断的

考虑合并两个方程,即对于方程
$$
\left\{
\begin{array}{lr}
x=a_1(mod~m_1)\\
x=a_2(mod~m_2)
\end{array}
\right.
$$
构造一个可行解。

将式子展开,我们发现:
$$
x = a_1 + b_1 \times m_1 = a_2 + b_2\times m_2
$$
所以
$$
a_1-a_2=b_2\times m_2-b_1\times m_1
$$
现在,令 $d = gcd(m_1,m_2)$,并求得 $(x,y)$ 满足 $m_1x+m_2y=d$ 。显然,如果 $d\not\setminus(a_1-a_2)$ 是无解的

然后求得$b_1=(a_1-a_2)/d\times x,b_2=(a_1-a_2)/d\times y$

那么同时满足两个方程的解就是$A = a_1+b_1\times m_1$

这样就求得了一个新的方程 $x=A(mod~lcm(m_1,m_2))$,一步步地去合并,就得到了最终的 $x$.

1
2
3
4
5
6
7
8
9
10
11
12
int exchina(int *a, int *m, int n) {
int A = a[1], M = m[1], t, d, x, y;
for (int i = 2; i <= n; i++) {
int d = exgcd(M, m[i], x, y);
if ((a[i] - A) % d != 0) return -1;
x *= (a[i] - A) / d;
t = m[i] / d;
x = (t + x % t) % t;
A = M * x + A, M *= t, A %= M;
}
return (A % M + M) % M;
}

0x04 $Lucas$ 定理

在求解大的组合数的时候,有一个小的模数,我们就可以干这么一件事情:

$P$ 为素数

$$
\binom{n}{m}=\binom{n/p}{m/p}\binom{n\%p}{m\%p} ~~(mod~p)
$$

$P$ 无限制

现在,上面的那个玩意不能用了

考虑 $P = \prod p_i^{k_i}$,如果我们求了 $\binom{n}{m} (mod~p_i^{k_i})$,就可以利用上面提到的中国剩余定理合并即可

现在的问题就是。。。如何求解 $\binom{n}{m}(mod~p_i^{k_2})$

根据组合数的阶乘公式 $\binom{n}{m}=\frac{n!}{m!(n-m)!}$

我们可以预处理 $n!(mod~p_i^{k_i})$ ,然后就可以 $O(1)$ 求组合数了?

问题是 $n$ 很大,我们的预处理要和 $p_i^{k_i}$ 有关。。。

考虑将阶乘中是 $p_i$ 倍数的数提出来,那么将得到
$$
1\times2\times\cdots\times(p_i-1)\times(p_i+1)\times(p_i+2)\times\cdots\times(2\times p_i-1)\times(2\times p_i + 1)\times \cdots
$$
由于是在模 $p_i^{k_i}$ 意义下的,所以这个阶乘只需要预处理到 $p_i^{k_i}$ 就可以了

现在,如果求挖掉 $p_i$ 及其倍数的阶乘,就很好处理了,答案便是 $prod[p_i^{k_i}]^{\lfloor n/p_i^{k_i}\rfloor}\times prod[n\%p_i^{k_i}]$

观察一下被挖掉的数字,它们就是 $p_i,2p_i,3p_i,4p_i\cdots$ ,如果集体除掉一个 $p_i$ 那么他们也是在模 $p_i^{k_i}$ 意义下的阶乘!

好了,解决了,我们可以递归地处理这一部分,就像 $Lucas$ 定理一样。最后统计一下除了多少个 $p_i$ 乘回去就好了!

$$
fac(n)=prod[p_i^{k_i}]^{\lfloor n/p_i^{k_i}\rfloor}\times prod[n\%p_i^{k_i}]\\
\binom{n}{m}=\frac{fac(n)}{fac(n-m)fac(m)}\times \binom{\lfloor n/p_i^{k_i}\rfloor}{\lfloor m/p_i^{k_i}\rfloor} \times p_i^{cnt}
$$

0x05 $BSGS$

考虑一个模方程
$$
a^x=b(mod~P)
$$
如何求解 $x$ ? 显然,我们可以暴力枚举 $x$,然后检查等式左边是不是等于等式右边,然后就得到了一个 $O(P)$ 的优秀做法辣。

天哪我会二分!我们二分一个 $x$,看等式左边比右边大了还是小了。。。

别理上面那个智障

卧槽这是模意义下啊,特么怎么比较大小啊?

既然二分的 $O(logP)$ 不能做到,我们可以退而求其次,寻找一个 $O(\sqrt{P})$ 的做法

首先,暴力预处理出所有 $a^k,k\in[0,\sqrt{P}]$,然后暴力枚举一个数 $a^{d},\sqrt{P}\setminus d$,如果 $b/a^{d}\in \{a^k,k\in[0,\sqrt{P}]\}$,那么我们就找到答案了

这就是大步小步法,在 $\sqrt{P}$ 的时间内求模意义下的根式

有关 $BSGS$ 的扩展定理,可以适应 $P$ 不是素数的情况,由于我相信出题人不会那么毒瘤,所以暂时没有学习

0x06 组合数相关

$\binom{n}{m}=$ $n$ 个有标号的物品中选择 $m$ 个物品的方案数。

$n$ $\binom{n}{0}$ $\binom{n}{1}$ $\binom{n}{3}$ $\binom{n}{4}$ $\binom{n}{5}$ $\binom{n}{6}$
$0$ $1$
$1$ $1$ $1$
$2$ $1$ $2$ $1$
$3$ $1$ $3$ $3$ $1$
$4$ $1$ $4$ $6$ $4$ $1$
$5$ $1$ $5$ $10$ $10$ $5$ $1$

以下内容摘自《具体数学》,最重要的十个二项式系数恒等式。

  • 阶乘展开式,用于快速求得组合数
    $$
    \binom{n}{m}=\frac{n!}{m!(n-m)!}\\
    $$
  • 对称恒等式,选 $m$ 个物品和不选 $n-m$ 个物品的方案是一样的
    $$
    \binom{n}{m}=\binom{n}{n-m}\\
    $$
  • 吸收/提取恒等式,我们可以从 $n$ 个物品中任选一个作为最后一个选择的物品,所以要乘 $n$,但是所有已经选择了的物品都是等价的,所以要除 $m$
    $$
    \binom{n}{m}=\frac{n}{m}\binom{n-1}{m-1}
    $$
  • 加法/归纳恒等式,假设我们已经考虑了 $n-1$ 个物品,现在考虑第 $n$ 个物品,如果选这个物品,那么之前就要选 $m-1$ 个物品,不然之前就要选 $m$ 个
    $$
    \binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}
    $$
  • 上指标反转,并不知道这是想干嘛
    $$
    \binom{n}{m}=(-1)^{m}\binom{m-n-1}{m}
    $$
  • 三项式版恒等式,等式相当于把集合 $n$ 划分为三个部分,$k,m-k,n-m$,由于方案和划分顺序无关,可以得到以下的等式,更漂亮一点的写法是把上面三个部分替换为 $a,b,c$
    $$
    \binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}\\
    \binom{a+b+c}{a+b}\binom{a+b}{a}=\binom{a+b+c}{a}\binom{b+c}{b}
    $$
  • 二项式定理,以及两个个特殊值的恒等式,可以用于二项式反演
    $$
    \sum_m\binom{n}{m}x^my^{n-m}=(x+y)^n\\
    \sum_m\binom{n}{m}=2^n\\
    \sum_m(-1)^m\binom{n}{m}=[n=0]
    $$
  • 平行求和法,递归展开加法归纳恒等式即可
    $$
    \sum_{k\leq n}\binom{r+k}{k}=\binom{r+n+1}{n}
    $$

  • 上指标求和法,递归展开加法归纳恒等式的另一半即可

$$
\sum_{0\leq k\leq n}\binom{k}{m}=\binom{n+1}{m+1}
$$

  • 范德蒙德卷积公式,如果我们想从 $n+m$ 个物品里面选择 $s$ 个,不妨从 $n$ 里面选 $k$ 个,并在 $m$ 里面选 $s-k$个

$$
\sum_k\binom{n}{k}\binom{m}{s-k}=\binom{n+m}{s}
$$

0x07 第二类斯特林数相关

$\left\{\begin{array}{lr}n\\ m\end{array}\right\}=$ 将 $n$ 个有标号的物品划分为 $m$ 个无标号的非空集合的方案数,为了方便起见这里只讨论第二类斯特林数,并用 $S(n,m)$ 代替以上的符号

递推式 $O(n^2)$

  • 前$n−1$个元素,若放入了$m−1$个集合,那么这个元素肯定是新开一个集合,所以等于$S(n−1,m−1)$

  • 若已经放入了$m$个集合,那么这个元素在前面所有元素中选一个放入,就是 $S(n-1,m) \times m$

$$
S(n,m)=S(n-1,m-1)+S(n-1,m)\times m
$$

主要应用在组合数之类的问题中。 以下摘自博客 BAJim_H
几个经典例子。

  • $N$本书,$M$个抽屉(无差别),每个抽屉不能为空,求方案数。 易得$Ans=S(N,M)$
  • $N$本书,$M$个抽屉(有差别),每个抽屉不能为空,求方案数。 易得$Ans=S(N,M)M!$
  • $N$本书,$M$个抽屉(无差别),每个抽屉可以空,求方案数。 枚举多少个抽屉非空,易得$Ans=\sum_{i=0}^mS(N,i)$
  • $N$本书,$M$个抽屉(有差别),每个抽屉可以空,求方案数。 枚举非空抽屉数,乘上一个排列。$Ans=\sum_{i=0}^MP_i^MS(N,i)$

通项公式 $O(n)$

$$
S(n,m) = \frac{1}{m!}\sum_{k=0}^{m}(-1)^k\binom{m}{k}(m-k)^n
$$

证明见 0x08 变换与反演.

0x08 变换与反演

二项式反演

$$
f(n) = \sum_{k=0}^n\binom{n}{k}g(k) \leftrightarrow g(n)=\sum_{k=0}^n(-1)^k\binom{n}{k}f(n-k)
$$

本质就是下面这个玩意
$$
\sum_{k=0}^{n}(-1)^k\binom{n}{k} = [n=0]\\
$$
证明如下
$$
\begin{aligned}
g(n)&=\sum_{k=0}^{n}\binom{n}{k}g(k)[n-k=0]\\
&=\sum_{k=0}^{n}\binom{n}{k}g(k)\sum_{s=0}^{n-k}(-1)^s\binom{n-k}{s}\\
&=\sum_{s=0}^n(-1)^s\binom{n}{s}\sum_{k=0}^{n-s}\binom{n-s}{k}g(k)\\
&=\sum_{s=0}^n(-s)^s\binom{n}{s}f(n-s)
\end{aligned}
$$

斯特林数 $S(n,m)$

$$
m^n=\sum_{k=0}^m\binom{m}{k}S(n,k)k! \leftrightarrow S(n,m)=\frac{1}{m!}\sum_{k=0}^m(-1)^k\binom{m}{k}(m-k)^n
$$

错排公式 $D(n)$

$$
n!=\sum_{k=0}^{n}\binom{n}{k}D(k)(n-k)! \leftrightarrow D(n)=\sum_{k=0}^n(-1)^k\binom{n}{k}k!
$$

莫比乌斯反演

  • 形式一

$$
f(n)=\sum_{d\setminus n}g(d) \leftrightarrow g(n)=\sum_{d\setminus n} \mu(\frac{n}{d})f(d)
$$

  • 形式二

$$
f(n)=\sum_{n\setminus d}g(d) \leftrightarrow g(n)=\sum_{n\setminus d} \mu(\frac{d}{n})f(d)
$$

本质就是下面这个玩意
$$
\sum_{d\setminus n}\mu(d) = [n=1]
$$
形式一证明如下
$$
\begin{aligned}
g(n)&=\sum_{d\setminus n}g(d)[\frac{n}{d}=1]\\
&=\sum_{d\setminus n}g(d)\sum_{k\setminus \frac{n}{d}}\mu(k)\\
&=\sum_{k\setminus n}\mu(k)\sum_{d\setminus\frac{n}{k}}g(k)\\
&=\sum_{k\setminus n}\mu(k)f(\frac{n}{k})
\end{aligned}
$$

形式二证明如下
$$
\begin{aligned}
g(n)&=\sum_{n\setminus d}g(d)[\frac{d}{n}=1]\\
&=\sum_{n\setminus d} g(d) \sum_{k\setminus \frac{d}{n}}\mu(k)\\
&=\sum_{n\setminus k} \mu(\frac{k}{n})\sum_{k\setminus d}g(d)\\
&=\sum_{n\setminus k}\mu(\frac{k}{n})f(k)
\end{aligned}
$$

欧拉函数 $\varphi(n)$

$$
\begin{aligned}
\varphi(n)&=\sum_{k=1}^{n}[gcd(n,k)=1]\\
&=\sum_{k=1}^{n}\sum_{d\setminus gcd(n,k)}\mu(d)\\
&=\sum_{d\setminus n}\mu(d) \frac{n}{d}\\
\end{aligned}
\rightarrow
\begin{aligned}
n=\sum_{d\setminus n}\varphi(d)
\end{aligned}
$$