Problème de calcul avec le mod

en premier

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

théorie

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.

formule de base 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 $

Application à ce problème

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.

algorithme

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.

la mise en oeuvre

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

Problème de calcul avec le mod
Mesure du temps de calcul à l'aide de maf
AtCoder ABC156 Problème D Calcul et séquence du module Bouquet, etc.
[Problème d'optimisation mathématique] Méthode de programmation linéaire utilisant PuLP
[Calcul scientifique / technique par Python] Résolution de problèmes de valeurs propres (généralisés) en utilisant numpy / scipy, en utilisant des bibliothèques