rioi 1c solution

Sol1 · 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

所以数据结构需要支持：

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

使用一个 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 个，可以通过。