[PYTHON] AtCoder Beginner Contest 177 Problem C Ich habe versucht herauszufinden, warum es falsch war

Einführung

In Problem C des Wettbewerbs177 vom 29. August 2020 war ich verzweifelt und habe es untersucht.

Problem

https://atcoder.jp/contests/abc177/tasks/abc177_c

Gedanken

Bei richtiger Berechnung dachte ich, es wäre wahrscheinlich TLE. Aber mit ein wenig Einfallsreichtum scheint es ganz so.

Denken Sie eine Weile nach.

Wir kamen zu dem Schluss, dass die gewünschte Summe {(A1 + A2 + ... + An) ^ 2- (A1 ^ 2 + A2 ^ 2 + ... + An ^ 2)} ÷ 2 war, und codierten sie. Fertig in ca. 10 Minuten.

c.py

n = int(input())
l = input()
a = l.split(' ')

tmp = 0
tmp2 = 0

for i in range(n):
    tmp += int(a[i])

for i in range(n):
    tmp2 += int(a[i])*int(a[i])

print(int((tmp*tmp-tmp2)/2)%1000000007)

Okay, ich bin heute in guter Verfassung! Möglicherweise können Sie 4 Fragen stellen! Sobald ich dachte, war das Urteil unerbittlich. Hier friert es ein und der Tag endet mit zwei Fragen.

Warum

Nachdem der Wettbewerb beendet ist, lesen Sie den Kommentar. weiß nicht. Warum? Sowohl die kumulative Summe als auch diese Berechnungsmethode sollten mathematisch den gleichen Wert haben. Ich war am Samstag sowieso nicht überzeugt, also habe ich geschlafen, mich beruhigt, Ich habe am Sonntag eine kumulative japanische Version geschrieben und eingereicht.

c_.py

n = int(input())
l = input()
a = l.split(' ')

tmp = 0
total2 = 0

for i in range(n):
    tmp += int(a[i])

for i in range(n):
    total2 += int(a[i])*(tmp-int(a[i]))
    tmp -= int(a[i])

print(total2%1000000007)

** Yeah yeah yeah yeah yeah yeah **

Warum? Warum machst du das Gleiche, einer ist WA und der andere ist AC? ?? ??

Ich habe verschiedene Dinge ausprobiert

Zuerst habe ich überprüft, wie groß eine int-Typ-Nummer von Python verarbeitet werden kann. Daher können Sie in Python Ver3 so viele Werte verwenden, wie der Speicher zulässt. Was dann seltsam ist, ist ÷ 2? Ich bin sicher, dass etwas Seltsames passiert, wenn die Zahlen groß sind.

Ich habe 10 Zahlen geeigneter Größe eingegeben und die Zahl vor dem Teilen durch 2 und die Zahl beim Teilen durch 2 angezeigt.

input_data1

10
1234567 2345678 3456789 4567890 5678901 6789012 7890123 8901234 9012345 1111111

2257615544087530
1128807772043765

Das sieht okay aus. Machen wir es etwas größer.

input_data2

10
12345678 23456789 34567890 45678901 56789012 67890123 78901234 89012345 90123456 11111111

225761590208477104
112880795104238560

Wenn man sich die Stelle der 1 ansieht, ist es 4, bevor man durch 2 teilt. Was also durch 2 geteilt wird, sollte 2 oder 7 sein. Noch 0. Wenn Sie also eine große Zahl durch 2 teilen, scheint etwas Seltsames zu passieren.

Warum bricht es nicht bei 2

Als ich gegoogelt habe "Python Division ist seltsam", habe ich den folgenden Artikel gefunden.

Das Ergebnis einer riesigen schwebenden Dezimalberechnung war in Python3 seltsam, daher habe ich versucht, den Grund herauszufinden https://paiza.hatenablog.com/entry/2017/08/01/Python3%E3%81%A7%E5%B7%A8%E5%A4%A7%E3%81%AA%E6%B5%AE%E5%8B%95%E5%B0%8F%E6%95%B0%E8%A8%88%E7%AE%97%E3%81%AE%E7%B5%90%E6%9E%9C%E3%81%8C%E5%A4%89%E3%81%A0%E3%81%A3%E3%81%9F%E3%81%AE%E3%81%A7%E7%90%86

Nun, ich verstehe ... aber ich verstehe immer noch nicht. .. .. Die großen Zahlen bedeuten jedoch, dass seltsame Dinge passieren können, wenn Sie sie teilen. Ich bin schlauer geworden. Vielen Dank.

... Ah, bedauerlich.