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