AtCoder Beginner Contest 147 D - Xor Sum 4

あったかい飲み物が離せません、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc147/tasks/abc147_d)にて開催されました、AtCoder Beginner Contest 147 D問題「D - Xor Sum 4」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

N 個の整数があり、 i 番目の整数は A i です。

を 10⁹ + 7 で割った余りを求めてください。

2.制約

• 2 ≤ N ≤ 3 × 10⁵
• 0 ≤ A i < 2⁶⁰
• 入力中のすべての値は整数である。

3.入力例

• 入力

10
3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820

• 出力

103715602

4.初見の感想

• XOR演算自体はa^bで実装できるので簡単
• 2⁶⁰は整数型に収まらないので工夫が必要
• 全パターン計算していると計算時間が終わらない

5.学びポイント

• XOR演算は桁の繰り上がりがないので各桁でそれぞれ考える
• XORは片方が0、片方が1の時計算結果が1になるのでそれぞれの数字で「0の個数」×「1の個数」を計算すれば何回1になるかが計算できる
• 個数計算は計算量O(N)なので総当たりのO(N²)より相当早い
• 2⁶⁰は整数型に収まらないので各桁でループを回して計算する

6.コードと簡単な解説

using System;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        //入力
        int N = int.Parse(Console.ReadLine());
        long[] A = new long[N];
        string[] str = Console.ReadLine().Split();
        for (var i = 0; i < N; i++)
        {
            A[i] = long.Parse(str[i]);
        }
        long[] D1 = new long[61];
        long[] D2 = new long[61];
        long mod = 1000000007;
        for (var i = 0; i < N; i++)
        {
            long digit = 1;
            for (var j = 0; j <= 60; j++)
            {
                //各桁で0と1の個数計算
                if (A[i] / digit % 2 == 1)
                {
                    D1[j]++;
                }
                else
                {
                    D2[j]++;
                }
                digit *= 2;
            }
        }
        long digit1 = 1;
        long ans = 0;
        for (var i = 0; i <= 60; i++)
        {
            //何回XORになるかを計算
            long temp = D1[i] * D2[i] % mod;
            temp = digit1 % mod * temp % mod;
            ans = (ans + temp) % mod;
            digit1 *= 2;
        }
        Console.WriteLine(ans);
    }
}

7.最後に

本番では解けなかったので残念でした…