TH911 Blog

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

题解:[POI 2015] LAS

洛谷P3584 | DP

题目传送门 题意分析 发现, $c_i$ 的限制比较多,因此针对此进行 DP。 设 $\textit{dp}{i,j},j\in\set{1,2,3,4}$ 表示食物 $i$ 的状态为 $j$ 的合法状态是从 $\textit{dp}{i-1,\textit{dp}{i,j}}$ 转移得来。同时,规定 $\textit{dp}{i,j}$ 有值表示合法,没有值表示不合法。 那...

题解:Sam 数

洛谷P2106 | 矩阵快速幂优化 DP

题目传送门 朴素数位 DP 一个显然的 DP:设 $\textit{dp}_{i,j},i\in[1,k],j\in[0,9]$ 为 $i$ 位且最高位为 $j$ 的 Sam 数的个数。 则有: \[\textit{dp}_{i,j}=\sum_{\max(j-2,0)}^{\min(j+2,9)}\textit{dp}_{i-1,j}\] 最终答案 $\textit{an...

题解:[HAOI2011] Problem b

P2522 | 莫比乌斯反演

题目传送门 题意分析 首先写出答案: \[\textit{ans}=\sum_{i=a}^b\sum_{j=c}^d[\gcd(i,j)=k]\] 这种涉及到 $\gcd$ 的题目,一般都考虑莫比乌斯反演。 不妨令 $b<d$,有: \[\begin{aligned} \textit{ans}&=\sum_{i=\lceil\frac ak\rceil}^{...

题解:Square Subsets

CF895C | 状压DP

题目传送门 题意分析 发现一个神奇的东西:$a_i\leq70$。值域如此之小,一定可以利用。因此考虑与值域有关的做法。 寻找完全平方数,则其所有质因子的指数均为偶数。 可以发现,$[1,70]$ 中的质数有且仅有 $19$ 个,可以考虑从此方面入手。 考虑影响是否为完全平方数的仅仅是质因子的指数的奇偶性,因此可以考虑状压 DP。 记第 $i$ 个质数为 $p_i,p_1...

题解:[COTS 2024] 双双决斗 Dvoboj

洛谷P10680 | 动态单点修改ST表 | 阈值分治

题目传送门 题意分析 首先注意到一个非常特殊的性质,区间查询形如 $\left[l,l+2^k-1\right]$,长度为 $2^k$。 其次,单点修改很简单,区间查询较为复杂。 所以,考虑使用相关数据结构和算法维护。 考虑 ST 表,这可以很好的维护长度为 $2^k$ 的区间信息。记 $\left[l,l+2^k-1\right]$ 的答案为 $\textit{st}_{...

多项式学习笔记

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$。 则两种跳法对应: 向左跳: \[\...