質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

1220閲覧

AtCoder BeginnerContest 177_C

encho

総合スコア182

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2020/09/01 12:32

編集2020/09/01 12:49

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)であまりを出すタイミングが異なっています。
なぜこの二つで結果が異なるのでしょうか?

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

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

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

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

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

投稿2020/09/01 13:25

mjk

総合スコア303

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

encho

2020/09/01 13:48

大変わかりやすい説明ありがとうございました。 WAのケースではA[i] * sumの部分でオーバーフローが起きていたんですね。 それぞれの値域を理解して掛け算をする必要がありました。 余剰定理に関しての説明もありがとうございます。 参考にさせていただきます。 余談ですがこの問題で灰diffなのですね... 道のりは長そうです...
mjk

2020/09/01 14:25

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問