Hinweis) Das Antwortbeispiel lautet nur Python3 </ b>. Für C ++ und Java wird empfohlen, den Code aus "Alle Übermittlungen" anzuzeigen und zu implementieren.
Hallo allerseits (wer nach dem Wettbewerb Guten Abend!) Ist Rute!
AtCoder Beginner Contest 177 C Ich bin dabei, das Problem zu erklären! Die Erklärung der Probleme A und C finden Sie unter den folgenden Links. Überprüfen Sie dies bitte! !!
| Ein Problem | B Problem | C Problem |
|---|---|---|
| in Vorbereitung | in Vorbereitung | Dieser Beitrag |
Bei einer Folge von Zahlen, die aus $ N $ ganzen Zahlen $ A_1, ... A_N $ bestehen. Finden Sie die Summe von $ A_i × A_j $ für alle Paare $ (i, j) $, die $ 1 \ leq i <j \ leq N $ mit $ mod (10 ^ 9 + 7) $ erfüllen.
Problem-URL: https://atcoder.jp/contests/abc177/tasks/abc177_c
・ $ 2 \ leq N \ leq 2 × 10 ^ 5 $ ・ $ 0 \ leq A_i \ leq 10 ^ 9 $ ・ Alle Eingänge sind ganze Zahlen
Von $ A_1, ... A_N $ ist das Paar $ (i, j) $ $ (N-1) + (N-2) + .... 1 $ Paar und $ \ frac {N (N (N)) Sie können sehen, dass es -1)} {2} $ Paare gibt. Wenn Sie über diese $ 1 $ nachdenken und rechnen, benötigen Sie den Betrag von $ O (N ^ 2) $. Im Allgemeinen beträgt die Anzahl der Berechnungen, die von einem Computer pro Sekunde verarbeitet werden können, etwa 10 ^ 8 $ (100 Millionen Mal). Aufgrund von Einschränkungen überschreitet dieser Rechenaufwand das Ausführungszeitlimit </ b>.
Betrachten wir das Problem nun aus einer anderen Perspektive.
In Eingabebeispiel 1 und Ausgabebeispiel 1 lautet die Antwort $ 11 $,
Über die Antwort
\sum_{i = 1}^{N-1} \sum_{j = i+1}^{N} A_i A_j
ich weiß das
Denken wir also zuerst darüber nach, $ \ sum_ {j = i + 1} ^ {N} A_j $ zu finden.
Die hier verwendete Technik heißt kumulative Summe </ b> </ font>.
Die kumulative Summe besteht darin, die Summe vom ersten Term bis zu einem bestimmten Term im Voraus zu ermitteln und eine Zahlenfolge dafür zu erstellen.
Als Beispiel für eine durch die kumulative Summe erstellte Zahlenspalte gilt:
Bei gegebener Reihenfolge $ B
Weitere Informationen finden Sie unter Kenchon-sans Artikel über die kumulative Summe.
Die kumulative Summe, die wir dieses Mal betrachten, ist eine Folge von Zahlen mit einer Länge von $ N-1 $.
Sie haben jetzt eine Folge von $ \ sum_ {j = i + 1} ^ {N} A_j $. Nennen wir diese Zahlenspalte $ C $.
Nächster,
\sum_{i = 1}^{N-1} \sum_{j = i+1}^{N} A_i A_j
Berechnen Sie $ A_i x C_i $ für jedes zu findende $ i (1 \ leq i \ leq N-1) $. Fügen Sie diesen Wert zum Wert der gesuchten Antwort hinzu.
Teilen Sie abschließend den Antwortwert durch $ (10 ^ 9 + 7) $ und geben Sie den Rest aus.
Hier ist es im Fall von Python nicht erforderlich, die Antwort jedes Mal durch $ (10 ^ 9 + 7) $ zu teilen, da sie Ganzzahlen mit mehreren Längen entspricht, aber im Fall von C ++ und Java befindet sie sich mitten in der Berechnung. Die Antwort ist möglicherweise größer als der Bereich des 64-Bit-Integer-Typs. </ b> (long, long long int usw.) (sogenannter Überlauf </ b>)
Dies liegt daran, dass $ 2 ^ {63} -1 \ simeq 9,22 × 10 ^ {18} $, aber aufgrund der Beschränkung von $ A_i $ ist es möglich, dass $ 10 ^ {18} $ mehr als $ 10 $ mal hinzugefügt werden. ist.
Selbst wenn Sie den Wert nach dem Hinzufügen jedes Mal durch $ 10 ^ 9 + 7 $ teilen, ist er am Ende derselbe. Wenn Sie ihn also weiterhin durch $ 10 ^ 9 + 7 $ teilen, Überlauf Sie müssen sich keine Sorgen um </ b> machen.
Der Berechnungsbetrag beträgt $ O (N) $ in der kumulativen Summenverarbeitung und kostet $ O (1) $ bei der Berechnung von $ A_i × C_i $ für jedes $ i (1 \ leq i \ leq N-1) $. Es wird $ O (N) $.
Das Folgende ist ein Beispiel für die Antwort in Pyhton3, C ++, Java. (Ab dem 30.08. Um 11:29 Uhr wird nur das Antwortbeispiel für Python3 angezeigt. C ++ und Java werden erstellt, sobald sie fertig sind. Warten Sie daher bitte auf das Update.)
{ABC177C.py}
N = int(input()) #Ganzzahl zur Eingabe
A = list(map(int,input().split())) #Zahlenfolge zur Eingabe von A.
SUMA = sum(A) #Summe der Zahlen
MOD = 10**9 + 7 # mod
C = [0] * (N-1) #Spalte mit der kumulativen Summennummer
for i in range(N-1): #\sum_{j = i+1}^{N}Und ordne es einer Folge von Zahlen zu
SUMA -= A[i]
C[i] = SUMA
ans = 0 #Die Antwort, die Sie suchen
for i in range(N-1):
ans += A[i]*C[i]
ans %= MOD #Teilen Sie jedes Mal durch Mod
print(ans) #Geben Sie die Antwort aus
#Der Berechnungsbetrag beträgt O.(N)ist.
in Vorbereitung
in Vorbereitung