#51 Problème
** Pensées ** Dans la production, j'ai recherché $ i, j $ complètement et TLE. Le montant du calcul est de $ O ((2 * 10 ^ 5) ^ {2}) $. Avec la limitation de ce problème, il ne passera pas à moins qu'il ne soit supprimé à environ $ O (N) $.
Les nombres exprimés en décimal peuvent être exprimés comme $ a_i * 10 ^ n + a_ {i-1} * 10 ^ {n-1} \ cdots a_0 * 10 ^ 0 $. Si la chaîne de caractères $ S $ de longueur $ N $ est divisée par $ i $ th à partir de la droite et la chaîne de caractères est $ S_i $, $ S_i $ est $ S_0 + S_1 * 10 ^ 1 \ cdots S_i * 10 ^ { Il peut être exprimé par Ni} $. Puisqu'il n'est pas possible de combiner des caractères séparément, la chaîne de caractères $ S_ {ij} $ dans l'intervalle de $ i, j, i <j $ in $ S $ est $ S_ {ij} = \ frac {S_ {j } -S_ {i}} {10 ^ i} $ peut être écrit. Où $ 2019,10 ^ i $ sont les uns par rapport aux autres (l'engagement maximal est de 1). Par conséquent, pour déterminer si $ S_ {ij} $ est un multiple de 2019, le dénominateur de l'équation précédente ($ \ frac {S_ {j} -S_ {i}} {10 ^ i} $) est un multiple de 2019. C'est la même valeur que le jugement qu'il y a. De plus, si vous soustrayez deux nombres différents avec le même reste divisé par 2019, vous obtenez un nombre divisible par 2019. Donc, enregistrez $ S_ {i} mod (2019) $ de $ i $ respectivement. Je suis tombé sur une liste pour enregistrer le reste. Le reste $ m $ divisé par 2019 sera naturellement 0 $ \ leq m <2019 $, mais seulement lorsque le reste est égal à 0, $ S_i $ seul peut être un multiple de 2019. Par conséquent, le terme du reste 0 dans la liste qui enregistre le reste doit être +1 au début. Ce +1 a une chaîne de caractères de longueur 0, et quand il est trop 0, il est associé à une chaîne de caractères de longueur 0 → On a l'impression que ce sera un multiple de 2019 par lui-même. La formule pour calculer la combinaison est $ n \ * (n-1) $ en transformant $ {} _n C _2 $.
s = input()
t, a = 0, 1
mod = [0]*2019
mod[0] = 1 #Premier élément(Reste 0)Est+1
s = s[::-1] #Il est plus facile de classer si vous regardez de derrière, alors inversez
n = len(s)
for i in range(n):
t += int(s[i]) * a
t %= 2019
a *= 10
a %= 2019 #Parce qu'ils sont tous les deux%La réponse t ne change pas même si 2019 est calculé
mod[t] += 1
ans = 0
for i in range(2019):
ans += mod[i]*(mod[i]-1)//2 #Calcul des combinaisons
print(ans)
Dois-je écrire t, a = 0, 1 sur une autre ligne? Je ne l'ai pas trouvé dans PEP8.
Je voulais le résoudre en production. Je suis plus heureux cette semaine parce que j'ai deux ABC donc je vais prendre un thé. à plus.
Recommended Posts