When the following problems were asked in AtCoder, I couldn't help at all, so I will summarize the theory and its implementation.
Multiple of 2019 ( AtCoder Beginner Contest 164; Problem D )
Problem statement You will be given the string S, which consists only of numbers from 1 to 9. A set of integers that satisfy the following conditions(i,j) (1≤i≤j≤|S|)Find the total number of.
Condition: If you look at the i-th to j-th letters of S as decimal integers, this integer is a multiple of 2019.
Constraint 1≤|S|≤200000 S is a string consisting only of numbers from 1 to 9
It is possible to calculate by stacking for loops in a straightforward manner, but in the case of AtCoder, it is necessary to devise because it exceeds the upper limit of the calculation time.
This kind of problem of calculating multiples (or the problem of thinking about radix?) Can be used to write efficient programs by algorithms that make good use of mod calculations.
a \equiv b \pmod{ 2019 } \\
c \equiv d \pmod{ 2019 }
When
a + c \equiv b + d \pmod{ 2019 } \\
a - c \equiv b - d \pmod{ 2019 } \\
a * c \equiv b * d \pmod{ 2019 }
Is established. In other words, the sum, difference, and product formulas in ordinary four arithmetic operations can be applied to mod calculations.
By the way, the following rules also hold for quotients.
If $ ab \ equiv ac $ and $ a $ and $ p $ are relatively prime, then $ b \ equiv c $
The given string $ S $ is
S = s_n s_{n-1} \dots s_2 s_1
Suppose that In other words, contrary to the problem, consider setting $ i <j $. What is the set $ (i, j) $ that meets the conditions in the problem?
N_{ij} = 10^{i-j} s_i + 10^{i-j-1} s_{i+1} + \dots + 10 s_{j+1} + s_j
Is a multiple of 2019. It is required to count the set $ (i, j) $ of this condition. First, define the following $ r_i $ and $ t_i $.
t_i = 10^{i-1} \\
r_i = t_i s_i + t_{i-1} s_{i-1} + \dots + t_1 s_1
This $ r_i $ can also be written as follows.
r_i = t_i s_i + r_{i-1}
At this time, the following equation holds.
r_{i} \equiv r_{j-1} \Rightarrow N_{ij} \equiv 0 \pmod{ 2019 }
This proof is shown below. The following relationship holds between $ r_i $ and $ N_ {ij} $.
r_{i} - r_{j-1} = N_{ij} * 10^{j-1}
If $ r_ {i} \ equiv r_ {j-1} $
r_{i} - r_{j-1} = N_{ij} * 10^{j-1} \equiv 0 \pmod{ 2019 }
Because it becomes
N_{ij} \equiv 0 \pmod{ 2019 }
Or
10^{j-1} \equiv 0 \pmod{ 2019 }
Should hold. But since $ 10 ^ {j-1} = 2 ^ {j-1} * 5 ^ {j-1} $, $ 2019 $ and $ 10 ^ {j-1} $ are clearly disjoint, the former $ N_ {ij} \ equiv 0 $ will hold.
r_i \equiv R_i \pmod{ 2019 } \\
s_i \equiv S_i \pmod{ 2019 } \\
t_i \equiv T_i \pmod{ 2019 }
However, $ R_i, S_i, T_i $ represent the remainder, which is $ 0 \ le R_i, S_i, T_i \ le 2018 $. Using these characters, the remainder of each $ r_i $ can be calculated continuously as follows.
\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}
You can use this method to calculate the remainder for each $ r_i $ for 2019, and count the combinations of $ r_i $ with the same remainder to calculate the answer.
By using the above algorithm, it is possible to calculate without overlapping for loops.
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