Als die folgenden Probleme in AtCoder gestellt wurden, konnte ich überhaupt nicht helfen, daher werde ich die Theorie und ihre Implementierung zusammenfassen.
Multiple of 2019 ( AtCoder Beginner Contest 164; Problem D )
Gegeben ist die Zeichenfolge S, die nur aus Zahlen von 1 bis 9 besteht. Eine Reihe von Ganzzahlen, die die folgenden Bedingungen erfüllen(i,j) (1≤i≤j≤|S|)Finden Sie die Gesamtzahl von.
Bedingung: Wenn Sie die i-ten bis j-ten Buchstaben von S als Dezimalzahlen betrachten, ist diese Ganzzahl ein Vielfaches von 2019.
Zwang 1≤|S|≤200000 S ist eine Zeichenfolge, die nur aus Zahlen von 1 bis 9 besteht
Es ist möglich, durch einfaches Stapeln von Schleifen in mehreren Schichten zu berechnen. Im Fall von AtCoder ist jedoch eine Berechnung erforderlich, da diese die Obergrenze der Berechnungszeit überschreitet.
Für diese Art von Problem der Berechnung von Vielfachen (oder des Denkens an Basiszahlen?) Können Sie ein effizientes Programm mit einem Algorithmus schreiben, der die Mod-Berechnung gut nutzt.
a \equiv b \pmod{ 2019 } \\
c \equiv d \pmod{ 2019 }
Wann
a + c \equiv b + d \pmod{ 2019 } \\
a - c \equiv b - d \pmod{ 2019 } \\
a * c \equiv b * d \pmod{ 2019 }
Ist festgelegt. Mit anderen Worten, die Summen-, Differenz- und Produktformeln in gewöhnlichen Operationen mit vier Regeln können auf die Berechnung von mod angewendet werden.
Die folgenden Regeln gelten übrigens auch für Quotienten.
Wenn sich $ ab \ equiv ac $ und $ a $ und $ p $ gegenseitig ausschließen, dann $ b \ equiv c $
S = s_n s_{n-1} \dots s_2 s_1
N_{ij} = 10^{i-j} s_i + 10^{i-j-1} s_{i+1} + \dots + 10 s_{j+1} + s_j
Nehme an, dass Mit anderen Worten, im Gegensatz zum Problem sollten Sie $ i <j $ setzen. Die Menge $ (i, j) $, die die fragliche Bedingung erfüllt, ist ein Vielfaches von 2019. Es ist erforderlich, die Menge $ (i, j) $ dieser Bedingung zu zählen. Definieren Sie zunächst die folgenden $ r_i $ und $ t_i $.
t_i = 10^{i-1} \\
r_i = t_i s_i + t_{i-1} s_{i-1} + \dots + t_1 s_1
Dieses $ r_i $ kann auch wie folgt geschrieben werden.
r_i = t_i s_i + r_{i-1}
Zu diesem Zeitpunkt gilt die folgende Gleichung.
r_{i} \equiv r_{j-1} \Rightarrow N_{ij} \equiv 0 \pmod{ 2019 }
Dieser Beweis ist unten gezeigt. Die folgende Beziehung gilt zwischen $ r_i $ und $ N_ {ij} $.
r_{i} - r_{j-1} = N_{ij} * 10^{j-1}
Wenn $ r_ {i} \ equiv r_ {j-1} $
r_{i} - r_{j-1} = N_{ij} * 10^{j-1} \equiv 0 \pmod{ 2019 }
Weil es wird
N_{ij} \equiv 0 \pmod{ 2019 }
Oder
10^{j-1} \equiv 0 \pmod{ 2019 }
Sollte halten. Aber da $ 10 ^ {j-1} = 2 ^ {j-1} * 5 ^ {j-1} $, schließen sich $ 2019 $ und $ 10 ^ {j-1} $ eindeutig gegenseitig aus, erstere $ N_ {ij} \ equiv 0 $ gilt.
r_i \equiv R_i \pmod{ 2019 } \\
s_i \equiv S_i \pmod{ 2019 } \\
t_i \equiv T_i \pmod{ 2019 }
$ R_i, S_i, T_i $ stellen jedoch den Rest dar, der $ 0 \ le R_i, S_i, T_i \ le 2018 $ ist. Mit diesen Zeichen kann der Rest jedes $ r_i $ kontinuierlich wie folgt berechnet werden.
\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}
Mit dieser Methode können Sie den Rest für jedes $ r_i $ für 2019 berechnen und die Kombinationen von $ r_i $ mit demselben Rest zählen, um die Antwort zu berechnen.
Unter Verwendung des obigen Algorithmus ist es möglich, ohne Überlappung für Schleifen zu berechnen.
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