邮局 是决策单调性优化 dp 的经典应用，其属于限制段数的序列划分问题，可以通过二分队列 + wqs 二分的方式做到 $O(n\log L\log n)$，其中 $L$ 指的是坐标的值域，此处不多赘述。

Read More

2024.5.21

树数术

给一颗 $n$ 个点的树和一个长为 $m$ 的序列 $a_{1\dots m}$，序列中每个数表示树上的一个节点。$q$ 次询问，每次询问给出 $a$ 的 $k$ 个子区间，将这 $k$ 个子区间顺次拼接成新的序列，求新序列上有多少个数是前缀 $\operatorname{lca}$。

Read More

不知道 nfls 模拟赛为什么出这种抽象东西，也不知道这玩意有什么用。

Read More

5.10

下午到达浙江余姚。今年很神奇又拿到了 THUSC 的正式名额。

Read More

Description

有 $m$ 个篮子放在一个环上，篮子按顺时针顺序编号为 $1\sim m$。有 $n$ 个球，第 $i$ 个球放在篮子 $a_i$ 中，$a_i$ 互不相同。接下来反复进行如下操作：从 $1\sim n$ 中等概率选出一个数 $i$，若球 $i$ 已被扔掉则什么都不做；否则将球 $i$ 移动到顺时针方向的下一个篮子里，如果下一个篮子里本来有一个球 $j$，则将球 $j$ 扔掉。进行一次上述操作总是花费 $1$ 单位时间，所有篮子中只剩下一个球时结束此过程。求过程持续的期望时间，答案对 $10^9 + 7$ 取模。

$1\le n\le 3\times 10^5, n\le m\le 10^9$

Read More