Python3で解く AtCoder Beginner Contest 147 D - Xor Sum 4

問題を把握するには、連続したシグマが何を意味しているのか、XORの特性を理解することがポイント。それさえできれば結構単純。自分は桁ごとに考えた。制約としてギリなのでローカル化しないとTLE。もっと工夫できるのかもしれないけど。

概要

問題
1. $n$ 個の整数が与えられる。
1. $\displaystyle{\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(a_i\ XOR\ a_j)}$ を $10^9+7$ で割った余りは？

制約

$2 \leqq n \leqq 3 \times 10^5$
$0 \leqq a_i \lt 2^{60}$

解くときに考えた内容

このシグマの連続（）はどういう意味か？
- $n=3$ の時、i=1から順に代入していくと
- $a_1 \ XOR\ a_2 + a_1 \ XOR\ a_3 + a_3 \ XOR\ a_3$ ということ
- $\frac{n(n-1)}{2}$ 個の重複のない組み合わせでのXORの和ということ
XORをどう考えるか
1. 桁ごとに考える。
  - '^'はPythonでの排他的論理和の論理演算子
  - 1 ^ 1は0
  - 0 ^ 0は0
  - 1 ^ 0は1
  - なので、1⁰となるような状態について各桁で考えればいい。
  - 例えば $a_i$ についてbitで考えて特に2桁目について考える。
  - $a_1, a_2, a_3$ をbitで考えて2桁目が1とする。（2, 3, 7など)　 $a_4, a_5$ をbitで考えて2桁目が0とする。（4, 1など）
  - 2桁目が1 ^ 0の組み合わせになる数は $3 \times 2 = 6$ となり、bitで2桁目というのは $2^1$ なので、6*2 = 12となる。
  - これを全ての桁で考えればいい。
2. より一般に考える。
  - $a_i$ の $d$ 桁目が1である数を $x$ とすると、XORをとって1になる組み合わせ数は $x \times (n-x)$ 。
  - $d$ 桁目は $2^{d-1}$ である。
  - $x \times (n-x) \times 2^{d-1}$ の全ての桁の和が求めるものとなる。

コード

今回はローカル化しないとTLEになってしまうので注意。

def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    ans = 0
    mod = 10 ** 9 + 7
    # 制約がai <= 2**60なので
    for d in range(61):
        # d桁目ごとに考える
        x = 0
        for a in A:
            if (a >> d) & 1:
                x += 1
        ans += x * (n-x) * 2**d
        ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

書籍

アルゴリズムの参考書籍

いわゆる、螺旋本。Aizu Online Judgeの問題を題材に解説されている。自分としては、 Aizu Online Judgeは最近はβ版運用中で、構成がアルゴリズムの項目ごとに問題がタグ付けされているようなイメージで、ここら辺弱いから集中的にやってみようっていう感じでできるので、いいと思っている。（AtCoderもそんな感じのリスト作って欲しい）ただ、この書籍はC++で書かれているのでPythonでやる場合はあくまでもその過程の考え方を参考にし自分で実装する必要がある。（AOJも解いているので、記事にしていこうかなぁ）