TH911 Blog

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

多项式学习笔记

FFT/NTT

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

Posted by TH911 on July 17, 2025

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...

Posted by TH911 on July 16, 2025

题解：[FJOI2016] 建筑师

洛谷P4609 | 第一类斯特林数

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

Posted by TH911 on July 16, 2025

题解：SP7363 TREESUM - Tree Sum

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

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

Posted by TH911 on July 16, 2025

题解：[POI 1997] 跳

洛谷P5940 | 斐波那契数列

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

Posted by TH911 on July 15, 2025

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

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

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

Posted by TH911 on July 15, 2025

题解：重返现世

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

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

Posted by TH911 on July 15, 2025

题解：[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...

Posted by TH911 on July 15, 2025

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

洛谷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}$。 观察题面和样例解释...

Posted by TH911 on July 15, 2025

题解：[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...

Posted by TH911 on July 14, 2025

FEATURED TAGS
树状数组 题解 提高+/省选− 省选/NOI− DP 普及+/提高 基础算法 数学 组合数学 普及/提高− 贪心 字符串 线段树 未完 图论 平衡树 数论 树形 DP 搜索 Tarjan Trie 二分 位运算 二分答案 状态压缩 FHQ Treap 前端 无聊时候的一点思考 最短路 树链剖分 NOI/NOI+/CTSC
ABOUT ME

要做一个优秀的 OIER

FRIENDS