P10399 ReLyna 题解

Nopain · 2024-02-29 22:10:52 · 题解

先将求期望转为求和，最后除掉方案数。

算法 1

我们发现每次贪心选择收益最大的即使最优方案。因为我们可以将后续的选择视为若干一次函数的嵌套，其结果仍是一次函数，且斜率截距均 \ge 0。所以对于任意操作形成的函数，设其为 f(x)=kx+b\ (k,b\ge 0)，若 x_1>x_2 则 kx_1+b>kx_2+b。所以贪心即是最优策略。

基于上述观察，我们可以在 O(n) 的时间内计算任意 f(i,j)，解决本题时间复杂度为 O(mn^3) 或 O(mn^2)，可以获得 5 或 10 分。

算法 2

基于贪心原则，我们发现在 a_i=1 时除第一个操作选择加法，其余时刻均选择乘法一定不劣。于是可以将暴力改为扫描 i，维护 sum_i=\sum\limits_{j=l}^i f(j,i)。注意到 sum_i=sum_{i-1}\times b_i+1，可以使用矩阵乘法快速维护，于是可以在 O(\log n) 的时间内回答一次询问，结合算法 1 可以获得 35 分。

算法 3

修改和询问数很少，这要求我们在低于 O(n^2) 的复杂度回答询问。我们考虑扫描 i，维护 \sum\limits_{j=l}^i f(j,i)。注意到 \forall j,\ f(j,i)> f(j+1,i)，于是我们发现一定存在一个位置 p，使得 p 之前均选择乘法， p 及以后均选择加法。这启发我们使用线段树维护 f(j,i)，利用不等式 a_i+f(j,i)>b_i\times f(j,i) 二分得到位置 p。该线段树需要支持区间加/乘，维护区间 max 的真实值而非取模后的值，维护全局和。一次询问的复杂度降为 O(n\log n)，总复杂度为 O(mn\log n)。结合算法 1，2 可以获得 60 分。

在实现细节上，注意到 a_i+mod<b_i\times mod 恒成立，所以线段树维护 max 时可以维护其与 mod 的 min，不影响二分结果。

算法 4

没有修改操作启发我们通过预处理信息拼出答案。我们注意到在经过至多 L=1+\lceil log_2\ mod\rceil 次操作后一定会选择乘法。因为选择 L 次乘法后，f(i,j) 至少为 2^L > mod，所以 a_i+f(i,j)<b_i\times f(i,j) 恒成立。这启发我们对 len=i-j+1 的长度进行分类讨论：