ABC201 E Xor Distances
まず, 全頂点対XOR距離を高速に求める方法を考える. 木の性質であったり経験から考察すると, 次の性質がわかる.
$ dist(x, y) = dist(1, x)xor $ dist(1, y)
よってこの問題は次の問題に帰着された.
$ N個の整数があり, $ i番目の整数は$ dist(1, i)です.
$ \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^{N} (dist(1, i) XOR dist(1, j))を$ 10^9 + 7で割った余りを求めてください.
すると登場する数は$ 0, 1のみであるから, 次のように場合分けすることで今(末尾から0-indexedで)$ i桁目であるとすると答えが$ 2^i \cdot (0の個数) \cdot (1の個数)であることを導ける.
$ 0, 0もしくは$ 1, 1の場合, 加算されるのは$ 0(打ち消される)
$ 0, 1もしくは$ 1, 0の場合, 加算されるのは$ 2^i
よってこの問題を高速に解くことができた.