[CF2182F1 / 2] Christmas Reindeer 题解

为啥上紫过后上了 max 就要下分，这场罚时吃饱了。

另外这场 F1 / 2 都是糖糖题吧，赛时切的人少只是时间原因，感觉跟 Good Bye 2025 的 F 是一个难度的。

可是我赛时差一点切 F1 / 2 导致晚上失眠了。

---

不妨令 ，设 表示当前权值的系数（），称一只权值为 的鹿的实际权值为 。

对于修改，直接拿个桶 存一下即可，于是考虑询问。观察这个式子：，因为 不增，所以显然有 $\lfloor \frac{c’i}{2^{i - 1}} \rfloor \gt \lfloor \frac{c’{i + 1}}{2^i} \rfloor + \ldots + \lfloor\frac{c’_k}{2^{k - 1}}\rfloorii$ 项后面的项之和。于是，每次选的鹿的权值应当 严格大于 当前 的一半，否则无解。

考虑先把权值相同的鹿视为一种，统计答案时再计算贡献。从大到小枚举鹿的权值 ，此时分为两种情况。

1. ：此时若选了权值为 的鹿，那么已经满足条件，统计答案。若不选权值为 的鹿，那么继续考虑权值为 的鹿。
2. ，此时 必须 选权值为 的鹿，并更新 与 ，且继续考虑权值为 的鹿。若不选，显然有 ，这会导致接下来无解。

考虑如何统计答案。假设在上述模拟过程中，选了一只权值为 的鹿过后满足条件，这说明这只鹿之前的每只鹿都满足第二种情况。所以我们可以对于 中的任意 确定选了多少只权值为 的鹿，记为 ，以及 至少 选了多少只权值为 的鹿，记为 。之所以是“至少”，是因为在满足条件过后我还可以额外选择一些权值为 的鹿。同理，我还可以额外选择一些权值小于 的鹿。设 ， 表示从 个物品中选至少 个物品的方案数，那么此时的答案就是：

三部分分别表示前、中、后的贡献。前和后都是好算的，问题在于如何计算 。

F1

单次 计算 ，时间复杂度 。

考虑如何快速计算 ，显然有 。

F1.5

把 预处理出来，时间复杂度 。

F2

容易发现，若不考虑额外选的没有用的鹿，每选一只鹿会让 至少减半，所以最多只会选 只鹿，因此 的第二维最多取到 ，于是 预处理即可，时间复杂度 。

Submission。