ABC147 D - Xor Sum 4 をPythonで考える

概要

題ではPythonで考えると書きましたが、正確にはPythonではなくPyPy3でACでした。Pythonで通らなくてもPyPyで通ることがたまにある。。。bitsetの有用性に気付いた初めての問題でした。

問題

ABC147 D - Xor Sum 4

方針

dpでとく。dp[i][j]にはA_i番目までの全てのAの2^jの位に1がいくつ含まれるかを格納する。

コード

def run():
  bit = 60
  N = int(input())
  a_li = list(map(int, input().split()))
  ans = 0
  dp = [[0]*bit for i in range(N)]
  for i in range(bit):
    dp[0][i] = (a_li[0] >> i) & 1
  for i in range(1, N):
    for j in range(bit):
      a_j = (a_li[i] >> j) & 1
      dp[i][j] = dp[i-1][j] + a_j
      if a_j == 1:
        ans += (i-dp[i-1][j]) << j
      else:
        ans += dp[i-1][j] << j
  print(ans%(10**9+7))
 
if __name__ == '__main__':
  run()