AGC025F Addition and Andition

题意： 给定长度为 的二进制数 和长度为 的 。

对他们进行 次以下操作 ：

• 令，并将 和 加上 。

求出 次操作后的 和 。

，时限 。

---

观察该操作的过程。

从高位到低位逐位查看，若 ，称发生一次“对1事件”，则将 置为 ，在 处加一，并进位。

我们发现，对于发生"对1事件"的某个 ，后面低位的进位（权值和仅有 ）不可能跨越 而影响到高位。

于是，低位的操作的“影响”永远不会追上高位操作的“影响”（影响是个偏序），可以先计算高位。

仍然考虑从高位到低位进行处理，先计算 位及以上部分 次操作后的结果，逐个加入低位。

加入一个低位时，不断尝试进行判定事件（可能向高位引发连锁反应），最多进行 次则停止。

---

这个算法的复杂度仍是 的，尝试优化。

讨论可能的操作，并观察影响。

若 同时 。

• ① 若 ，则消耗 并发生一次事件，使得 加一。

• ② 若 ，则 ，令 加一。

• ③ 若 ，则 ，令 加一。

• ④ 若 ，则 ，令 加一。

若 单独加一。（ 单独加一类似）

• ⑤ 若 ，，停止。

• ⑥ 若 ，则 ，消耗 并发生一次事件，令 加一。

• ⑦ 若 ，则 ，令 加一。

能够发现，对于 ⑤，一轮只会发生 次；对于 ④⑥⑦，会减少 的数量；对于 ②③，使得双加状态变为单加状态，而想要回到双加状态，需要利用 ⑥ 而减少 的数量。

综上，除情况 ① 之外，其余情况的发生次数均摊 。

对于情况 ①，只需在操作时快速跳过连续的 的段，可以用 std::set 维护。

总复杂度 。