F - It Looks Difficult

解法1

$f(a,b)$ が最大何回の変形で $b=0$ にたどり着くかを考えてみてみましょう。
まず、

• $a_0=a,b_0=b$
• $a_n=a_{n-1}\ \text{xor}\ b_{n-1}$
• $b_n=2\times(a_{n-1}\ \text{and}\ b_{n-1})$

とします。

ここで、ある非負整数 $x$ を $2$ 進数表記した時に立っているビットの数を $\text{popcount}(x)$ とします。
$\text{xor},\text{and}$ の性質から、$\text{xor}$ で打ち消し合ったビットが $\text{and}$ に立つので、

$$\begin{aligned} \text{popcount}(a_n)+\text{popcount}(b_n)&=\text{popcount}(a_{n+1})+2\times\text{popcount}(b_{n+1})\\ &\ge\text{popcount}(a_{n+1})+\text{popcount}(b_{n+1}) \end{aligned}$$

であることがすぐに分かります。

ここで、等号が成り立つのは $b_{n+1}=0$ の時のみであり、追加で $1$ 回変形を行うと、 $f(a,b)=f(a_{n+1},0)=a_{n+1}$ を導くことができます。

あとは $b_{n+1}\ne0$ の場合について何回の変形で計算が終了するかが分かればよく、

$$\text{popcount}(a_n)+\text{popcount}(b_n) >\text{popcount}(a_{n+1})+\text{popcount}(b_{n+1})$$

より、最大で $\text{popcount}(a)+\text{popcount}(b)$ 回程度の変換で $b_n=0$ にたどり着くことが分かります。

以上より、$O(\log a+\log b)$ 回の変換で $b=0$ になることが分かりました。

再帰関数等を用いて問題文の $f(a,b)$ をそのまま愚直に実装します。
計算量は $O(N\log(X+\sum A))$ です。

解法2

実は、$2$ 進数の足し算の筆算を考えることで、$f(a,b)=a+b$ が分かります。
より厳密には、以下の議論によって $f(a,b)=a+b$ を証明することができます。

$f(x,i)$ を非負整数 $x$ を $2$ 進数表記したときの $i$ 桁目とします。

$$x=\sum_{i=N}^\infty f(x,i)2^i$$

より、$\text{xor},\text{and}$ はビットごとに独立であることから、

$$\begin{aligned} a\text{ xor }b&=\left(\sum_{i=N}^\infty f(a,i)2^i\right)\text{ xor }\left(\sum_{i=N}^\infty f(b,i)2^i\right)\\ &=\sum_{i=N}^\infty(f(a,i)\text{ xor }f(b,i))2^i\\ a\text{ and }b&=\left(\sum_{i=N}^\infty f(a,i)2^i\right)\text{ and }\left(\sum_{i=N}^\infty f(b,i)2^i\right)\\ &=\sum_{i=N}^\infty(f(a,i)\text{ and }f(b,i))2^i \end{aligned}$$

が成り立ちます。
そして、$x,y\in\{0,1\}$ に対して $x+y=x\text{ xor }y+2\times(x\text{ and }y)$ であることは少し考えればわかるので、上の式と併せて以下が成り立つことが分かります。

$$\begin{aligned} a\text{ xor }b+2\times(a\text{ and }b)&=\sum_{i=N}^\infty(f(a,i)\text{ xor }f(b,i))2^i+2\times\sum_{i=N}^\infty(f(a,i)\text{ and }f(b,i))2^i\\ &=\sum_{i=N}^\infty(f(a,i)\text{ xor }f(b,i)+2\times(f(a,i)\text{ and }f(b,i)))2^i\\ &=\sum_{i=N}^\infty(f(a,i)+f(b,i))2^i\\ &=\sum_{i=N}^\infty f(a,i)2^i+\sum_{i=N}^\infty f(b,i)2^i\\ &=a+b \end{aligned}$$

また、解法1の後半と同様の考察をすることで有限回の変換によって計算結果 $a+b$ が得られることも分かります。

よって、$B_1=X+A_1$ に注意して累積和を計算すればよいです。

計算量は $O(N)$ です。

解法1の実装例（C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14#include <bits/stdc++.h>
using namespace std;
long long f(long long a, long long b)
{
  if (b == 0) return a;
  return f(a ^ b, 2 * (a & b));
}
int main()
{
  long long N, X, a;
  cin >> N >> X;
  while (N--)
    cin >> a, X = f(X, a), cout << X << " ";
}

解法2の実装例（C++）

1
2
3
4
5
6
7
8
9#include <bits/stdc++.h>
using namespace std;
int main()
{
  long long N, X, a;
  cin >> N >> X;
  while (N--)
    cin >> a, X += a, cout << X << " ";
}