主要思路
这题好神仙啊。
首先介绍一个暴力的套路（虽然跟正解没关系，但我觉得碰上很多比赛的时候会用上）：我们设置 \(f[i][j]\) 当前为前 \(i\) 个数中第 \(j\) 小的贡献，那么有
\[ f[i][j] = \begin{cases} \sum_{k = 1}^{i – 1} f[i – 1][k] (s_{i – 1} = <) \\ \sum_{k = i}^{j} f[i – 1][k] (s_{i – 1} = >) \end{cases} \]
多项式开根
原理推导
按照多项式求逆中倍增的思想，可以写出这样的推导：假设我们已知在\(\pmod {x^{\lceil \frac{n}{2} \rceil}}\)求得\(B'(x)\)为当前的解，现在要步进至\(\pmod x^n\)，那么我们可以写出
HNOI 2018 省队集训 Day 1 – 解题报告
A – Tree
这道题粗看需要 Link Cut Tree，其实不然：如果我们仍然在把节点 \(1\) 作为根节点来处理子树信息、放入线段树，之后的询问我们只需要灵活的分类讨论即可。在实根为 \(root\) 时，\(u, v\) 之间的 \(LCA\) 显然是 \(lca(u, v), lca(root, u), lca(root, v)\) 之间深度最大的那一个。而修改权值和查询权值，只需要讨论两种祖先关系和平行关系即可。
Continue reading →生成函数 | Generating Function
P4091:「HEOI2016/TJOI2016」求和题解
主要思路
真你妈毒瘤。
原式子是长这个样子的：
\[ f(n) = \sum_{i = 0}^n \sum_{j = 0}^i \begin{Bmatrix} i \\ j \end{Bmatrix} 2^j (j!) \]
多项式求逆
前置技能
FFT、NTT、多项式乘法。
原理推理
现在我们有一个这样的式子：
\[ A(x)B(x) \equiv C(x) \ (mod \ x^n) \]
现在我们已知\(B(x), C(x)\)的信息，而我们计算答案的时候需要用\(A(x)\)进行运算。这个时候，我们需要求出\(B(x)\)的逆元。多项式求逆元，我们一般是用倍增的方式来求解。假如我们有\(B(x)\)在模\(x^{\lceil \frac{x}{2} \rceil}\)意义下的逆元\(D(x)\)：