自动搬运

查看原文

来自洛谷，原作者为

	Sol1 博客：sol1.netlify.app

搬运于2025-08-24 22:44:00，当前版本为作者最后更新于2023-01-01 19:56:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Ex 题解

1C

考虑暴力 DP：

设 $f_{i,j}$ 表示填到前 $i$ 位，运算结果是 $j$ 的方案数，结果大于 $m$ 统一记为 $m+1$（因为再接一位一定是 0）。朴素实现可得 24，精细实现可得 40。（事实上 40 分很提示正解）

考虑所有转移。对于 A：

1. 所有数都可以往后接一个更小的数转移到 0。
2. 1 可以接任意数转移到对应的数。
3. 0 接任意数转移到 1。
4. 其余转移不多。

对于 C：

5. 所有数都可以往后接一个更小的数转移到 $0$。
6. 所有数都可以往后接自己转移到 $1$。
7. 所有数都可以往后接自己 +1 转移到自己 +1。
8. 1 可以接任意数转移到该数。
9. 其余转移不多。

这里会有几个重复转移（例如 $1{\rm C}1=1$ 会被多次转移），需要减掉。重复部分很少所以可以直接归到最后一类里面。

依次考虑每一种转移：

1. 全局 $\sum a_i(i-1)$，单点修改
2. 全局加
3. 单点修改，单点求值
4. 单点修改，单点求值
5. 同 1
6. 全局和，单点修改
7. 整体向右平移一位
8. 全局加
9. 同 3

所以数据结构需要支持：

• $O(1)$ 单点修改；
• $O(1)$ 单点求值；
• $O(\sqrt m)$ 以下全局加；
• $O(\sqrt m)$ 以下全局和；
• $O(\sqrt m)$ 以下全局 $\sum a_i(i-1)$；
• $O(\sqrt m)$ 以下向右平移一位。

注意这个转移的过程中前一列的 DP 不能继承到后一列，所以还要支持：

• $O(\sqrt m)$ 以下全部清零。

使用一个 $O(1)$ 数据结构维护：保存 DP 数组 $f$ 和一个时间标记数组 $t$，$s_1=\sum_{i=0}^mf_i$，$s_2=\sum_{i=0}^mf_{i}(i-1)$，以及一个清零值 $v_0$，清零时间 $t_0$，整体加的值 $v_A$。考虑所有操作：

• 单点修改：这里是单点加，下放标记（如果 $t_i<t_0$，将时间修改到 $t_0$，$f_i$ 修改到 $v_0$）之后直接改数组并对应更新 $s_1$ 和 $s_2$ 就行，$O(1)$。
• 单点求值：下放标记后返回 $f_i+v_A$ 即可，$O(1)$。
• 全局加：修改 $v_A,s_1,s_2$ 即可，$O(1)$。
• 全局和：返回 $s_1$ 即可，$O(1)$。
• 全局 $\sum a_i(i-1)$：返回 $s_2+f_0$ 即可（注意 $s_2$ 中 $f_0$ 的系数是 $-1$），$O(1)$。
• 向右平移一位：修改 $f,t$ 的起始指针的位置（可以开一个两倍长的数组，初始把指针指在中间，这样每次直接自减 1 即可），并对应修改 $s_1$ 和 $s_2$ 即可，$O(1)$。
• 清零：将 $t_0$ 设为当前时间，$v_0$ 设为 $-v_A$，$s_1$ 和 $s_2$ 均设为 $0$ 即可，$O(1)$。

最后一个运算符特殊处理，需要求组合数上指标前缀和或者下降幂底数前缀和，都是经典问题，可以 $O(1)$ 求。

所以这题就做完了。最后复杂度是 $O(n\sum_{i=2}^{\sqrt m}\sqrt[i]{i!m})$，实际 $m=10^5$ 时 A/C 转移分别只有 $393/1195$ 个，可以通过。