可重组合

从 ${1, 2, 3 \cdots, n – 1, n}$ 中选出 $m$ 个元素，可以重复，有多少个不同的组合？

答案 $C_{n + m – 1}^{m}$

证明

显然，问题可以转换为 $m$ 个球放入 $n$ 个盒子，可以放无数个或者不放

即插入 $n – 1$ 个隔板，然后求全排列 $(m + n – 1)!$

但是隔板和球的顺序是无效的所以除去 $m! \times (n-1)!$

即
$$
\frac{(m + n – 1)!}{m! \times (n – 1)!} = C_{n + m -1}^m
$$

题目链接: https://www.luogu.org/problemnew/show/P3809

后缀数组

后缀数组用于解决各种玄学字符串问题，准确来说，它是一种思想

基于后缀数组有很多好玩毒瘤的东西

目前已知的求后缀数组的方法有

• 倍增法 (本博客所讲述) — $O(n \log(n))$
• DC3 — $O(n)$
  • DC3 虽然从复杂度分析的角度而言比倍增快，但配合各种常数问题，在信息学竞赛中反而容易被卡……
• SA – IS 算法 — $O(n)$
  • 可以参考这篇 Luogu 日报: https://www.luogu.org/blog/ShadowassIIXVIIIIV/on-hou-zhui-shuo-zu-sa-is-suan-fa

因为我太菜了，所以我就讲倍增求法

题目链接: https://oj.woshiluo.site/problem/2055 / https://www.luogu.org/problemnew/show/P5323

我看到题目的一瞬间

我是在学 oi 还是在学物理？

然后我仔细思考了一下，这两个镜子来回反射，您这是要求极限？

然后我仔细思考了一下

设 $f_i$ 为从 $1$ 到 $i$ 的透光率，$g_i$ 为从 $i$ 到 $1$ 的反光率

题目链接: https://www.luogu.org/problemnew/show/P1829

显然，题目所求为以下式子

以下均默认$n \leq m$

$$
\sum_{i = 1}^n \sum_{j = 1}^m lcm(i,j)
$$

先来一些比较显然的东西
$$
\begin{aligned}
\sum_{i = 1}^n \sum_{j = 1}^m lcm(i,j) & =
\sum_{i = 1}^n \sum_{j = 1}^n \frac{i \cdot j}{\gcd(i,j)}\\
& = \sum_{d = 1}^n d \sum_{i = 1}^{\frac{n}{d}} \sum_{j = 1}^{\frac{m}{d}} i \cdot j \cdot [\gcd(i,j) = 1]\\
\end{aligned}
$$
后面一段看起来还可以再加优化

狄利克雷卷积

数论函数

数论函数是指一类函数，其定义域是正整数，值域是一个数集

积性函数都是数论函数

常见的数论函数有

• $id(n) = n$ 单位函数，完全积性函数
• $\epsilon(n) = [n = 1]$ 元函数，完全积性函数
• $d(n)$ 约数个数，积性函数
• $\sigma(n)$ 约数和函数，积性函数
• $\mu(n)$ 莫比乌斯函数，积性函数
• $\varphi(n)$ 欧拉函数，积性函数

道理我都懂，考试时这东西能推？

本人菜鸡，有问题请指出

鉴于不同博客对于整除符号$|$的定义不同， 特此表明本博客的整除定义

$a | b$ 表明 $b$ 是 $a$ 的倍数

0x01 什么是反演

对于一个数列${f_n}​$,如果有另外一个数列${g_n}​$满足如下条件
$$
g_n = \sum_{i = 1}^n a_if_i
$$
反演的过程是用$ g_n$来表示 $f_n$
$$
f_n = \sum_{i = 0}^n b_ig_i
$$