TH911 Blog

「光阴不可测,岁月亦无歌。」

多项式学习笔记

FFT/NTT

多项式乘法 本部分主要介绍 傅里叶变换 及 快速傅里叶变换(FFT)等在 OI范围内 的应用。 参考 Blog 参考 Blog 参考 Blog 参考文章 本文会简要介绍 FFT 的原理、思想,涉及诸如 复平面、平面向量 等数学内容,文中会简要介绍。 FFT 快速傅里叶变换 傅里叶变换的本质就是将一个多项式在 系数表示法 和 点值表示法 之间转换。 FFT...

C++神奇错误之vector扩容导致引用失效

变量更改

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69...

题解:[FJOI2016] 建筑师

洛谷P4609 | 第一类斯特林数

题目传送门 题意分析 首先,高度为 $n$ 的建筑是不会被挡住的。 剩下的建筑即 $n-1$ 个。将这 $n-1$ 个建筑划分为 $A+B-2$ 个圆排列即可,每个排列内最高的建筑为起始端。 只需要考虑在 $n$ 的左侧还是右侧,因此乘上一个组合数。 故,答案为: \[\begin{bmatrix}n-1\\A+B-2\end{bmatrix}\dbinom{A+B-2}...

题解:SP7363 TREESUM - Tree Sum

洛谷SP7363 | 斯特林数展开下降幂 | 换根 DP

题目传送门 其实和[集训队互测 2011] Crash 的文明世界是差不多的。 题意分析 树上问题 首先,$n$ 个点 $n-1$ 条边,显然是一个树。 设 $\operatorname{dist}(i,j)$ 表示以 $i$ 为根节点时,$j$ 的深度。不难发现这其实就是任意节点为根节点时,$i,j$ 之间的树上距离加 $1$。因此令 $\operatorname{d...

题解:[POI 1997] 跳

洛谷P5940 | 斐波那契数列

题目传送门 题意分析 观察棋子的跳法,不难想到斐波那契数列(本文中“斐波那契数列”均将下标视为无限延伸)。 设斐波那契数列第 $i$ 项为 $f_i$,满足 $f_i=f_{i-1}+f_{i-2}$。 因此可以想到每一个位置都对应斐波那契数列中的某一项。设位置 $i$ 的棋子数量为 $\textit{cnt}_i$。 则两种跳法对应: 向左跳: \[\...

题解:[集训队互测 2011] Crash 的文明世界

洛谷P4827 | 斯特林数展开下降幂 | 换根 DP

题目传送门 题意分析 树上问题 首先,$n$ 个点 $n-1$ 条边,显然是一个树。 因此,$\operatorname{dist}(i,j)$ 其实可以 $\mathcal O(1)$ 计算出来。只需要 $\mathcal O(n\log n)$ 预处理一个 DFS 序 LCA 即可。(详见此处) 斯特林数 对于整数 $x$ 的 $k$ 次方,其实可以通过第二类斯特林数...

题解:重返现世

洛谷P4707 | kth Min-max 容斥 | DP

题目传送门 题意分析 kth Min-max 容斥 首先可以去除掉 $p$ 中的 $0$,因为 $p_i=0$ 的 $i$ 不会生成,对答案没有任何影响。 求收集到 $k$ 种原料的期望时间,即求收集所有原料的期望时间的第 $k$ 大时间。 那么就可以考虑 kth Min-max 容斥。 定义 \(\operatorname*{kthmin}\) 表示求第 $k$ 小,\...

题解:[PKUWC2018] 随机游走

洛谷P5643 | Min-max 容斥 | 树形 DP | 高维前缀和

题目传送门 题意分析 Min-max 容斥 记走到点 $i$ 的期望步数为 $t_i$,$S=\set{1,2,3,\cdots,n}$,题目所求即: \[E\left(\max_{i\in S}t_i\right)\] 根据 Min-max 容斥,等价于求: \[\sum_{T\subseteq S}(-1)^{\vert T\vert-1}E\left(\min_{i...

题解:已经没有什么好害怕的了

洛谷P4859 | 二项式反演

题意分析 设“糖果”能量为 $a_1,a_2,a_3,\cdots,a_n$,“药片”能量为 $b_1,b_2,b_3,\cdots,b_n$;不妨令 $a,b$ 均单调递增。 因为 $a_i,b_j$ 互不相同,因此每一种组合都是独一无二的。 设“糖果”比“药片”能量大的组数为 $k’$,则有 $k’+(k’-k)=n,k’=\dfrac{n+k}{2}$。 观察题面和样例解释...

题解:[HAOI2015] 按位或

洛谷P3175 | Min-max 容斥

题目传送门 题意分析 设 $t_i$ 表示第 $i$ 位变为 $1$ 的时间,设 $S=\lbrace1,2,3,\cdots,n\rbrace$。 则题目所求为: \[E\left(\max_{i\in S} t_i\right)\] 期望套 $\max$,看起来就很像 Min-max 容斥。 由 Min-max 容斥,有: \[E\left(\max_{i\in S...