introduction

J'étais désespérément accro au problème C du concours177 tenu le 29 août 2020, alors j'ai enquêté dessus.

problème

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

Pensées

Lorsque calculé correctement, je pensais que ce serait probablement TLE. Mais avec un peu d'ingéniosité, cela semble tout à fait vrai.

Réfléchissez un moment.

Nous sommes arrivés à la conclusion que la somme souhaitée était {(A1 + A2 +… + An) ^ 2- (A1 ^ 2 + A2 ^ 2 +… + An ^ 2)} ÷ 2, et l'avons codée. Terminé en 10 minutes environ.

`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)

D'accord, je suis en forme aujourd'hui! Vous pourrez peut-être poser 4 questions! Dès que j'ai pensé, le jugement était implacable. Il se fige ici et la journée se termine par deux questions.

Pourquoi

Une fois le concours terminé, consultez le commentaire. ne sait pas. Pourquoi? La somme cumulée et cette méthode de calcul doivent avoir mathématiquement la même valeur. Je n'étais pas convaincu samedi de toute façon, alors j'ai dormi, je me suis calmé, J'ai écrit une version japonaise cumulative dimanche et je l'ai soumise.

`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)

** Ouais ouais ouais ouais ouais ouais **

Pourquoi? Pourquoi faites-vous la même chose, l'un est WA et l'autre est AC? ?? ??

J'ai essayé diverses choses

Tout d'abord, j'ai vérifié la taille d'un nombre de type int pouvant être gérée par python. En conséquence, dans python ver3, vous pouvez utiliser autant de valeurs que la mémoire le permet. Alors, qu'est-ce qui est étrange est ÷ 2? Je suis sûr que quelque chose d'étrange se produit lorsque les chiffres sont élevés.

J'ai entré 10 nombres de taille appropriée et affiché le nombre avant de diviser par 2 et le nombre lors de la division par 2.

`input_data1`


10
1234567 2345678 3456789 4567890 5678901 6789012 7890123 8901234 9012345 1111111

2257615544087530
1128807772043765

Cela semble correct. Faisons un peu plus grand.

`input_data2`


10
12345678 23456789 34567890 45678901 56789012 67890123 78901234 89012345 90123456 11111111

225761590208477104
112880795104238560

En regardant la place du 1, il est 4 avant de diviser par 2, donc ce qui est divisé par 2 devrait être 2 ou 7. Pourtant 0. Donc, si vous divisez un grand nombre par 2, quelque chose d'étrange semble se produire.

Pourquoi ça ne casse pas à 2

Quand j'ai googlé "la division python est étrange", j'ai trouvé l'article suivant.

Le résultat d'un énorme calcul décimal flottant était étrange dans Python3, j'ai donc essayé de trouver la raison 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

Eh bien, je comprends ... mais je ne comprends toujours pas. .. .. Cependant, les grands nombres signifient que des choses étranges peuvent se produire lorsque vous les divisez. Je suis devenu plus intelligent. Merci beaucoup.

... Ah, regrettable.

AtCoder Beginner Contest 177 Problème C J'ai essayé de découvrir pourquoi c'était faux