10-02 OI中的数学方法 笔记

一些OI中NOIp范围内的数学知识(中间差分序列、插值部分有点掉线啊...)

一、数论相关

gcd的一些性质

1. $\gcd(x^a-1, x^b-1) = x^{\gcd(a, b)} - 1$
2. $\gcd(fib_a, fib_b) = fib_{\gcd(a, b)}$

   事实上第二个性质只要形如$f_i = af_{i-1} + bf_{i-2}$($a,b$互质)这样的递推式就成立

欧拉定理

若$gcd(a,p)=1$则有$a^{\varphi(p)} \equiv 1 (mod~p)$

拓展(一般情况):

$a^{t} \equiv a^{\min(t,\, t ~mod~ \varphi(p) + \varphi(p))} (mod~p)$

同余方程

形如:$x \equiv a_i (mod~{p_i})$

• 中国剩余定理:

  若$p_i$两两互质,存在通解$x$:

  $\begin{aligned} P &= \prod_{i} p_i \\ \\ P_i &= \frac{P}{p_i} \\ \\ T_i &= P_i^{-1} ~mod~p_i \\ \\ x &\equiv \sum_{i} a_iT_iP_i (mod~P) \end{aligned}$

• 拓展形式(合并线性同余方程):$\begin{aligned} x &\equiv a_1 (mod~{p_1}) \\ x &\equiv a_2 (mod~{p_2}) \\ x &= a_1 + k_1p_1 = a_2 + k_2p_2 \\ \end{aligned}$令$t=gcd(p_1,p_2)$,则:$\begin{aligned} a_1 + k_1\frac{p_1}{t}t& = a_2 + k_2\frac{p_2}{t}t \\ k_1\frac{p_1}{t}&\equiv \frac{a_2 - a_1}{t} (mod~{\frac{p_2}{t}})\\ k_1 &\equiv \frac{a_2 - a_1}{t} \times (\frac{p_1}{t})^{-1} (mod~{\frac{p_2}{t}}) \\ x &\equiv a_1 + p_1 \left(\frac{a_2 - a_1}{t} \times (\frac{p_1}{t})^{-1}~mod~ \frac{p_2}{t} \right) (mod~{\frac{p_1p_2}{t}}) \end{aligned}$

二、积性函数

基础知识

令$n=p_1^{e_1}p_2^{e_2}...p_k^{e_k}$

$\epsilon(n) = [n = 1]$

$\mathrm{1}(n) = 1$

$\mathrm{Id}(n) = n$

$\mu(n) = [\max(e_1, e_2, \cdots, e_k) \le 1] (-1)^k$

$\varphi(n) = n\prod_{i=1}^{k} (1 - \frac{1}{p_i})$

$\mathrm{d}(n) = \sum_{d|n} 1$ 约数个数

$\sigma(n) = \sum_{d|n} d$ 约数和

$\lambda(n) = (-1)^k$ 刘维尔函数($\mu$是一种特殊的刘维尔函数) 可做容斥

Dirichlet卷积

$(f*g)(n) = \sum_{d|n} f(d) g(\frac{n}{d})$

$\mu * 1 = \epsilon$

$\mathrm{Id} = \varphi * 1 \Rightarrow \varphi = \mathrm{Id} * \mu$

$\mathrm{d} = 1 * 1 \Rightarrow 1 = \mu * \mathrm{d}$

$\sigma = \mathrm{Id} * 1 \Rightarrow \mathrm{Id} = \mu * \sigma \Rightarrow \sigma = \varphi * \mathrm{d}$

这三个右边的式子可以通过左边的式子两边同时卷上$\mu$得到($\epsilon$卷任何函数等于其本身)

$d(ij) = \sum_{x|i}\sum_{y|j} [\gcd(x, y) = 1]$

$\sigma(ij) = \sum_{x|i}\sum_{y|j} [\gcd(x, y) = 1] \frac{iy}{x}$

满足交换律, 结合律, 两个积性函数的卷积也是积性的

三、组合数学

Lucas定理

