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$能不能也找到某种分块来合并一些计算呢