atcoder ABC 147D でWAから抜け出せません。

Question

atcoder の問題を解いているのですが、正解にたどり着けません。
自分で考えてもわからなかったので、私のコードのだめな点を指摘してもらえると助かります。

問題

N 個の整数があり、i 番目の整数は Ai です。
∑(i=1->N-1)∑(j=i+1->N)(Ai XOR Aj) を 10^9+7 で割った余りを求めてください。

整数 A,B のビットごとの排他的論理和 a XOR b は、以下のように定義されます。

• a XOR b を二進表記した際の 2^k (k≥0) の位の数は、A,B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。

例えば、3 XOR 5=6 となります (二進表記すると: 011 XOR 101=110)。

制約

• 2≤N≤3×10^5
• 0≤Ai<2^(60)
• 入力中のすべての値は整数である。

###自分のコード

#include<iostream>
#include<algorithm>
#include<cmath>
typedef long long ll;
using namespace std;

int main(){
    int N; cin >> N;
    ll A[N], ans = 0;
    int one[60] = {}, count = 0, amari;
    for(int i=0; i<N; i++) cin >> A[i];

    // A[i] = 2進数で2^i桁目が1になる数字の数
    for(int i=0; i<60; i++){
        for(int j=0; j<N; j++){
            one[i] += A[j]%2;
            A[j] = A[j]/2;
        }
    }
    for(int i=0; i<60; i++){
        if(one[i] == 0) continue;
        ans += one[i]*(N-one[i])*pow(2, i);
        ans = ans%1000000007;
    }
    cout << ans << endl;
}

Answer 1

        ans += one[i]*(N-one[i])*pow(2, i);

この右辺の最大値は150000 * 150000 * 2^59になるので、long longには乗りません。

Comments

[退会済みユーザー]

剰余算先にすれば解決すると思いきや起きるであろうバグをもう一つ。
goro_gnmさん前も整数問題でpow使っちゃだーめってお話ししましたよー？
戻り値がdoubleだから2^60もすると整数でも浮動小数点誤差が乗りますって。

[goro_gnm]

yudedako67さん
なるほど、最終的な答えの桁数は気にしても途中のことは頭から抜けていました。これはいけませんね。
そこを修正したらACにたどり着くことができました。ありがとうございます。

NotionalKettleさん
その節はありがとうございました^^
あれから少し勉強したのですが、２の累乗数はバイナリに変換しても、きれいに表せるから浮動小数点誤差発生しないのでは？と考えました。
だから例外的にpow(2,x)は使ってもいいんじゃないかと。（今冷静に考えたら2^60がそもそもdoubleに入らないから、結局だめかって感じではあるんですが...。）
２の累乗数でも不動小数点誤差は発生するんでしょうか？

[退会済みユーザー]

double(8byte)なら2進数53桁精度らしいので恐らくは2^54で誤差が出始めると思います。
値としては2^60はdoubleに入ると思いますよ？
指数部が11bitで1023引くらしいので仮数部は置いといても2^(2^11-1023)=2^1025は入るみたいです(多分)
もちろん整数としての精度はガタガタです

[goro_gnm]

そうなのですね、まだよく理解できていなかったようです。
勉強します><
ありがとうございます。

[退会済みユーザー]

まぁこんなのの具体的な値ってそうそう必要にならないですけどね（誤差が発生しそうなポイントは意識する必要がありますが）
頑張ってください！