Daily AtCoder # 51 in Python

Introduction

** Thoughts ** In the production, I searched $ i and j $ completely and TLE. The amount of calculation is $ O ((2 * 10 ^ 5) ^ {2}) $. The constraint of this problem is that it will not pass unless it is suppressed to about $ O (N) $.

Numbers expressed in decimal numbers can be represented as $ a_i * 10 ^ n + a_ {i-1} * 10 ^ {n-1} \ cdots a_0 * 10 ^ 0 $. If the character string $ S $ of length $ N $ is divided by the $ i $ th from the right and the character string is $ S_i $, then $ S_i $ is $ S_0 + S_1 * 10 ^ 1 \ cdots S_i * 10 ^ { It can be expressed as Ni} $. Since it is not possible to combine characters separately, the character string $ S_ {ij} $ in the interval of $ i, j, i <j $ in $ S $ is $ S_ {ij} = \ frac {S_ {j }-S_ {i}} {10 ^ i} $ can be written. Where $ 2019,10 ^ i $ are relatively prime (greatest common divisor is 1). Therefore, to determine if $ S_ {ij} $ is a multiple of 2019, the denominator of the previous equation ($ \ frac {S_ {j} -S_ {i}} {10 ^ i} $) is a multiple of 2019. It is the same value as the judgment that there is. Also, if you subtract two different numbers that have the same remainder divided by 2019, you get a number that is divisible by 2019. So, record $ S_ {i} mod (2019) $ of $ i $ respectively. I stumbled upon making a list to record the remainder. Of course, the remainder $ m $ divided by 2019 is $ 0 \ leq m <2019 $, but only when the remainder is 0, $ S_i $ alone can be a multiple of 2019. So, add +1 to the 0 term of the list that records the remainder first. This +1 has a character string of length 0, and when it is too 0, it is paired with a character string of length 0 → I feel that it will be a multiple of 2019 by itself. The formula for calculating the combination is $ n \ * (n-1) $ by transforming $ {} _n C _2 $.

s = input()

t, a = 0, 1
mod = [0]*2019
mod[0] = 1 #First element(Remainder 0)Is+1
s = s[::-1] #It's easier to scale if you look from behind, so reverse
n = len(s)
for i in range(n):
    t += int(s[i]) * a
    t %= 2019
    a *= 10
    a %= 2019 #Because they are relatively prime%The answer t does not change even if 2019 is calculated
    mod[t] += 1
ans = 0

for i in range(2019):
    ans += mod[i]*(mod[i]-1)//2 #Calculation of combinations
print(ans)

Should I write t, a = 0, 1 on another line? I couldn't find it in PEP8.

Summary

I wanted to solve it in production. I'm happiest this week because I have two ABCs so I'm going to have a cup of tea. see you.