${n\choose m} = {\lfloor\frac{n}{p}\rfloor\choose \lfloor\frac{m}{p}\rfloor} \times {n~mod~p\choose m~mod~p}~(mod~ p)~|~p~is~prime$

基本组合恒等式

$\begin{aligned} & \sum_{i=0}^{n} {n \choose i} = 2 ^ n \\ & \sum_{i=0}^{n} {i \choose x} = {n+1 \choose x+1} \\ & \sum_{i=0}^{n} {k+i \choose i} = {k+n+1 \choose n} \\ & \sum_{i=0}^{m} {m \choose i} {n-m \choose m-i} = {n \choose m} \end{aligned}$

四、Stirling数

第一类Stirling数

1. 定义: $\begin{bmatrix} n \\ m \end{bmatrix}$ 表示将$n$ 个物品分为 $m$ 个无序非空环的方案数.
2. 递推式:

$\begin{bmatrix} n \\ m \end{bmatrix} = \begin{bmatrix} n-1 \\ m-1 \end{bmatrix} + (n-1)\begin{bmatrix} n-1 \\ m \end{bmatrix}$

1. 生成函数:$\begin{aligned} & x^{\overline{n}} = \sum_{i=0}^{n} \begin{bmatrix} n \\ i \end{bmatrix} x^i \\ & x^{\underline{n}}= \sum_{i=0}^{n} (-1)^{n-i} \begin{bmatrix} n \\ i \end{bmatrix} x^i \end{aligned}$

第二类Stirling数

1. 定义: $\left\{ \begin{aligned} &n \\ &m \end{aligned} \right\}$ 表示将 $n$个物品分成 $m$ 个无序非空集合的方案数.

2. 递推式:

   $\left\{ \begin{aligned} &n \\ &m \end{aligned} \right\} = \left\{ \begin{aligned} &n-1 \\ &m-1 \end{aligned} \right\} + m\left\{ \begin{aligned} n&-1 \\ &m \end{aligned} \right\}$

3. 生成函数:

   $\begin{aligned} & x^n = \sum_{i=0}^{n} \left\{ \begin{aligned} &n \\ &i \end{aligned} \right\} x^{\underline{i}} \\ & m!\left\{ \begin{aligned} &n \\ &m \end{aligned} \right\} = \sum_{i=0}^{m} (-1)^{m-i} {m \choose i} i^n \end{aligned}$

五、差分序列

定义 $\Delta^{k} f(n)$ 为 $f(n)$ 的 $k$ 阶差分序列, 并且:

$\Delta^{k} f(n) = \begin{cases} f(n), & \mathrm{k = 0} \\ \Delta^{k-1} f(n+1) - \Delta^{k-1} f(n), & \mathrm{otherwise} \end{cases}$

容易发现差分序列的具有线性性, 特别地, 多项式:

$f(x) = \{0, 0, 0, \cdots, 1\} \mid x \in [0, n]$

它的差分序列长这样:

$\begin{aligned} \{&0,0,0,0,\cdot\cdot\cdot,1\}\\ \{&0,0,0,\cdot\cdot\cdot,1 \}\\ \{&0,0,\cdot\cdot\cdot,1 \}\\ \{&0,\cdot\cdot\cdot,1 \}\\ \{&\cdot\cdot\cdot\}\\ \{&1\} \end{aligned}$

其第一列是 $\{0, 0, 0, \cdots, 1\}$ , 事实上这个多项式就是

$\frac{1}{n!} \prod_{i=0}^{n-1} (x - i) = {x \choose n}$

.

六、插值

已知一个 $n$ 次多项式的 $n+1$ 个点值, 求这个多项式的系数表示.

牛顿差值

求出多项式的 $n$ 阶差分序列第一列 $\{c_i\}$, 可以将多项式表示成:

$f(x) = \sum_{i=0}^{n} c_i {x \choose i}$

拉格朗日插值

考虑构造一个经过所有给定点的多项式:

$\begin{aligned} g_i(x) = \prod_{j=0, j \neq i}^{n} \frac{x - x_j}{x_i - x_j} \\ f(x) = \sum_{i=0}^{n} y_ig_i(x) \end{aligned}$

