莫比乌斯反演

两个重要的公式

若 $F(n) = \sum_{n|d} f(d)$,则 $f(n) = \sum_{n|d} \mu(\frac{d}{n})F(d)$
若 $F(n) = \sum_{d|n} f(d)$,则 $f(n) = \sum_{d|n} \mu(d)F(\frac{n}{d})$

主要是要写出 $F(n)$ 和 $f(n)$ 的函数,把原式 用$f(n)$来表示,求答案的时候一般都要用到整数分块 把复杂度降到 $\sqrt n$, 可能中间会用到多次整数分块，预处理一下就行了。

积性函数

$ {\forall} (a,b) = 1$ $f(ab) = f(a)f(b)$

其中 欧拉函数(小于等于本身和自己互质的数的个数) 就是积性函数
$ {\forall} (a,b) = 1$ $\varphi(ab) = \varphi(a)\varphi(b) $

$BSGS$

Discrete Roots

解法：
题目说了 $p$ 是质数，根据原根存在定理， $p$ 一定有原根,把 $x$ 换成 $g^c$, 其中 $g$ 为原根。 枚举$1 {-}p$,其中最小的原根的大小 差不多在 $p^{1/4}$。然后看 $OI WiKi$ 上 $BSGS$ 部分
最后枚举所有的解的时候
枚举到$p-2$时因为 对于质数$p$,假设 $g$ 是 $p$ 的一个原根,则 $g^0$, $g^1$,…,$g^{p-2}$ 在模$p$意义下是$1$,$2$,…,$p-1$的全排列

$FFT$ (快速傅里叶变化)

时间复杂度 $O(nlogn)$
主要思想就是 化成 点权

前置知识 $w_n^k$ $n$次单位根
$$ w_n^i \ne w_n^j,{\forall} i\ne j,(i,j\in [0,n-1])$$
$$ w_n^k = cos(\frac{2k\pi}{n}) + sin(\frac{2k\pi}{n})i$$
$$ w_n^0 = w_n^k = 1$$
$$ w_{2n}^{2k} = w_n^k $$
$$ w_n^{k + \frac{n}{2}} = -w_n^k$$

拉格朗日插值

$n$ 个点值($x_i$,$y_i$),( $1 \le i \le n$),满足 $x_i \ne x_j$,($i \ne j$),它们唯一确定一个$n$ - 1次多项式, $f(x)$,
$$f(x) = \sum_{i = 1}^n y_i \prod_{j \ne i} \frac{x - x_j}{x_i - x_j}$$

第二类斯特林数

重要公式 $\begin{Bmatrix}n\\\k\end{Bmatrix}=\begin{Bmatrix} n-1\\\k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\\k\end{Bmatrix} $

多重排列