ABC164 D.Multiple of 2019

D.Multiple of 2019 Question 给一个字符串S,求有多少个子串在十进制下为2019的倍数。 Solution 前置知识: S[l][r]×10l−r=s[l][k]−s[r][k]S[l][r]\times10^{l-r}=s[l][k]-s[r][k]S[l][r]×10l−r=s[l][k]−s[r][k] 若S[l][k]−S[r][k]≡0(mod P)S[l][k]-S[r][k] \equiv 0(mod\ P)S[l][k]−S[r][k]≡0(mod P) ∵10xmod P≠0∵10^{x} mod\ P \neq 0∵10xmod P​=0 ∴S