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.はじめに
1.問題文
N 個の整数があり、 i 番目の整数は A i です。
を 109 + 7 で割った余りを求めてください。
2.制約
- 2 ≤ N ≤ 3 × 105
- 0 ≤ A i < 260
- 入力中のすべての値は整数である。
3.入力例
- 入力
10 3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820
- 出力
103715602
4.初見の感想
- XOR演算自体はabで実装できるので簡単
- 260は整数型に収まらないので工夫が必要
- 全パターン計算していると計算時間が終わらない
5.学びポイント
- XOR演算は桁の繰り上がりがないので各桁でそれぞれ考える
- XORは片方が0、片方が1の時計算結果が1になるのでそれぞれの数字で「0の個数」×「1の個数」を計算すれば何回1になるかが計算できる
- 個数計算は計算量O(N)なので総当たりのO(N2)より相当早い
- 260は整数型に収まらないので各桁でループを回して計算する
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.最後に
本番では解けなかったので残念でした…