数论小记

扩展欧几里得

\[ax + by = \gcd(a, b) \]

由$\gcd(a,b) = \gcd(b, a \mod b)$可得，(这里 $a / b$ 表示 $\lfloor \frac{a}{b} \rfloor$)

\[ax + by = \gcd(a,b)=bx + (a - a / b * b)y = \gcd(b, a \mod b) \]

\[ax + by = bx + (a - a / b * b)y \]

\[= bx + ay - a / b * b * y \]

\[= ay + b(x - a / b * y) \]

欧拉定理：

前提: $\gcd(a, P) = 1$

\[a^{\varphi(P)} \equiv 1 \pmod P \]

扩展欧拉定理：

不需要一定满足: $\gcd(a, P) = 1$

\[a^k \equiv a^{k \mod \varphi(P) + \varphi(P)} \pmod P (k > \varphi(P)) \]

当 $P$ 为质数时，就有费马小定理：

\[a^{\varphi(P)} \equiv a^{P - 1} \equiv 1 \pmod P \]

中国剩余定理：

合并方程组 $ax \equiv b \pmod p$，满足 $\forall i, j$ $p_i$ 与 $p_j$ 互质。

考虑构造 $x$, 令 $P = \prod p$, 那么在任意一个方程代入 $P$ 结果都是0。

对于第 $i$ 个方程，代入 $\frac{P}{p_i}$ 时，结果不为 0，但是在剩下的方程的结果都是 0，也就是说，这个$x = \frac{P}{p_i}$ 只对第 $i$ 个方程有贡献。

剩下考虑构造结果，求出 $a_i\frac{P}{p_i}$ 在 mod $p_i$ 下的逆元,设为 $c_i$, 那 $a_ic_i\frac{P}{p_i}b \equiv b \pmod {p_i}$

最后得到 $x = \sum_{i = 1}^{n} a_ic_i\frac{P}{p_i}b$

这就是一个解。

扩展中国剩余定理：

合并方程组 $x \equiv b \pmod p$。

考虑合并两个方程 $x \equiv b_1 \pmod {p_1}$,$x \equiv b_2 \pmod {p_2}$

实际上对于一个解 $x$ 而言, 有：

\[x + k_1p_1 = b_1 \]

\[x + k_2p_2 = b_2 \]

对第一个式子移项：

\[x = b_1 - k_1p_1 \]

代入第二个式子：

\[b_1 - k_1p_1 + k_2p_2 = b_2 \]

整理一下：

\[- k_1p_1+ k_2p_2 = b_2 - b_1 \]

实际上 $k_1$ 正负号无所谓：

\[k_1p_1+ k_2p_2 = b_2 - b_1 \]

当 $\gcd(p_1, p_2) | b_2 - b_1$ 时才有解。

用 $exgcd$ 求出特解 $k_1$, 代入式子 $x + k_1p_1 = b_1$, 就能得到 $x$.

用 $p_3$ 表示合并后的模数，$p_3 = lcm(p_1, p_2)$。

就得到新的方程

