#51 Problem
** Gedanken ** In der Produktion habe ich $ i, j $ vollständig und TLE durchsucht. Der Berechnungsbetrag beträgt $ O ((2 * 10 ^ 5) ^ {2}) $. Mit der Einschränkung dieses Problems wird es nicht bestanden, es sei denn, es wird auf ungefähr $ O (N) $ unterdrückt.
In Dezimalzahlen ausgedrückte Zahlen können ausgedrückt werden als $ a_i * 10 ^ n + a_ {i-1} * 10 ^ {n-1} \ cdots a_0 * 10 ^ 0 $. Wenn die Zeichenkette $ S $ der Länge $ N $ durch das $ i $ th von rechts geteilt wird und die Zeichenkette $ S_i $ ist, ist $ S_i $ $ S_0 + S_1 * 10 ^ 1 \ cdots S_i * 10 ^ { Es kann als Ni} $ ausgedrückt werden. Da es nicht möglich ist, Zeichen separat zu kombinieren, ist die Zeichenfolge $ S_ {ij} $ im Intervall von $ i, j, i <j $ in $ S $ $ S_ {ij} = \ frac {S_ {j } -S_ {i}} {10 ^ i} $ kann geschrieben werden. Wobei $ 2019,10 ^ i $ zueinander stehen (maximale Verpflichtung ist 1). Um zu bestimmen, ob $ S_ {ij} $ ein Vielfaches von 2019 ist, ist der Nenner der vorherigen Gleichung ($ \ frac {S_ {j} -S_ {i}} {10 ^ i} $) ein Vielfaches von 2019. Es ist der gleiche Wert wie das Urteil, das es gibt. Wenn Sie zwei verschiedene Zahlen mit demselben Rest geteilt durch 2019 subtrahieren, erhalten Sie eine Zahl, die durch 2019 teilbar ist. Nehmen Sie also $ S_ {i} mod (2019) $ von $ i $ auf. Ich stolperte über eine Liste, um den Rest aufzuzeichnen. Der Rest $ m $ geteilt durch 2019 wird natürlich $ 0 \ leq m <2019 $ sein, aber nur wenn der Rest 0 ist, kann $ S_i $ allein ein Vielfaches von 2019 sein. Fügen Sie daher dem Element +1 mit einem Rest von 0 in der Liste hinzu, in der der Rest aufgezeichnet wird. Diese +1 hat eine Zeichenkette mit der Länge 0, und wenn sie zu 0 ist, wird sie mit einer Zeichenkette mit der Länge 0 gepaart. → Ich denke, es wird ein Vielfaches von 2019 für sich sein. Die Formel zur Berechnung der Kombination lautet $ n \ * (n-1) $ durch Transformation von $ {} _n C _2 $.
s = input()
t, a = 0, 1
mod = [0]*2019
mod[0] = 1 #Erstes Element(Rest 0)Ist+1
s = s[::-1] #Es ist einfacher zu ranken, wenn Sie von hinten schauen, also umgekehrt
n = len(s)
for i in range(n):
t += int(s[i]) * a
t %= 2019
a *= 10
a %= 2019 #Weil sie beide sind%Die Antwort t ändert sich auch dann nicht, wenn 2019 berechnet wird
mod[t] += 1
ans = 0
for i in range(2019):
ans += mod[i]*(mod[i]-1)//2 #Berechnung von Kombinationen
print(ans)
Soll ich t, a = 0, 1 in eine andere Zeile schreiben? Ich konnte es in PEP8 nicht finden.
Ich wollte es in der Produktion lösen. Ich bin diese Woche am glücklichsten, weil ich zwei ABCs habe, also werde ich einen Tee trinken. wir sehen uns.
Recommended Posts