多项式复合+拉格朗日反演
多项式复合+拉格朗日反演
多项式复合
多项式复合形如 \(F(G(x))\) ，即复合函数，较为数学的形式可以写作 \(u=F(v),v=G(x)\)。
在符号上，记做 \(F\circ G=F(G(x))\)。
稍微展开一下就是 \(\begin{aligned} F(G(x))=\sum_i [x^i]F(x)\cdot G^i(x)\end{aligned}\)。
平面图的欧拉定理
平面图的欧拉定理
平面图
平面图是一张无向图，顾名思义：存在一种在平面上画点的方法，使得所有的边不会相交。
欧拉定理
对于一张平面图 \(G=(V,E)\)，\(F\) 为平面图上的边把平面划分的区域个数（注意统计最外层的无限区域），则：
一张平面图是连通的 \(\Longleftrightarrow\) \(|V|-|E|+|F|=2\)。
拉格朗日反演 (Lagrange Inversion)
拉格朗日反演 (Lagrange Inversion)
复合逆
对于 \(F(G(x))=x (\Leftrightarrow G(F(x))=x)\)，则称 \(F(x)\) 与 \(G(x)\) 互为复合逆，下文中记为 \(\hat F(x)\)。
存在复合逆的条件为 \([x^0]F(x)=0,[x^1]F(x)\ne 0\)。
多项式指定大小的单位根点值式求解(含Bluestein’s Algorithm)
多项式指定大小的单位根点值式求解(含Bluestein’s Algorithm)
下面的阐述建立于存在 \(n\) 阶单位根的前提下。
（如果是NTT，必须满足 \(n|(P-1)\) ，否则单位根可能会变成一个复杂的多维向量）。
\[ \ \]
用卷积解决多项式与点值式的转化:Bluestein’s Algorithm
设最终求得的点值式为 \(f(x^k)=\sum a_i\cdot \omega_n^{i k}\)。
其中指数为 \(ik\) ，有一种简单的转化 \(i\cdot k=\cfrac{i^2+k^2-(i-k)^2}{2}\)。
由于在模意义下， \(x^{\frac{i}{2}}\) 次(二次剩余)是一个非常麻烦的东西，所以考虑一个更优的转化。
\[ i\cdot k=C(i+k,2)-C(i,2)-C(k,2) \] 这条式子的组合意义是：从集合 \(i,k\) 分别选一个，等价于从 \(i+k\) 选两个减去在 \(i,k\) 内部选两个。
通过这样的转化，我们可以对于每一个 \(a_i\) 计算其对于每个 \(f(x^k)\) 的贡献，
具体过程是简单的构造卷积，这里省略。
适用于特殊情况的转化方法
需要了解的是，多项式卷积的 FFT / NTT 不止适用与于二元分治。
对于多项式 \(F(x)\) 的 \(d\) 元分治，设分治子问题的答案为 \(G_j(x'_i),j\in[0,d-1]\) ，可以得到合并式子：
\[ F(x_i)=\sum_{j=0}^{d-1}x_i^jG_j(x_i^d)=\sum_{i=0}^{d-1}x_i^jG_j(x'_{i\mod \frac{n}{d}}) \] 对于 \(n\) 进行质因数分解，得到 \(n=\prod p_i\) ，带入上面的式子，带入 \(p_i\) 元分治强行求解，可以认为最终复杂度为 \(O(n\sum p_i)=O(n\cdot \max\{p_i\} \log n)\)。
因此，这种方法使用于 \(p_i\) 较小的情况。
n 元点值式的用途
DFT 的卷积是溢出的， \(x^i\) 会溢出到 \(x^{i\mod n}\) ，系数之间存在着循环关系。
我们可以利用 \(n\) 元卷积做到指定大小的循环卷积，可以处理一些特定问题。
例题: [CTSC2010]性能优化（使用 \(O(n\log n\log C)\) 的快速幂无法通过，尚未尝试Bluestein’s Algorithm）。
集训队论文《浅谈生成函数在掷骰子问题上的应用》 阅读笔记
集训队论文《浅谈生成函数在掷骰子问题上的应用》 阅读笔记
概率生成函数
对于随机非负离散变量 \(x\) ，它的概率生成函数是 \(F(z)=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)z^i\end{aligned}\)。
有性质：
\(F(1)=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)=1\end{aligned}\)。
\(F'(1)=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)\cdot i=E(x)\end{aligned}\)。
\(E(x^{\underline{k}})=F^{(k)}(1)\) （ \(x\) 的 \(k\) 阶下降幂）。
\(x\) 的方差 \(=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)\cdot (i-E(x))^2\end{aligned}=\begin{aligned}\sum_{i=0}^{\infty}P(x=i)\cdot i^2-2P(x=i)\cdot i\cdot E(x)+P(x=i)\cdot E^2(x)\end{aligned}\)
\(=E(x^2)-2E^2(x)+E^2(x)=E(x^2)-E^2(x)=E(x^{\underline{2}})+E(x)-E^2(x)=F''(1)+F'(1)-(F'(1))^2\)
CTSC2006 歌唱王国
给定序列 \(A_{1.. n}\)。
求从一个空序列每次放 \([1,m]\) 随机，第一次出现 \(A\) 的期望长度。
设当前对应 \(\text{kmp}\) 位置为 \(i\) ，每次都可以转移一下：
\(F(n)=0\)
\(F(i)=\frac{\sum_{j=1}^m F(nxt_{i,j})}{m}+1\)
\(nxt\) 非拓扑关系，且无法枚举 \(1..m\)。
考虑每次 \(\text{kmp}\) 合法匹配指针最多位移一位，令 \(G(i)\) 为匹配变为 \(i+1\) 的期望次数，则 \(G(i)=\sum_{j=1}^{m}\sum_{k=nxt_{i,j}}^{i} G(k)\)。
设 \(sum_i=\sum_1^{i}G(i)\) ，依次求出 \([1,n-1]\) 所有的 \(G(i)\)。
并不需要知道真的 \(nxt\) 数组，只需要知道 \(-sum_{nxt_{i,j}-1}\) ，每次从 \(fail_i\) 转移过来，改变一个位置的值，可以 \(O(1)\) 完成计算，即可做到 \(O(n)\)。
数论知识小结 [基础篇]
数论知识小结 [基础篇]
符号 \((a,b)=\gcd(a,b)\)。
乘除 \(a|b\rightarrow b=ka (k\in \N^+)\)。
\(\sum\) 求和，\(\prod\) 求积。
任意 \(\forall\)，存在 \(\exists\)。
$x$ 向下取整，$x$ 向上取整。
\([a,b]\) 区间，通常指整数即 \([a,b]\cap \Z\)。
数论知识小结 [微提高篇]
最大流/最小割树/等价流树 学习笔记
最大流/最小割树/等价流树 学习笔记
最小割树 \(\text{Gomory-Hu Tree}\)
前置
约定无向图点数为 \(n\)，边数为 \(m\)。
割:断开一些边，使得 \(s,t\) 两点不连通。
设 \(\lambda(u,v)\) 为 \(u,v\) 的最小割权值。
在非负边权的无向图上使用网络流即可求得两点间的最小割，但是如果涉及查询所有点对的最小割，就需要进行 \(n^2\) 次网络流，复杂度很高。
最小树形图 | 最小内向森林
最小树形图 | 最小内向森林
最小树形图
对于带权有向图 \(G=(V,E)\)。
对于根 \(root\) 最小树形图为以 \(root\) 为根的外向树最小边权和。
有根树的树形图
对于确定的 \(root\) 求最小树形图。