\[x' \equiv x \pmod {p_3} \]

依次合并就能求解。

大步小步BSGS:

求解 $a^x \equiv b \pmod p$, 其中 $\gcd(a, p) = 1$。

大步 $a^{\sqrt{p}}$, 小步 $a$, 都只有 $\sqrt{p}$ 步。

枚举大步，看小步里有没有即可。

\[(a^{\sqrt{p}})^i \cdot b^{-1} \equiv a^c \pmod p \]

查询 $(a^{\sqrt{p}})^i \cdot b^{-1}$ 即可，

时间复杂度是 $O(\sqrt{p})$。

扩展：

$\gcd(a, p) \neq 1$。

考虑使 $\gcd(a, p) = 1$,

设 $d =\gcd(a, p)$。

有恒等式:

\[\frac{a^x}{d} \equiv \frac{b}{d} \pmod \frac{p}{d} \]

因为：

$a^x +k_1p = b$

$\frac{a^x}{d} +k_1\frac{p}{d} = \frac{b}{d}$

期间只要不满足 $d | b$, 容易发现原方程无解。

最后得到 $D = \prod_{i = 1}^{k}d_k$,

\[a^{x - k}\frac{a^k}{D} \equiv \frac{b}{D} \pmod {\frac{p}{D}} \]

这时满足 $\gcd(a^{x - k}, \frac{p}{D}) = 1$，

对:

\[a^{x - k} \equiv \frac{b}{a^k} \pmod {\frac{p}{D}} \]

做普通大步小步即可。

可能存在 $x < k$, 做大步小步之前暴力跑一遍 $O(k)$ 验证。

阶

模数 $P$ 下，底数 $a$ 最小的指数 $x$ 满足 $a^x \equiv 1 \pmod P$，记做 $\delta_P(a)$。

原根

底数 $a$ 满足模 $P$ 意义下，$\delta_P(a) = \varphi(P)$,称 $a$ 是模数 $P$ 的原根。

排列组合：

二项式定理

\[(a + b)^n = \sum_{i = 0}^{n}\binom{n}{i}a^ib^{n - i} \]

扩展：

\[(a_1 + a_2 + ... + a_m)^n = \sum_{i_1+i_2+...+i_m = n} \binom{n}{i_1,i_2,...,i_m}a_1^{i_1}a_2^{i_2}..a_m^{i_m} \]

Clues 这题用到了。

范德蒙德恒等式：

\[\binom{n + m}{k} = \sum_{i = 0}^{k} \binom{n}{k} \binom{m}{k - i} \]

\[m \binom{n}{m} = \frac{(n - 1)! n}{(m - 1)! (n - m)!} = n \binom{n - 1}{m - 1} \]
\[\binom{n}{m}\binom{m}{r} = \binom{n}{r} \binom{n - r}{m - r} \]
\[\sum_{i = 0}^{n} \frac{\binom{n}{i}}{i+1} = \frac{2^{n + 1} - 1}{n + 1} \]
\[\sum_{i = 0} \binom{n}{i}^2 = \binom{2n}{n} \]

Lucas 定理

对于 $p \leq n$,

\[\binom{n}{m} = \binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor} \binom{n \mod p}{m \mod p} \]

容斥原理：

参考：
oi-wiki

模型：

全集：$U$
元素：$x$
属性集合：$P_i$

目标：求出满足至少满足一个属性的集合。

