Lorsque les problèmes suivants ont été posés dans AtCoder, je n'ai pas pu aider du tout, je vais donc résumer la théorie et sa mise en œuvre.
Multiple of 2019 ( AtCoder Beginner Contest 164; Problem D )
Énoncé du problème Étant donné la chaîne S, qui se compose uniquement de nombres de 1 à 9. Un ensemble d'entiers qui satisfont les conditions suivantes(i,j) (1≤i≤j≤|S|)Trouvez le nombre total de fichiers.
Condition: Si vous regardez les i-ième à j-ième lettres de S comme des entiers décimaux, cet entier est un multiple de 2019.
Contrainte 1≤|S|≤200000 S est une chaîne composée uniquement de nombres de 1 à 9
Il est possible de calculer en empilant simplement pour des boucles en plusieurs couches, mais dans le cas d'AtCoder, il est nécessaire de le concevoir car il dépasse la limite supérieure du temps de calcul.
Pour ce genre de problème de calcul de multiples (ou de réflexion sur les nombres de base?), Vous pouvez écrire un programme efficace par un algorithme qui fait bon usage du calcul mod.
a \equiv b \pmod{ 2019 } \\
c \equiv d \pmod{ 2019 }
Quand
a + c \equiv b + d \pmod{ 2019 } \\
a - c \equiv b - d \pmod{ 2019 } \\
a * c \equiv b * d \pmod{ 2019 }
Est établi. En d'autres termes, les formules de somme, de différence et de produit dans les opérations ordinaires à quatre règles peuvent être appliquées au calcul de mod.
À propos, les règles suivantes s'appliquent également aux quotients.
Si $ ab \ equiv ac $ et $ a $ et $ p $ s'excluent mutuellement, alors $ b \ equiv c $
Compte tenu de la chaîne $ S $
S = s_n s_{n-1} \dots s_2 s_1
Supposer que En d'autres termes, contrairement au problème, envisagez de définir $ i <j $. Quel est l'ensemble $ (i, j) $ qui remplit les conditions du problème?
N_{ij} = 10^{i-j} s_i + 10^{i-j-1} s_{i+1} + \dots + 10 s_{j+1} + s_j
Est un multiple de 2019. Il est nécessaire de compter l'ensemble $ (i, j) $ de cette condition. Tout d'abord, définissez les $ r_i $ et $ t_i $ suivants.
t_i = 10^{i-1} \\
r_i = t_i s_i + t_{i-1} s_{i-1} + \dots + t_1 s_1
Ce $ r_i $ peut également être écrit comme suit.
r_i = t_i s_i + r_{i-1}
À ce stade, l'équation suivante est vraie.
r_{i} \equiv r_{j-1} \Rightarrow N_{ij} \equiv 0 \pmod{ 2019 }
Cette preuve est présentée ci-dessous. La relation suivante est valable entre $ r_i $ et $ N_ {ij} $.
r_{i} - r_{j-1} = N_{ij} * 10^{j-1}
Si $ r_ {i} \ equiv r_ {j-1} $
r_{i} - r_{j-1} = N_{ij} * 10^{j-1} \equiv 0 \pmod{ 2019 }
Parce que ça devient
N_{ij} \equiv 0 \pmod{ 2019 }
Ou
10^{j-1} \equiv 0 \pmod{ 2019 }
Devrait tenir. Mais puisque $ 10 ^ {j-1} = 2 ^ {j-1} * 5 ^ {j-1} $, $ 2019 $ et $ 10 ^ {j-1} $ s'excluent clairement mutuellement, le premier $ N_ {ij} \ equiv 0 $ tiendra.
r_i \equiv R_i \pmod{ 2019 } \\
s_i \equiv S_i \pmod{ 2019 } \\
t_i \equiv T_i \pmod{ 2019 }
Cependant, $ R_i, S_i, T_i $ représentent le reste, qui est $ 0 \ le R_i, S_i, T_i \ le 2018 $. En utilisant ces caractères, le reste de chaque $ r_i $ peut être calculé en continu comme suit.
\begin{align}
r_i &= t_i s_i + r_{i-1} \\
& \equiv T_i S_i + R_{i-1} = R_i \pmod{ 2019 } \\
\end{align}
Vous pouvez utiliser cette méthode pour calculer le reste pour chaque $ r_i $ pour 2019 et compter les combinaisons de $ r_i $ avec le même reste pour calculer la réponse.
En utilisant l'algorithme ci-dessus, il est possible de calculer sans chevauchement pour les boucles.
s = input()
d = [ int( 0 ) ] * 2019
d[ 0 ] = int( 1 )
r = int( 0 )
t = int( 1 )
for si in reversed( s ):
# print( si )
r = int( si ) * t + r
r = r % 2019
t = t * 10
t = t % 2019
d[ r ] = d[ r ] + 1
ans = int( 0 )
for di in d:
ans = ans + di * ( di - 1 ) // 2
print( ans )
Recommended Posts