can someone explain matthew chen solution
see link below
https://usaco.guide/problems/ac-MultipleOf2019/user-solutions
questions about matthew chen comments
- i don’t understand what this number means
d_k + 10d_{k+1} + 100d_{k+2} + … + 10^(n-k)d_n - why do we multiple by 10^(k-1)?
- and how does multiplying number above by 10^(k-1) turns into this?
S_n - S_{k-1} = 0 (mod 2019) <=> S_n = S_{k-1} (mod 2019) - also, what does S_{k-1} mean?
- how is this true? 10^(-1) = 202 (mod 2019)
isn’t this 0.1 = 202 (mod 2019)? not sure how they got 202 - why do we do this " multiply subsequent terms by a factor of 202 to form an equivalent sequence for S_n in the field F_{2019}."
- can someone give a better summary than mines?
-
- take mod of substring
-
- multiply remainder from 1. by factor than take mod again
- Q: why do multiply by factor, isn’t that redundant?
- why not just use the remainder directly as a hash key?
- 3.use remainder from 2. as a key for hash residues
-
- calculate answer from hash residues