闲话
哈哈,没有选题了。
没有选题就不写了(
最近摆的很舒服啊。
等卖了题再拿题解充当闲话吧。
碰壁:处理▂▕▄▄制▒▟▀问题不可以▙依赖[错误: 所引对象未导引至对象实例 ; 标准处理方法_004.rtf 不存在]。不确定[已编辑]难的。
轻舟慢慢 多少涟漪 全部入梦里
过往云烟 我怎敢去回忆 怎敢回忆
导数题
前两天是 2024 CCPC 网络赛。看到了这个题和大家的做法,感觉很好玩,就总结一下。
做法来自 Houraisan_Kaguya,_rqy et al.,本文只作转述。
有一个长条形状的传送带,其上有 \(n\) 个行李。建立坐标轴,第 \(i\) 个行李在传送带上的位置为 \(a_i\)。有 \(m\) 个人站在传送带前,第 \(i\) 个人的位置为 \(b_i\)。传送带向坐标轴正方向每秒移动一个单位,即每秒会对每个 \(i\) 执行 \(a_i \leftarrow a_i + 1\)。
显然对于一个人来说,右边的行李都是看过了的,没有自己的行李,自己的行李只可能在其左边,也可能没有。(如果坐标 \(i < j\),认为 \(i\) 在 \(j\) 左边)并且不会有一个行李同时属于两个人,但可能不属于这 \(m\) 个人中的任何人。一个人至多只有一个行李。
请对所有本质不同的情况,求得最早有人拿到自己行李的时间之和。当然,每个人的左边都没有自己的行李的情况不需要考虑。两种情况不同当且仅当:在一种情况下某个人有行李而在另一种情况中没有,或存在某个人在两种情况中的行李编号不同。
\(n,m,V\le 500\)。
令 \(m, V\) 都与 \(n\) 同阶。
首先由于 \(t\le V\),我们可以枚举这个最早的时间 \(t\),计算最早有人拿到自己行李的时间恰为 \(t\) 的方案数,乘一下就是 \(t\) 的贡献。恰为 \(t\) 不好算,改为至少为 \(t\)。这个限制的更改放在某个位于 \(x\) 的人身上,就变成只能选择坐标 \(\le x - t\) 的行李。H_kaguya 声称,这就好算了。
令 \(f(i, j)\) 为已经给 \(x \le i\) 的所有人分配完行李,剩余 \(j\) 个坐标 \(\le i - t\) 的行李未被分配的方案数。那么从前往后扫,\(f(i - 1, \cdot)\to f(i, \cdot)\) 的转移也就容易写出了。
- 若 \(i - t\) 处有行李,则整体向高位平移 \(1\),即 \(f(i, j) \leftarrow f(i - 1, j - 1)\);
- 若 \(i\) 处有人,他可以不取行李,也可以从当前行李中选择一个,即 \(f(i, j) \leftarrow f(i - 1, j) + (j + 1) \times f(i - 1, j + 1)\)。
直接做这个 dp,我们就能在 \(O(n^2)\) 的复杂度内计算出每个 \(f(n, \cdot)\),从而计算出最早有人拿到自己行李的时间至少为 \(t\) 的方案数,和至少为 \(t + 1\) 的方案数做差即可得到恰好为 \(t\) 的方案数。由于对每个 \(t\) 都需要计算,总复杂度 \(O(n^3)\),可以通过。
能不能再给力一点啊?
考察确定 \(t\) 后的子问题。一眼看过去,最可做的就是优化 dp。那就优化它吧。大家都喜欢 dp 转 gf,那就转一下吧。
令 \(F_i(x) = \sum_{j} f(i, j)x^j\),那么知道
- 若 \(i - t\) 处有行李,则整体向高位平移 \(1\),即 \(F_i(x) \leftarrow x F_{i - 1}(x)\);
- 若 \(i\) 处有人,他可以不取行李,也可以从当前行李中选择一个,即 \(F_i(x) \leftarrow F_{i - 1}(x) + F_{i - 1}'(x)\)。
因此,问题可以被转化成如下的形式;
你需要维护一个初值为 \(1\) 的多项式 \(f\),支持进行下面两种操作共 \(n\) 次:
- \(f\leftarrow xf\)
- \(f\leftarrow f + f'\)
输出所有操作执行后的 \(f \bmod x^{n + 1}\)。
注意到 \(f + f' = \dfrac{(e^x f)'}{e^x}\),而把所有操作对 \(f\) 的影响合并后会发现,只有第一次乘和最后一次除的 \(e^x\) 会对答案产生贡献,其余的 \(e^x\) 都两两消掉了。
因此我们只需要令 \(f\) 初值为 \(e^x\),维护两个操作:乘 \(x\)、求导,最终取前 \(n\) 项系数乘以 \(e^{-x}\) 即可。
_rqy 声称,这个就可以 \(\widetilde O(n)\) 求了。这是因为,初始的 \(x^k\) 项系数会在第 \(t\) 次求导后乘入 \(k + a_t\),而这列 \(a\) 对每项都相同。因此这本质上就是对某个 \(g(x) = \prod_{t} (x + a_t)\) 做多点求值(\(x = 0, \dots, n\))。容易做到 \(O(n\log^2 n)\)。
总时间复杂度 \(O(n^2 \log^2 n)\)。你就说是不是 \(\widetilde O(n^2)\) 吧。
标签:11,le,24.9,传送带,leftarrow,行李,闲话,cdot,dp From: https://www.cnblogs.com/joke3579/p/-/chitchat240911