Remarque) L'exemple de réponse est uniquement Python3 </ b>. Pour C ++ et Java, il est recommandé de voir le code de «Toutes les soumissions» et de l'implémenter.
Salut à tous (qui après le concours Bonsoir!) C'est Rute!
AtCoder Beginner Contest 177 C Je vais commencer à expliquer le problème! Vous pouvez voir l'explication des problèmes A et C à partir des liens ci-dessous, veuillez donc vérifier! !!
| Un problème | Problème B | Problème C |
|---|---|---|
| en préparation | en préparation | Cet article |
Étant donné une suite de nombres composée de $ N $ entiers $ A_1, ... A_N $. Trouvez la somme de $ A_i × A_j $ pour toutes les paires $ (i, j) $ qui satisfont $ 1 \ leq i <j \ leq N $ avec $ mod (10 ^ 9 + 7) $.
URL du problème: https://atcoder.jp/contests/abc177/tasks/abc177_c
・ $ 2 \ leq N \ leq 2 × 10 ^ 5 $ ・ $ 0 \ leq A_i \ leq 10 ^ 9 $ ・ Toutes les entrées sont des entiers
De $ A_1, ... A_N $, la paire $ (i, j) $ est $ (N-1) + (N-2) + .... 1 $ paire, et $ \ frac {N (N (N) Vous pouvez voir qu'il y a -1)} {2} $ paires. Si vous pensez à ceux-ci de 1 $ et calculez, vous aurez besoin du montant de $ O (N ^ 2) $. En règle générale, le nombre de calculs qu'un ordinateur peut traiter par seconde est d'environ 10 ^ 8 $ (100 millions de fois), donc en raison de restrictions, ce montant de calcul dépassera le délai d'exécution </ b>.
Considérons maintenant le problème sous un angle différent.
Dans l'exemple d'entrée 1 et l'exemple de sortie 1, la réponse est 11 $,
À propos de la réponse
\sum_{i = 1}^{N-1} \sum_{j = i+1}^{N} A_i A_j
je le sais
Alors, tout d'abord, pensons à trouver $ \ sum_ {j = i + 1} ^ {N} A_j $.
La technique utilisée ici est appelée somme cumulée </ b> </ font>.
La somme cumulative consiste à trouver la somme du premier terme à un certain terme à l'avance et à créer une séquence de nombres pour elle.
À titre d'exemple de colonne numérique créée par somme cumulée,
Étant donné la séquence $ B
Pour plus de détails, consultez l'article de Kenchon-san sur la somme cumulée.
La somme cumulative que nous considérons cette fois est une suite de nombres d'une longueur de $ N-1 $.
Vous avez maintenant une séquence de $ \ sum_ {j = i + 1} ^ {N} A_j $. Appelons cette colonne numérique $ C $.
prochain,
\sum_{i = 1}^{N-1} \sum_{j = i+1}^{N} A_i A_j
Calculez $ A_i x C_i $ pour chaque $ i (1 \ leq i \ leq N-1) $ à trouver. Ajoutez cette valeur à la valeur de la réponse que vous recherchez.
Enfin, divisez la valeur de la réponse par $ (10 ^ 9 + 7) $ et affichez le reste.
Ici, dans le cas de Python, il n'est pas nécessaire de diviser la réponse par $ (10 ^ 9 + 7) $ à chaque fois car cela correspond à plusieurs entiers de longueur, mais dans le cas de C ++ et Java, c'est au milieu du calcul. La réponse peut être plus large que la plage de type entier 64 bits. </ b> (long, long long int, etc.) (soi-disant débordement </ b>)
C'est parce que $ 2 ^ {63} -1 \ simeq 9,22 × 10 ^ {18} $, mais en raison de la limitation de $ A_i $, il est possible que $ 10 ^ {18} $ puisse être ajouté plus de 10 $ fois. est.
Après tout, même si vous continuez à diviser la valeur par 10 $ ^ 9 + 7 $ à chaque fois après l'avoir ajoutée, ce sera la même chose à la fin, donc si vous continuez à la diviser par 10 $ ^ 9 + 7 $, débordement Vous n'avez pas à vous soucier de </ b>.
Le montant du calcul est $ O (N) $ dans le traitement de la somme cumulative, et il en coûte $ O (1) $ lors du calcul de $ A_i × C_i $ pour chaque $ i (1 \ leq i \ leq N-1) $. Cela devient $ O (N) $.
Ce qui suit est un exemple de réponse dans Pyhton3, C ++, Java. (À partir du 30/08 11:29, seul l'exemple de réponse de Python3 est affiché. C ++ et Java seront créés dès qu'ils seront prêts, veuillez donc attendre la mise à jour)
{ABC177C.py}
N = int(input()) #Entier à saisir
A = list(map(int,input().split())) #Chaîne numérique à saisir A
SUMA = sum(A) #Somme des nombres
MOD = 10**9 + 7 # mod
C = [0] * (N-1) #Colonne du nombre de somme cumulée
for i in range(N-1): #\sum_{j = i+1}^{N}Et assignez-le à une séquence de nombres
SUMA -= A[i]
C[i] = SUMA
ans = 0 #La réponse que vous cherchez
for i in range(N-1):
ans += A[i]*C[i]
ans %= MOD #Divisez par mod à chaque fois
print(ans) #Sortez la réponse
#Le montant du calcul est O(N)est.
en préparation
en préparation
Recommended Posts