🌊

ABC098 D: Xor Sum 2

2022/12/03に公開

AtCoder

tech

問題

考えたこと

XORとSUMが同じになる条件は何かを考えたときに、
ある数列において各桁でビットが1のものが高々1個であるのが必要十分条件であることがわかる。

十分条件を見ていく。下記のように各桁でビットが1のものが高々1個であるとき繰り上がりが起きないことがわかり、その時XORとSUMは同値である。

必要条件を見ていく。XORとSUMが同じになるとき、ある数列において各桁でビットが1のものが2個以上存在すると仮定する。
このとき1が2個以上あることからSUMにおいて繰り上がりが発生する。
繰り上がりが発生するということは繰り上がった桁の1の個数がXORとSUMで異なるということ。
これによってXORとSUMの結果が異なりうる (繰り上がりが偶数であれば同じになる)。
これは、XORとSUMが同じになることと矛盾するため、XORとSUMが同じになるとき、各桁でビットが1のものは高々1個しか存在しないことが言える。

これらから必要十分性が示せた。

次に考えたこととして、ある区間でXORとSUMが同じになるならばその区間の部分区間もXORとSUMが同じになると言える、ということ。
上記の必要十分性から1が同じ桁に複数個存在しない。複数個存在し得ない状態で区間から任意の値をのぞいたとしてもこの事実は変わらない。

ある区間で条件を満たすとき、その区間のなかの連続する区間も条件を満たすことから尺取り法が使えるとわかる。^[1]

ある区間でXORとSUMが同じになるかどうかを判定するのに $O(N)$ 愚直にやるとかかってしまうが、それぞれ累積和を事前計算しておけば $O(1)$ で求められで求められる。

コード

提出結果

N = int(input())
A = list(int(x) for x in input().split())

axor = [0]
asum = [0]
for a in A:
  axor.append(axor[-1]^a)
  asum.append(asum[-1]+a)

r = 1
ans = 0
for l in range(N):
  while r < N and (asum[r+1] - asum[l]) == (axor[r+1]^axor[l]):
    r += 1

  if r == l:
    r += 1

  ans += r - l

print(ans)

脚注

尺取り法はQiitaの記事が非常に参考になる: https://qiita.com/drken/items/ecd1a472d3a0e7db8dce ↩︎

問題

考えたこと

コード

Discussion