ARC135题解

F暂时有个地方没搞明白, 但我会研究题解和正确代码, 把它搞会。

C - XOR to All

题面

关键在于发现若干次操作一定可以等价于一次操作。

假设进行了多次操作, 考察前两次操作$B_0$$B_1$。由定义, $B_0$一定是原数组中的一个数, 而$B_1$一定是原数组中的某个数$A$$B_0$的异或和, 因为$B_1$取自被$B_0$更新过的数组。我们发现$B_0,B_1$两次操作的结果等价于直接用$A$进行一次操作。现在操作次数减少了1, 可以一直使用这个方法直到将多次操作等价为一次操作。

现在只需要比较选择每个数对数组元素之和的影响, 这可以按位统计做到。对每一位 (最多30位) 统计有多少个数在这一位是1, 然后选择$A_i$对和的影响就是: $A_i$会对数组中所有的数翻转$A_i$中为1的那些位, 翻转的贡献可以由统计的数据计算出来。

E - Sequence of Multiples

题面

赛后自己做出来了, 很高兴。

下面记题目描述的数列本身为$A_i$, 而不论怎样得到它。

初见端倪的朴素算法

观察一个特殊的例子: $X=1,N=1e18$。这时数列就是$1$$n$本身! 然后考察$X=2,N=1e18$, 发现数列是$\{2n\}$。继续观察, 会总结出一个规律: 无论$X$如何, 当$n$充分大时, 数列会变成$\{kn\}$的形式, $k$为常数。

证明: 假设第$n$项是$kn$, 那么第$n+1$项的一个上界是$k(n+1)$, 这比前一项大了$k$。只要$k\leq n+1$, 这个上界就会被取到, 因为更小的$n+1$的倍数已经小于第$n$项了, 这不符合题目要求。

于是我们发现这个$k$的变化趋势是很重要的, 如果我们能搞清楚什么时候$k\leq n+1$, 这之后的内容就可以$O(1)$计算了。为了研究它, 构造新的数组$\{B_n\}:B_i=A_i/i$

在特殊例子上构造$\{B_n\}$会给我们一些最基本的认识, 例如: $\{B_n\}$是不增的。前面的证明过程稍加修改就能证明这个结论。实际上, 我们感到它以类似于反比函数的速度减少。

为了解出$B_i\leq i+1$的时刻, 我们研究$B_i$的变化趋势, 而这可以其定义中的$A_i$入手, 考察$A_i$的变化趋势。我们发现$A_{i+1}-A_i\leq i+1$, 否则$A_{i+1}$会被$A_{i+1}-(i+1)$取代。于是$A_i$大致以$O(n^2)$的速度增加, 具体来说, $A_i-A_1\leq(\sum_{k=2}^{i} k)=(i+2)(i-1)/2$

得到了$\{A_i\}$的变化趋势, 两侧同时除以$i$即可得到$\{B_i\}$的变化趋势上界: $B_i-\frac{X}{i}\leq \frac{(i+2)(i-1)}{2i}\leq i$, $B_i\leq \frac{X}{i}+i$。这个上界是有极小值的, 但我们知道$B_i$不增, 所以我们可以先增加$i$得到极小值, 然后等待$i+1$追上这个极小值。显然, 这个极小值在$i=\sqrt{X}$附近取到, 而$i=2\sqrt{X}$时就一定有$B_i\leq i+1$了。于是我们证明了, 如果我们暴力计算$\{A_i\}$直到$B_i\leq i+1$, 时间复杂度是$O(\sqrt{X})$的。尽管我们没有证明其下界, 但这个算法实际效率也不够高, 对1e18 1e18的输入需要计算20秒, 10组就是200秒, 远不是常数问题。

正解

$B_i$有一个类似于反比函数的, 一开始快速下降, 然后缓慢下降, 最后不变的变化过程。对反比函数的取整求和有整除分块, 对$B_i$能不能也找到某种分块来合并一些计算呢?