ABC177 Cの積和は、全ての組を二重ループで列挙せず、左側の添字を一つ固定して計算できます。現在の値を先に右側の合計から引き、その合計を現在の値に掛けて答えへ加えます。こうすると、条件 1 <= i < j <= N に合う組だけを、各位置一回の更新で数えられます。
この見方を使えるのは、固定した一要素と、残りの要素との組合せを単純な集約値へまとめられる場合です。ABC177 Cでは積の分配法則によって右側の要素の合計にまとめられますが、任意のペア条件へそのまま一般化するものではありません。
左側の添字を固定すると、全ペアの和が一つの寄与になる
公式の添字は1から始まります。iを固定すると、組になるjはi+1からNまでです。したがって、iを左側に持つ積の合計は、次のように書けます。
Ai × Ai+1 + Ai × Ai+2 + ... + Ai × AN
ここでAiをくくると、右側の合計を一度だけ求めればよくなります。右側の合計をSiとすると、Si = Ai+1 + Ai+2 + ... + AN、その位置の寄与はAi × Siです。全体の答えは、i = 1からN - 1までの寄与を足したものです。
右側の合計を毎回配列の後ろから足し直すと、各iでの計算が長くなります。そこで、最初に配列全体の合計を持ち、現在の値Aiを引いてから使います。引く前の合計には現在値も含まれているため、先に掛けるとAi × Aiまで入ってしまいます。i < jを守るため、順序は必ず「引く、掛ける、足す」です。
[1, 2, 3, 4]で後続和と寄与を追う
次の配列は、式と状態変化を確かめるために構成した例です。公式サンプルではありません。全ての組を直接列挙すると、1 × 2 + 1 × 3 + 1 × 4 + 2 × 3 + 2 × 4 + 3 × 4 = 35になります。
左から順に現在値を処理します。最初の後続和は全体の合計10から始め、各行で現在値を先に引きます。
| i | 引く前の合計 | 現在値を引く | 引いた後の後続和 | 寄与 | 答えの累積 |
|---|---|---|---|---|---|
| 1 | 1 + 2 + 3 + 4 = 10 | 10 – 1 | 2 + 3 + 4 = 9 | 1 × 9 = 9 | 9 |
| 2 | 2 + 3 + 4 = 9 | 9 – 2 | 3 + 4 = 7 | 2 × 7 = 14 | 23 |
| 3 | 3 + 4 = 7 | 7 – 3 | 4 | 3 × 4 = 12 | 35 |
| 4 | 4 | 4 – 4 | 0 | 4 × 0 = 0 | 35 |
例えば1行目の1 × 9は、1 × 2、1 × 3、1 × 4をまとめたものです。2行目は2 × 3と2 × 4、3行目は3 × 4に対応します。最後の値には右側の要素がないので、後続和も寄与も0です。この4行で、6組を重複なく一度ずつ数えています。
ABC177 Cの条件と公式サンプル
ABC177 C – Sum of product of pairsは、N個の整数について、1 <= i < j <= Nを満たす全ての組のAi × Ajの和を109 + 7で割った余りを出力する問題です。入力は1行目がN、2行目がA1 ... ANです。
| 項目 | 公式の条件 |
|---|---|
N |
2 <= N <= 2 × 105 |
Ai |
0 <= Ai <= 109 |
| 法 | 109 + 7 |
| Time Limit | 2 sec |
| Memory Limit | 1024 MiB |
公式サンプル1は次の入力と出力です。入力の形は問題文のままです。
3
1 2 311この例では1 × 2 + 1 × 3 + 2 × 3 = 11となります。公式サンプル2も無加工で示します。
4
141421356 17320508 22360679 244949437235829式の導出と掲載コードの対応は、ABC177 Cの公式解説でも確認できます。
入力を読み、後続和を更新する完全なPython参考コード
コードでは、まず標準入力から整数を全て読みます。N = data[0]で個数を取り出し、A = data[1:1 + N]で問題文の配列をそのまま取り出します。問題の入力はこの1組だけなので、追加のクエリや位置更新を処理するコードは必要ありません。
import sys
MOD = 1_000_000_007
data = list(map(int, sys.stdin.buffer.read().split()))
N = data[0]
A = data[1:1 + N]
suffix_sum = sum(A) % MOD
answer = 0
for value in A:
suffix_sum = (suffix_sum - value) % MOD
answer = (answer + value * suffix_sum) % MOD
print(answer)suffix_sumは、処理前には現在値を含む残りの合計です。ループの最初でvalueを引くと、現在値より右だけの合計になります。その値をvalueに掛け、answerへ加えます。sum(A)、減算、乗算、累積加算の各所で法を適用しているため、保持する値は常に出力の余りとして扱えます。
不変条件で、各組を一度だけ数える
このループの正しさは、各反復の直前に成り立つ不変条件で説明できます。value = Aiを処理する直前、suffix_sumはAi + Ai+1 + ... + ANと法の下で同じ値です。最初は全体の合計なので成り立ち、前の反復で一つの現在値を引いた後は、次の位置から末尾までの合計が残ります。
このanswerの添字範囲も、掲載コードのループの向きに合わせて帰納的に確認できます。1-indexedで現在の左端iを処理する直前、answerは、1 <= p < q <= Nかつp < iを満たす積の総和です。式で書けば∑ Ap × Aq（条件 1 <= p < q <= N、p < i）です。suffix_sumからAiを引くと、∑q=i+1..N Aqが残ります。そこへAi × ∑q=i+1..N Aqを加えた直後は、同じ全ペア条件のうちp <= iを満たす積の総和、つまり∑ Ap × Aq（条件 1 <= p < q <= N、p <= i）です。i = Nでは引いた後の後続和が0で追加寄与も0ですが、p <= Nに広がったこの条件は全ての1 <= p < q <= Nを含むため、終了時のanswerは全ペアの積和に一致します。
現在値を先に引くと、suffix_sumはAi+1 + ... + ANになります。したがって、その反復で足すAi × suffix_sumは、iを左側の添字とする全ての組の積の和です。iを左から右へ進めると、任意の組(i, j)は小さい方の添字を処理した行でだけ現れます。大きい方の添字の行では、すでに左側にある要素を組み合わせないため、同じ組をもう一度足しません。
減算や乗算を各段階で法に対して行っても、元の値と同じ合同関係が保たれます。そのため、最後のanswerは問題が求める積和の余りです。
計算量と、制約の端で確認すること
配列全体の合計を一度計算し、配列を一度走査するため、時間計算量は O(N) です。入力を保持するdataとAの大きさはNに比例し、補助変数の数は一定なので、空間計算量はO(N)です。これは掲載したPythonコードの操作と保持するデータから導いており、特定環境での実測時間を保証するものではありません。
N = 2では、最初の値を引いた後に二つ目の値が残るため、最初の寄与が唯一の組A1 × A2になります。二つ目の反復では自分自身を引いて後続和が0になり、余分な組は加わりません。Ai = 0なら、その位置の寄与は0です。それでも現在値を後続和から引く更新は行います。更新を省くと、次の位置で右側の合計がずれます。- 最後の値を処理すると、現在値を引いた後の後続和は0です。ここで自分自身との積を足さないことが、
i < jの条件に対応します。 - 大きな合計に対しては、コードのように各更新で
109 + 7を適用します。入力の個数と値の範囲は、問題文に合わせてN個の整数として扱います。 - 同じ値でも、位置が異なり
i < jを満たすなら、通常の一組としてAi × Ajを数えます。
この問題には位置の更新や順位の問い合わせがないため、後続和を一つ持つ方法で足ります。残りを一つの集約値にできない問題へ、BITやセグメント木などの別の構造を追加する説明は、ここでは扱いません。
次はABC206 Cで、集約する対象を変える
次の練習には、ABC206 C – Swappableを選べます。ここではi < jかつAi ≠ Ajを満たす組の数を求めます。公式サンプル1は次のとおりです。
3
1 7 12(1, 2)と(2, 3)は異なる値なので数え、(1, 3)は同じ値なので数えません。この区別を確認したうえで、ABC177 Cで右側の合計を集約したのと同じように、ABC206 Cでは値ごとの出現回数を集約します。ABC206 Cの制約は2 <= N <= 3 × 105、1 <= Ai <= 109です。公式解説の方法では、頻度をmapで数えるとO(N)、配列をsortしてから数えるとO(N log N)です。公式解説は、全組数から同値の組を引く方法を示しており、値の出現回数をqとすると同値ペアはq × (q - 1) / 2です。まずこの式を紙で追い、重複値を二重に数えないことを確かめてからコードへ進む、という目的で選ぶ一問です。この記事ではABC206 Cの完全解答までは扱いません。
ABC206 Cの公式解説には、頻度を使う方法と、ソートまたはmapを使う場合の計算量の説明があります。ABC177 Cの後続和からABC206 Cの値の頻度へ、集約する対象が変わる点を意識すると、寄与を分けて数える発想を別の条件で試せます。
