AGC047E

· · 题解

模拟赛题，感觉非常难啊。

步数 2966，应该是最优的了。

先考虑一个 O(xy) 的做法（这个我就想了一个小时）。

首先搞出两个个长度为 O(x) 的序列，然后第一个序列里面有 x 个 1，第二个里面有 y 个 1，这个是好做的。

然后枚举上面的每一个元素，下面的每一个元素，那么答案加上它们与起来即可。

看到这个像竖式一样的东西，那么容易想到二进制拆分一下，那么相当于上面第 i 位和下面第 j 位产生 2^{i+j} 的贡献。

二进制拆分部分是 O(\log^2 V) 的，后面解竖式部分直接做是 O(\log^3 V) 的，步数大约 30000。

然后发现竖式部分每次暴力算 2^{i+j} 很浪费，可以开个桶记录 i+j 相同的东西再算，然后也不用每次重新算，可以用秦久韶算法，也就是 a_0+2(a_1+2(a_2+2(...)))。

这样大概就需要 3700 步，也是我能想出来的部分，code

后面比较阴间，上面步数是 4\log^2 V 级别的，发现加法的时候两个取与非常浪费啊。

注意到 !x \& y = x < y，因此可以先把 a_0 的二进制翻转，然后中间只需要一步即可。

这样就进入 3000 了，然后疯狂卡常。

code