天梯赛 2021 L3-3 可怜的简单题题解

题意：重复从 $1,n$ 中随机加一个数到序列末，直至序列的 $\gcd$ 为 $1$ 为止，序列初始为空，求序列的期望长度。

CF1780G Delicious Dessert 题解

不会 SAM，也不会 SA，原来 SA 还有这种用法。

CF1817C Similar Polynomials 题解

$F(x)$ 差分 $n-1$ 次后的结果是 $F^{(n-1)}(x)$，$F(x+d)$ 差分 $n-1$ 次后的结果是 $F^{(n-1)}(x+d)$，而 $F^{(n-1)}(x)$ 和 $F^{(n-1)}(x+d)$ 都是一次函数，不妨令 $F^{(n-1)}=kx+b$，那么

QOJ9042 Fast Bogosort 题解

不妨令 $f_n$ 表示一个长度为 $n$ 的随机排列的 shuffle 次数的期望，那么答案就是

ICPC2025 南京站游寄

离开那片赛场时，暮色还未正沉沉压下，我却能看见天上的死线。金陵的秋，本应是爽朗的，带着桂花那一点甜润的香气；但今天却只有一片灰蒙蒙的、无所适从的天，正如我脸上的疲惫。南京，是一座铁铸的、失落的城。

exgcd 忘光了

FPS24 题解

A - Snack

QOJ14548 魔塔题解

首先，我们发现角色的攻击力始终没有发生变化，因此击杀所有怪物消耗的时间均相同。
令在第 $i$ 只怪物的位置的受击次数为 $y_i=\left(\left\lfloor\frac{h}{X-d}\right\rfloor-1\right)$。因此，我们可以在预处理时就受到 $a_iy_i$ 点伤害，然后在走到这个点时恢复 $y_i\times$ 当前防御力的生命。

QOJ2539A Grid Problem 题解

可以发现两个矩阵可以凑成一个 $1\times1$ 的 $3$，因此后续只需在 $\bmod 3$ 意义下考虑。
另外大矩阵可以由小矩阵组成，因此只需考虑小矩阵即可。

QOJ5540 City Hall 题解

首先，对 $s,t$ 各跑出单源最短路，然后考虑枚举修改点点 $i$，那么就需要对于路径 $s\to i\to t$ 求值。
枚举 $i$ 的相邻点 $u,v$，那么不难证明要把 $h_i$ 设置为 $\frac12(h_u+h_v)$，那么答案就是