七、自然数幂和

求:$f_k(n) = \sum_{i=0}^{n} i^k$

Solution

直接用第二类斯特林数展开:

$\begin{aligned} f_k(n) &= \sum_{i=0}^{n} \sum_{j=0}^{k} \left\{ \begin{aligned} &k \\ &j \end{aligned} \right\} i^{\underline{j}} \\ &= \sum_{j=0}^{k} \left\{ \begin{aligned} &k \\ &j\end{aligned} \right\} j! \sum_{i=0}^{n} {i \choose j} \\ &= \sum_{j=0}^{k} \left\{ \begin{aligned} &k\\ &j\end{aligned} \right\} j! {n + 1 \choose j + 1} \end{aligned}$

这样的时间复杂度是$O(k^2)$的,考虑继续优化

通过上一个方法我们知道 $f_k(n)$ 是一个关于 $n$ 的 $k+1$ 次多项式, 于是直接拉格朗日插值即可, 并且由于系数的特殊性质, 可以做到 $O(k)$.

八、容斥与反演

Min-Max容斥

$\max(S) = \sum_{T \subseteq S, T \neq \varnothing} {(-1) ^ {|T|-1}} \min(T)$

gcd-lcm容斥(Min-Max容斥的拓展)

$\mathrm{lcm}(S) = \prod_{T \subseteq S, T \neq \varnothing} \gcd(T) ^ {(-1) ^ {|T|-1}}$

二项式反演

$\begin{aligned} f(n) &= \sum_{i=0}^{n} {n \choose i} g(i)\\ \Leftrightarrow g(n) &= \sum_{i=0}^{n} (-1)^{n-i} {n \choose i} f(i) \end{aligned}$

Stirling反演

$\begin{aligned} f(n) &= \sum_{i=0}^{n} \left\{ \begin{aligned} &n \\ &i \end{aligned} \right\} g(i) \\ \Leftrightarrow g(n) &= \sum_{i=0}^{n} (-1)^{n-i} \begin{bmatrix} n \\ i \end{bmatrix} f(i) \end{aligned}$

九、题目选讲

「BZOJ4833」

Description

已知:

$\begin{aligned} f(n) &= \begin{cases} 0, & {n = 0} \\ 1, & {n = 1} \\ 2f(n-1) + f(n-2), & {otherwise} \end{cases} \\ \\ g(n) &= \mathrm{lcm}(f(1), f(2), \cdots, f(n)) \end{aligned}$

求:

$\sum_{i=1}^{n} g(i) \times i$

$n \le 10^6$

Solution

首先由前面提到关于gcd的结论,有 $\gcd(f(i), f(j)) = f(\gcd(i, j))$

根据 Min-Max 容斥有:

$\begin{aligned} g(n) &= \prod_{T \subseteq S, T \neq \varnothing} \gcd(T)^{(-1)^{|T|+1}} \\ &= \prod_{T \subseteq S, T \neq \varnothing} f(\gcd(T))^{(-1)^{|T|+1}} \end{aligned}$

构造$h$满足$f(n) = \prod_{d|n} h(d)$,代入得到

$\begin{aligned} g(n) &= \prod_{d=1}^{n} h(d)^{\sum_{T \subseteq S, T \neq \varnothing} [d \mid gcd(T)] (-1)^{|T|+1}} \\ &= \prod_{d=1}^{n} h(d) \end{aligned}$

(最后这一步还是有点没想清楚,想通了再来填这个坑吧)

10.8 Update:

这个地方其实是因为所有含$d$这个因子的数所构成的所有集合的gcd显然都是能被$d$整除的,那么这些数构成的集合中,每个数都有选或不选两种方案,一种贡献是1,一种贡献是-1,但是因为$T$不能为空集,因此要减去空集的贡献$-1$,因此那个上面指数部分就是$1$

通过广义莫比乌斯反演可以得到:

$h(n)=\prod_{d|n}f(d)^{\mu(\frac{n}{d})}$

总时间复杂度$O(n\log n)$

剩下两道题还没看,坑待填