\[|\bigcup_{i = 1}^{n}P_i| = \sum_{i = 1}^{n}(-1)^{i - 1}\sum_{a_1

证明：
考虑贡献，假设 $x$ 的贡献，假设它出现在 $P_1, ..., P_m$，

\[\text{cnt} = \sum_{i = 1}^{m} (-1)^{i - 1}\binom{m}{i} \]

\[= 1 - \sum_{i = 0}^{m} (-1)^{i}\binom{m}{i} \]

\[= 1-(1 - 1)^m \]

\[= 1 \]

所以每个元素只会贡献一次，就是全集。

求出满足全部属性的集合：

\[|\bigcap_{i = 1}^nP_i| = |U| - |\bigcup_{i = 1}^{n}\overline{P_i}| \]

一般化(也是算一种反演)：

类似前缀和和差分

\[f(S) = \sum_{T\subseteq S} g(T) \]

\[g(S) = \sum_{T\subseteq S} (-1)^{|S| - |T|}f(T) \]

类似超集和

\[f(S) = \sum_{S\subseteq T} g(T) \]

\[g(S) = \sum_{S\subseteq T} (-1)^{|T| - |S|}f(T) \]

min-max 容斥:

考虑把 $\max \min$ 映射到集合上，

第 k 大对应 $f(k) = \{x | 1 \leq x \leq k, k \in Z\}$，就是集合有整数$1 \sim k$。

对于 $f(\min(x, y)) = f(x) \cap f(y)$, $f(\max(x, y)) = f(x) \cup f(y)$。

就是并集和交集的关系, 上面容斥的式子：

\[|\bigcup_{i = 1}^{n}P_i| = \sum_{i = 1}^{n}(-1)^{i - 1}\sum_{a_1

替换一下：

\[|f(\max_{i = 1}^{n}P_i)| = \sum_{i = 1}^{n}(-1)^{i - 1}\sum_{a_1

min,max 反过来的也类似。

这在期望上也成立.

\[E(\max_{x\in S} x) = \sum_{T\in S}(-1)^{|T| - 1}E(\min_{y \in T} y) \]

二项式反演：

本质上，二项式反演和上面的容斥没有区别，只不过对于元素个数相同的集合，它们的贡献是一样的，这样就可以二项式反演了。
基本式子：

\[f(n) = \sum_{i = 1}^{n} (-1)^{i}\binom{n}{i} g(i) \]

\[g(n) = \sum_{i = 1}^{n}(-1)^{i}\binom{n}{i}f(i) \]

恰好和至少：

$g(n)$ 为恰好满足 $n$ 个条件，

$f(n)$ 为至少满足 $n$ 个条件。

\[f(n) = \sum_{i = n}^{m} \binom{i}{n} g(i) \]

\[g(n) = \sum_{i = n}^{m}(-1)^{i - n}\binom{i}{n}f(i) \]

其中 $m$ 为总条件个数。

对比一下容斥原理的式子：

\[f(S) = \sum_{S\subseteq T} g(T) \]

\[g(S) = \sum_{S\subseteq T} (-1)^{|T| - |S|}f(T) \]

差别就在选出的集合个数，二项式反演中，选出的 $C(i, m)$ 的集合的值都相同，而在容斥原理里就不一定。

这里有能优化计算数 dp 的一个地方 放宽限制：

当方程里含要有恰好的限制时，可以转化为至少或者至多，相邻两个至少相减就是恰好了。

第二类斯特林数:

模型：

将 $n$ 个不同的小球放入 $m$ 个相同的盒子，盒子非空。
将 $n$ 个元素分为$m$个集合，集合非空。

$S_2(n, m)$ 就是问题的答案。

递推：

考虑当前放了 $n$ 个小球和 $m$ 个盒子，并且其中每个盒子非空。

考虑第 $n$ 个小球是怎样放的:

放到 $m$ 个盒子中，因为小球不同，所以放到哪个盒子方案数都不同, 有 $m$ 种选择, 即$m * S_2(n - 1, m)$。
开新的一个盒子，也就是新开第 $m$ 个盒子，即$S(n - 1, m - 1)$。

综上所述，

\[S_2(n, m) = m * S_2(n - 1, m) + S_2(n - 1, m - 1) \]

容斥原理：

先不考虑盒子非空，也不考虑盒子相同，
那么问题就是将 $n$ 个不同的小球放入 $m$ 个不同的盒子。

对于每个小球，都能放入 $m$ 个盒子中，方案数为

\[m^n \]

不考虑盒子相同。

算出所有情况，

减去空盒为一的方案数: 可以选出$\binom{m}{1}$个盒子。方案数为

\[\binom{m}{1}(m-1)^n \]

这样会多减空盒为二的方案数，所以加回空盒为二的方案数。

以此类推，最后再除以 $m!$ 去掉盒子的顺序使得盒子相同。

\[S_2(n, m)= \frac{1}{m!}\sum_{i=0}^{m}(-1)^{i}\binom{m}{i}(m-i)^n \]

还能变下形：

\[\frac{1}{m!}\sum_{i=0}^{m}(-1)^{i}\frac{m!}{(m - i)!i!}(m-i)^n \]

\[\sum_{i=0}^{m}\frac{(m-i)^n}{(m - i)!} \frac{(-1)^{i}}{i!} \]

就变成了卷积的形式。

自然幂转下降幂

\[m^n = \sum_{i = 0}^{m}\begin{Bmatrix} n\\ i \end{Bmatrix}m^{\underline{i}} \]

实际上，可以根据二项式反演来证明，

$f(m) = m^n$, $g(m) = m! \begin{Bmatrix} n \\ m \end{Bmatrix}$

前面的容斥式子变换一下 $i$：

\[g(m) = \sum_{i = 0}^m(-1)^{m - i}\binom{m}{i}f(i) \]

二项式反演有：

\[f(m) = \sum_{i = 0}^{m}\binom{m}{i}g(i) \]

于是：

\[m^n = \sum_{i = 0}^{m}\binom{m}{i}i!\begin{Bmatrix} n\\ i \end{Bmatrix} \]

\[m^n = \sum_{i = 0}^{m}\begin{Bmatrix} n\\ i \end{Bmatrix}m^{\underline{i}} \]

这里也有个能优化dp的地方：

当 dp 里混入多项式或者说 $n^m$ 这样的东西，可以考虑合起来，转移搞点组合数，这样求和就和 $m$ 有关了？

狄利克雷卷积

这里就简记了，我之前还写过呢。

以下提及的函数都是积性函数。

定义：

\[(f\ast g)(n) = \sum\limits_{d|n}f(d)g(\frac{n}{d}) \]

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

\[1(n) = 1 \]

\[\text{id}(n) = n \]

\[d(n) = \sum\limits_{d|n}1 \]

\[\sigma(n) = \sum\limits_{d|n}d \]

\[d_w(n) =\sum\limits_{d|n}1^w \]

\[\sigma_w(n) = \sum\limits_{d|n}d^w \]

\[g(n) = \sum\limits_{i=1}^{n}\gcd(n,i) \]

恒等式：

\[f \ast \epsilon = f \]
\[\mu \ast 1 = \epsilon \]
\[\varphi\ast 1 = \text{id} \]
\[\text{id} \ast \mu =\varphi \]
\[1 \ast 1 = d \]
\[d \ast \mu = 1 \]
\[\text{id} \ast 1 = \sigma \]
\[\sigma \ast \mu = \text{id} \]
\[\text{id}_w \ast 1 = \sigma_{w} \]
\[\varphi \ast d = \sigma \]
\[\varphi \ast \text{id} = g \]

莫比乌斯反演

利用 $\epsilon(n) = [n = 1]$ 和 $\mu \ast 1 = \epsilon$ 进行反演。

例如，求：

\[\sum_{i = 1}^{n}\sum_{j = 1}^{m} \gcd(i, j) \]

不妨设 $n \leq m$。

经典枚举因数 $\gcd$。

\[\sum_{d = 1}^{n}d\sum_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j = 1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i, j) =1] \]

换成 $\mu \ast 1 = \epsilon$。

\[\sum_{d = 1}^{n}d\sum_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j = 1}^{\lfloor\frac{m}{d}\rfloor}\sum_{k |i,k|j}\mu(k) \]

再枚举 $k$,

\[\sum_{d = 1}^{n}d\sum_{k = 1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\sum_{i = 1}^{\lfloor\frac{n}{dk}\rfloor}\sum_{j = 1}^{\lfloor\frac{m}{dk}\rfloor} 1 \]

\[\sum_{d = 1}^{n}d\sum_{k = 1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\lfloor\frac{n}{dk}\rfloor\lfloor\frac{m}{dk}\rfloor \]

后面的式子用数论分块就行了。

见到 $\gcd(a_1,a_2,...,a_n) = d$ 的限制就可以莫比乌斯反演了。

杜教筛

参考：
cmd——杜教筛

作用：求积性函数 $f$：

\[S_{f}(n) = \sum_{i = 1}^{n} f(i) \]

构造积性函数 $g,h$, 满足：

\[f \ast g = h \]

就有：

\[(f\ast g)(n) = h(i) = \sum_{d|n}g(d)f(\frac{n}{d}) \]

求：

\[\sum_{i = 1}^{n} h(n) = \sum_{i = 1}^{n}\sum_{d|i}g(d)f(\frac{i}{d}) \]

枚举因数 $d$:

\[= \sum_{d = 1}^{n}g(d)\sum_{d|i}^{n}f(\frac{i}{d}) \]

发现 $\frac{i}{d}$ 是连续的, 即$1 \sim \lfloor \frac{n}{d}\rfloor$:

\[= \sum_{d = 1}^{n}g(d)S_{f}(\lfloor \frac{n}{d}\rfloor) \]

经过移项：

\[S_{f}(n) = S_{h}(n) - \sum_{d = 2}^{n}g(d)S_{f}(\lfloor \frac{n}{d}\rfloor) \]

只要能快速计算 $S_{h}(n)$ 和 $g(d)$, 就能快速计算出 $S_{f}(n)$。

时间复杂度：直接递归是 $O(n^{\frac{3}{4}})$, 如果线性筛预处理出前 $n ^{\frac{2}{3}}$ 项，那么时间复杂度是 $O(n^{\frac{2}{3}})$ 的。
例：对于 $\mu$ 求和。

从上面狄利克雷卷积恒等式选出 2. $\mu \ast 1 = \epsilon$。

根据：

\[S_{f}(n) = S_{h}(n) - \sum_{d = 2}^{n}g(d)S_{f}(\lfloor \frac{n}{d}\rfloor) \]

得到：

\[S_{\mu}(n) = S_{\epsilon}(n) - \sum_{d = 2}^{n}1(d)S_{f}(\lfloor \frac{\mu}{d}\rfloor) \]

即：

\[S_{\mu}(n) = 1 - \sum_{d = 2}^{n}S_{f}(\lfloor \frac{\mu}{d}\rfloor) \]

min_25筛

参考
cmd

求积性函数前缀和，并且 $f(p^k), p \in \text{prime}$ 是低阶多项式，可以快速求。

求:

\[\sum_{i = 1}^{n} f(i) \]

例如模板题:$f(p^k) = p^k(p^k - 1)$。

这里 $f(x) = x^2 - x, x = p^k$。

第一步：

求出 $h(n, m)$, 表示求出 $1\sim n$ 里，最小质因数大于 $p_m$ 的合数或者质数的 k 次方和，这里要求 1 次方和 2 次方和。其中，$p_m$ 表示第 $m$ 个质数。

例题中要把 f 拆成两个单项式。

先考虑 $h'(n,m)$, 这里只有最小质因数大于 $p_m$ 的合数的 k 次方和。

\[h'(n, m) = h'(n, m - 1) - d(n, m) \]

其中 $d(n, m)$ 表示最小质因数恰好是 $p_m$ 的所有数的 k 次方和。

实际上，

\[d(n, m) = p_m^k h'(\lfloor \frac{n}{p_m} \rfloor, m - 1) \]

可以理解为埃氏筛筛去 $p_1\sim p_m$ 及它们的倍数，剩下 $1 \sim \lfloor \frac{n}{p_m} \rfloor$ 没有被筛去的数，它们的最小质因数肯定 $> p_{m - 1}$, 即 $\geq p_{m - 1}$。全部数乘上 $p_m^k$, 就与 $1 \sim n$ 的满足条件的数一一映射。

就有：

\[h'(n, m) = h'(n, m - 1) - p_m^k h'(\lfloor \frac{n}{p_m} \rfloor, m - 1) \]

这里有边界: $h'(n, 0) = \sum_{i = 1, i \notin\text{prime}}^{n}i^k$。

考虑把 $h'(n, m)$ 还原回 $h(n, m)$。

在 $\sqrt{n} < p_m$ 时，有:

\[h'(n, m) = h'(n, m - 1) - p_m^k \]

每次筛，只会筛去这个质数本身。

当加入质数时，有：

\[h'(n, m) + P_m = h'(n, m - 1) + P_{m - 1} \]

其中 $P_m$ 表示 $1 \sim p_m$ 的 k 次方和。

可以发现 $P_m - P_{m - 1} = p_m^k$，上式显然成立。

这时,两边就满足了 $h(n, m)$ 的定义, $h(n, m) = h'(n, m) + P_m$。

于是：

\[h(n, m) = h(n, m - 1) \]

在 $\sqrt{n} \geq p_m$ 时, 有：

上面的得到了：

\[h'(n, m) = h'(n, m - 1) - p_m^k h'(\lfloor \frac{n}{p_m} \rfloor, m - 1) \]

对两边加上 $P_m$:

\[h'(n, m) + P_m = h'(n, m - 1) + P_m - p_m^k h'(\lfloor \frac{n}{p_m} \rfloor, m - 1) \]

\[h(n, m) = h(n, m - 1) + p_m^k - p_m^k h'(\lfloor \frac{n}{p_m} \rfloor, m - 1) \]

\[h(n, m) = h(n, m - 1) - p_m^k (h'(\lfloor \frac{n}{p_m} \rfloor, m - 1) - 1) \]

考虑把 $h'(\lfloor \frac{n}{p_m} \rfloor, m - 1)$ 还原：

\[h(n, m) = h(n, m - 1) - p_m^k (h(\lfloor \frac{n}{p_m} \rfloor, m - 1) - P_{m - 1} - 1) \]

发现 $P_{m - 1} + 1 = h(p_{m - 1}, m - 1)$, 因为 $h'(p_{m - 1}, m - 1) = 1$(除了 1 都筛完了)。

得到最后的转移式子:

\[h(n, m) = h(n, m - 1) - p_m^k (h(\lfloor \frac{n}{p_m} \rfloor, m - 1) - h(p_{m - 1}, m - 1)) \]

边界：

\[h(n, 0) = \sum_{i = 1}^{n} i^k \]

$k$ 过大的话就用拉格朗日插值。

考虑具体如何计算：

能发现转移的时候跟 $h(n, m)$ 只与 $h(n, m - 1)$ 有关，可以考虑进行 $m$ 次递推，上面的限制有 $p_m \leq \sqrt{n}$(否则不管 $m$ 多大都一样)，可以知道质数个数是 $O(\frac{\sqrt{n}}{\log n} )$ 的。
能发现 $h(n, m)$ 的 $n$ 取值是 $O(\sqrt{n})$ 种, 因此只需要对每种取值保留结果，只对这些取值递推。
还能发现, $h(p_{m - 1}, m - 1)$ 实际上就是前 $m - 1$ 个质数的 $k$
次方和h(还有 1)，可以在线筛的时候预处理。
注意 1 也要计算。

只用开一维数组，最后得到
$h(n)$ 表示，$1 \sim m$ 的质数的 k 次方和。

时间复杂度应该是 $O(\frac{n^{\frac{3}{4}}}{\log n})$。

第二步：

求 $S(n, m)$ 表示 $1 \sim n$里，最小质因数大于 $p_m$ 的 $f$ 之和。

考虑分成两部分：

$> p_m$ 的质数 $i$ 的 $f(i)$和:

\[h(n) - P_m \]
最小质因数 $> p_m$ 的合数 $i$ 的 $f(i)$ 和：

\[\sum_{j = m + 1} \sum_{p_j^k\leq n} f(p_j^k) (S(\lfloor\frac{n}{p_j^k}\rfloor, j) + [k != 1]) \]

这里是枚举合数的最小质因数，和指数。这里 $f(i) = i^k$ 是完全积性函数，可以随便拆，随便乘。当 $k > 1$ 时，就可以取空集，$k = 1$ 是就不能取，不然就是质数了。

所以：

\[S(n, m) = h(n) - P_m + \sum_{j = m + 1} \sum_{p_j^k\leq n} f(p_j^k) (S(\lfloor\frac{n}{p_j^k}\rfloor, j) + [k != 1]) \]

最后答案就是 $S(n, 0) + 1$。

这个过程好像会少算 $f(1)$，因为 $1$ 不是质数也不是合数。

用递归计算，不用记忆化(不知道为什么，反正不会超时)。

概率：

参考:
暴躁的野生猿

独立性：

$P(A \cup B) = P(A)P(B)$

条件概率：

事件 $A$ 在事件 $B$ 发生后的前提下的发生的概率。

$P(A | B) = \frac{P(AB)}{P(B)}$

可以理解为两个集合求交占另一个集合的比例。

乘法公式：

就是条件概率公式移项。

\[P(AB)= P(A | B) P(B) = P(B | A)P(A) \]

全概率公式：

对于事件 $A_1, A_2, ..., A_n$ 相互独立，并且 $\sum_{i = 1}^{n} A_n = 1$

对于事件 $B$

\[P(B) = \sum_{i = 1}^{n} P(B | A_i)P(A_i) \]

可以理解为把总样本分成几个事件集合，求这个事件在这几个集合发生的概率之和。

贝叶斯公式：

求：

\[P(A_i | B) = \frac{P(A_i)P(B | A_i)}{\sum_{i = 1}^{n} P(B | A_i)P(A_i)} \]

根据全概率公式：

\[P(A_i | B) = \frac{P(A_i)P(B | A_i)}{P(B)} \]

根据乘法公式：

\[P(A_i | B) = \frac{P(A_iB)}{P(B)} \]

就得到一个条件概率公式。

可以说是贝叶斯公式把上面的式子组合起来。

期望

DAG 模型

求 $u$ 到终点的总路程。

\[E(u) = \sum_{u \to v} P(u,v) \cdot E(u, v) + W(u,v) \]

一般终点的期望步数容易确定，所以倒推期望，能倒推因为有线性性吧。(

最优策略一般还可以取min

生成函数

参考：
铃悬的数学小讲堂——生成函数初步

求导

乘法法则：

\[(f(x)g(x))'=f'(x)g(x) + f(x)g'(x) \]

除法法则：

\[(\frac{f(x)}{g(x)})' = \frac{f'(x)g(x) - f(x)g'(x)}{g^2(x)} \]

链式法则：

\[(f(g(x)))'=f'(g(x))g'(x) \]

常用导数：

\[(\ln x)' = \frac{1}{x} \]

\[(e)' = e \]

\[(\frac{1}{1 - x})' = \frac{1}{(1 - x)^2} \]

泰勒公式

\[F(x) = \sum_{i = 0}^{\infty}\frac{f^{(i)}(x_0)}{i!}(x - x_0)^i \]

一般 $x_0 = 0$, 在 $0$ 处展开。

常用生成函数：

\[\sum_{i \geq 0} x^i = \frac{1}{1 - x} \]
\[\sum_{i \geq m} x^i = \frac{x^m}{1 - x} \]
\[\sum_{i \geq 0} c^ix^i = \frac{1}{1 - cx} \]
\[\sum_{i \geq 0} \binom{i + k - 1}{i}x^i = \frac{1}{(1 - x)^k} \]
\[\sum_{i \geq 0} \frac{c^ix^i}{i!} = e^{cx} \]
\[\sum_{i > 0} \frac{(-1)^{i - 1}}{i}x^i = \ln(1 + x) \]

在 $1$ 处展开。

\[\sum_{i > 0} \frac{1}{i}x^i = \ln(\frac{1}{1 - x}) \]

在 $0$ 处展开。

概率生成函数

一般设一个生成函数表示到达 $X = i$ 状态的结束概率 $f$，

再设一个辅助常生成函数 $X = i$ 状态还没结束的概率 $g$。

找出等量关系。

\[F(x) = \sum_{i = 0}^{\infty} P(X = i) x^i \]

\[F(1) = 1 \]

\[F'(1) = E(X) \]

容易发现：

\[E(X^{\underline{k}}) = F^{(k)}(x) \]

所以：

\[E(X^2) = F''(x) + F'(x) \]

因为：

\[D(X) = E(X^2) - E^2(X) \]

所以：

\[D(X) = F''(x) + F'(x) - F^2(x) \]

拉格朗日插值

用 $k + 1$ 个点插出 $k$ 次多项式。

实际上和中国剩余定理构造的过程类似，构造一个乘积，代入 $x_i$ 的时候为 $1$, 代入其它给出点的值 $x$ 时为 $0$, 再乘个 $y_i$。

\[f(x) = \sum_{i = 1}^{k + 1}y_i \prod_{i \neq j}\frac{x - x_j}{x_i - x_j} \]

多项式

省选大概率不考，随便写点式子。

NTT/FTT

一个蝴蝶变换后的推上来长度是 $n$ 的多项式。

\[f(x + \frac{n}{2}) = f(x) - f(x + \frac{n}{2}) \]

\[f(x) = f(x) + f(x + \frac{n}{2}) \]

or, 可以理解为子集和。

\[f(x + \frac{n}{2}) = f(x + \frac{n}{2}) + f(x) \]

and, 可以理解为超集和。

\[f(x) = f(x) + f(x + \frac{n}{2}) \]

上面两个逆回去时后面一项的系数是 $-1$。

\[f(x + \frac{n}{2}) = f(x) - f(x + \frac{n}{2}) \]

\[f(x) = f(x) + f(x + \frac{n}{2}) \]

逆回去时候要乘上 $1/2$。

牛顿迭代：

\[f(x) \equiv f_0(x) - \frac{h(f_0(x))}{h'(f_0(x))} \pmod {x^{n}} \]

构造，$h(x)$

\[h(f(x))=\frac{1}{f(x)} - g(x) \]

\[f(x) \equiv f_0(x) - \frac{\frac{1}{f_0(x)} - g(x)}{-f_0^2(x)} \pmod {x^{n}} \]

\[f(x) \equiv 2f_0(x) - f_0^2(x)g(x) \pmod {x^{n}} \]

博弈论

状态定理：

必败状态是没有后继状态的状态。
必胜状态存在一个后继状态是必败状态的状态。
必败状态不存在任意一个后继状态是必败状态的状态。

nim 和：

令 nim 和为 $s = \oplus_{i}^{n}a_i$

$s = 0$ 时必败。
$s \ne 0$ 时必胜。

nim 和与状态定理有相似之处。

其后继状态就是存在一个 $a_i' < a_i$。

当所有 $a_i = 0$ 时，没有后继状态，要满足 $0 \leq a_i$。
一次操作使得 $a_i' \gets a_i \oplus k, k > 0$, 不妨令 $s = \oplus_{i}^{n}a_i = k \ne 0$, $k$ 一定存在某一位上是 $1$, 并由奇数个这位上有 $1$ 的 $a$ 异或得出，那么任选一个$a_i$, $a_i' < a_i \oplus k$ 恒成立, 此时这个操作合法并满足操作后 $s = 0$。
$0 \oplus 0 = 0$，而并不存在一个后继状态中$a_i \oplus 0 < a_i$。

由此可见，nim 和与状态定理基本相同。

SG和 :

参考:cmd

一次只对一个游戏操作, 后继状态只有一个改变。

$ \operatorname{SG}(x) = \operatorname{mex}{\operatorname{SG}(x'),\dots}$

其中 $x'$ 是 $x$ 的后继状态。

SG 定理：

$ \operatorname{SG}(x) \ne 0$ 时必胜。
$ \operatorname{SG}(x) = \oplus_{x'} \operatorname{SG}(x')$

SG 定理和 nim 和很像。

没有后继状态时，$\operatorname{SG} = \operatorname{mex}\{\varnothing\} = 0$ 。
$\oplus_{x}\operatorname{SG}(x) = k\ne 0$ 后继状态一定有一个状态 $\operatorname{SG}(x) \oplus k < \operatorname{SG}(x)$, 由 $\operatorname{mex}$的定义可知， $\operatorname{SG}(x')=\operatorname{SG}(x) \oplus k$ 的 $x'$ 状态一定存在, 往这里操作就能得到 $\operatorname{SG} = 0$ 的状态。
由 $\operatorname{mex}$的定义可知，后继状态没有与当前状态 $\operatorname{SG}$ 相同的状态，不能走到 $\operatorname{SG} = 0$ 的状态。

组合游戏的SG函数：

\[\operatorname{SG}(X) = \operatorname{SG}(X_1) \oplus \operatorname{SG}(X_2) \oplus ... \oplus \operatorname{SG}(X_n) \]

Anti SG:

不能取的赢。

对于必胜态：

\[\operatorname{SG}(X) \neq 0 \& \max_{i=1}^{n} X_i > 1 \]

\[\operatorname{SG}(X) = 0 \& \max_{i=1}^{n} X_i \leq 1 \]

翻硬币

多个正面向上的硬币可以拆成多个只有一个硬币的子游戏。

这样就考虑找单独一个硬币的 $SG$ 函数的规律。

小结：

对于后继状态：$ \operatorname{SG}(x) = \operatorname{mex}{\operatorname{SG}(x'),\dots}$

对于独立子游戏: $\operatorname{SG}(X) = \operatorname{SG}(X_1) \oplus \operatorname{SG}(X_2) \oplus ... \oplus \operatorname{SG}(X_n)$

数论狄利克雷卷积杜教筛 Lucas定理 FWT 计数概率期望组合数学

数论小记

扩展欧几里得

欧拉定理：

中国剩余定理：

扩展中国剩余定理：

大步小步BSGS:

阶

原根

排列组合：

Lucas 定理

容斥原理：

二项式反演：

第二类斯特林数:

递推：

容斥原理：

狄利克雷卷积

莫比乌斯反演

杜教筛

min_25筛

概率：

期望

生成函数

拉格朗日插值

多项式

博弈论

nim 和 ：

SG和 :

相关

nim 和：