AtCoder BeginnerContest 177_C

Question

AtCoder BeginnerContest 177_C

177_C問題

N個の整数 A1,…,ANが与えられます。

1≤i<j≤Nを満たす全ての組 (i,j)についての Ai×Ajの和を mod(10の9乗+7)で求めてください。
制約
2≤N≤2×1050≤Ai≤109入力は全て整数

上記の問題について質問があります。解答を読んだ上で解法は理解していますが、
mod計算を行うタイミングについて質問があります。
以下のような2つのコードを実装しましたがなぜ片方のコードだけうまくいかないのかがわかりませんでした。

##ACが出た

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;
 
int main(){
    ll N;
    cin >> N;
    vector<ll> A(N);
    ll sum = 0;
    for(int i=0; i<N; i++) {
        cin >> A[i];
        sum += A[i];
    }
 
    ll ans = 0;
 
    for(int i=0; i<N; i++) {
        sum -= A[i];
        ans += (A[i]) * (sum % (1000000000 + 7));
        ans %= (1000000000 + 7);
    }
    cout << ans;
}

##WAのケース

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N);
    ll sum = 0;
    for(int i=0; i<N; i++) {
        cin >> A[i];
        sum += A[i];
    }

    ll ans = 0;

    for(int i=0; i<N; i++) {
        sum -= A[i];
        ans += (A[i] * sum) % (1000000000 + 7);
        ans %= (1000000000 + 7);
    }
    cout << ans;
}

違いはfor文の中身のみで(1000000000 + 7)であまりを出すタイミングが異なっています。
なぜこの二つで結果が異なるのでしょうか？

何かアドバイスをいただけると幸いです。
よろしくお願いいたします

Answer 1

最大でA=10^9がN=10^5個入力される極端な例を想像すれば、
大きい数字を掛け合わせた時に桁あふれを起こしていることは予想出来るかと思います。
テストデータを作って両方のコードで同じものを入力して途中の値を見比べれば分かるはずです。

上のコードでは掛け算する前にsum%1000000007の前処理をしていて、
次のA[i] * sumで掛けるsumの値が小さいので桁あふれしないで繰り返せるということかと。

下のコードではA[i] * sumでsumが大きいままの場合があるはずです。

途中計算で1000000007などの素数で割ることを中国余剰定理というらしく、累積和を使う問題では頻出しているようなので覚えるしかないようです。
２つのキーワードで検索すれば問題や解説がたくさんあります。

Comments

[encho]

大変わかりやすい説明ありがとうございました。
WAのケースではA[i] * sumの部分でオーバーフローが起きていたんですね。
それぞれの値域を理解して掛け算をする必要がありました。

余剰定理に関しての説明もありがとうございます。
参考にさせていただきます。

余談ですがこの問題で灰diffなのですね...
道のりは長そうです...

[mjk]

自分も最初は解けませんでした。
解説見て写経して3回目くらいで白紙からやっとAC通るコード書けました。
ある意味丸暗記状態です。