Problem:
 Score : 400 points    Problem Statement Given is a string S consisting of digits from 1 through 9 .  Find the number of pairs of integers (i,j) ( 1 ≤ i ≤ j ≤ |S| ) that satisfy the following condition:  Condition: In base ten, the i -th through j -th characters of S form an integer that is a multiple of 2019 .      Constraints  1 ≤ |S| ≤ 200000  S is a string consisting of digits from 1 through 9 .         Input Input is given from Standard Input in the following format:  S       Output Print the number of pairs of integers (i,j) ( 1 ≤ i ≤ j ≤ |S| ) that satisfy the condition.        Sample Input 1 1817181712114      Sample Output 1 3  Three pairs - (1,5) , (5,9) , and (9,13) - satisfy the condition.       Sample Input 2 14282668646      Sample Output 2 2       Sample Input 3 2119      Sample Output 3 0  No pairs satisfy the condition.

Solution (Python):
def main():
    S = list( map( int, list( input())))
    N =len(S)
    A = [0]*2019
    P = 2019
    num = [0] * P
    num[0] = 1
    now, ans = 0, 0
    _10 = 1
    for i in range(N-1, -1, -1):
        now = (now + int(S[i]) * _10) % P
        _10 *= 10
        _10 %= P
        ans += num[now]
        num[now] += 1
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
def resolve():
    S = input()
    table=[0]*2019
    table[0]=1
    x = 0
    x_10 =1
    for i in S[::-1]:

        x = (x+ int(i)*x_10)%2019

        table[x]+=1

        x_10*=10
        x_10 %= 2019

    ans =0
    for i in table:
        ans += i*(i-1)//2
    
    print(ans)



if __name__ == "__main__":
    resolve()

Solution (Python):
from collections import Counter

S = input()
P = 2019

def solve(S, P):
    S = S[::-1]
    T = [0] * len(S)
    T[0] = int(S[0]) % P
    power = 1
    for i in range(1, len(S)):
        power *= 10
        power %= P
        T[i] = T[i - 1] + power * int(S[i])
        T[i] %= P
    counter = Counter(T)
    return sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]


print(solve(S, P))

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict

S = input()[:-1]
cnt = defaultdict(int)
cnt[0] = 1
ans = 0
now = 0

for i in range(len(S)-1, -1, -1):
    now = (now+int(S[i])*pow(10, len(S)-1-i, 2019))%2019
    ans += cnt[now]
    cnt[now] += 1

print(ans)

Solution (Python):
S = input()



p=2019
h=0
d=1
total = 0
counts = [0]*p
counts[0]=1
for s in reversed(S):
  m = (int(s)*d) % p
  h = (h+m) % p
  total += counts[h]
  counts[h] += 1
  d = (d*10) % p
print(total)

Solution (Python):
S = input()
N = len(S)

dp = [0] * (N+1)
base = 2019
for i, s in enumerate(S, 1):
    dp[i] = (dp[i-1]*10 + int(s)) % 2019

digit = 1
for i in range(N):
    j = N - i
    dp[j] *= digit
    dp[j] %= base
    digit *= 10
    digit %= base

ans = 0
d = {}
for r in dp:
    if r in d:
        ans += d[r]
        d[r] += 1
    else:
        d[r] = 1

print(ans)

Solution (Python):
S=input()
DP=[0]*len(S)

now=0
for i in range(len(S)-1,-1,-1):
    now=(now+pow(10,len(S)-1-i,2019)*int(S[i]))%2019
    DP[i]=now
    
DP.append(0)

from collections import Counter
C=Counter(DP)

ANS=0
for c in C.values():
    ANS+=c*(c-1)//2

print(ANS)

Solution (Python):
s = input()
mod = 2019
remains = [0]*mod

ans = 0
now = 0
remains[0] = 1
for i,val in enumerate(s[::-1]):
    now += int(val) * pow(10,i,mod )
    now %= mod
    ans += remains[now]
    remains[now] += 1

print(ans)

Solution (Python):
s = input()
x = list(map(int, list(s)))
x = x[::-1]
dic = [0 for _ in range(2020)]
ten = 1
y = 0
for i in range(len(s)):
    y = (y+ten*x[i])%2019
    dic[y] += 1
    ten = (ten*10)%2019
result = 0
for i in range(2019):
    result += max([dic[i]*(dic[i]-1)//2, 0])
result += dic[0]
print(result)

Solution (Python):
s=list(input())
mod=2019
A=[0]*2019
a=0
b=1
for i in range(len(s)):
  a=(a+int(s[-1-i])*b)%mod
  A[a]+=1
  b=b*10%mod
ans=A[0]*(A[0]+1)//2
for i in range(1,2019):
  if A[i]!=0:
    ans=ans+(A[i]-1)*A[i]//2
print(ans)

Solution (Python):
from collections import Counter
S = [int(c) for c in input()]
N = len(S)
ls = [0]*N
m = 1
for i in range(N):
  ls[N-1-i] = S[N-1-i]*m%2019
  m *= 10
  m %= 2019
T = [0]*N
T[0] = ls[0]
for i in range(1,N):
  T[i] = (T[i-1]+ls[i])%2019
c = Counter(T)
ans = c[0]+sum(v*(v-1)//2 for v in c.values())
print(ans)

Solution (Python):
import sys
range = xrange
input = raw_input

mod = 2019

S = input()
X = [0]
power = 1
for c in reversed(S):
    X.append((int(c) * power + X[-1]) % mod)
    power = power * 10 % mod

counter = [0]*mod
for x in X:
    counter[x] += 1

ans = 0
for c in counter:
    ans += c * (c - 1) // 2
print ans

Solution (Python):
s = input()
a = [0]
l = len(s)
for i in s:
    i = int(i)
    a.append((a[-1] + i * pow(10, l, 2019)) % 2019)
    l -= 1

b = [0] * 2019
for i in a:
    b[i] += 1
ans = 0
for i in b:
    ans += i * (i - 1) // 2
print(ans)

Solution (Python):
from collections import Counter
MOD = 2019
s = input()[::-1]
n = len(s)
l = [0] * (n + 1)
t = 1
for i in range(n):
    l[i + 1] = ((ord(s[i]) - ord('0')) * t + l[i]) % MOD
    t = t * 10 % MOD
c = Counter(l)
ans = 0
for v in c.values():
    ans += (v - 1) * v // 2
print(ans)

Solution (Python):
from collections import defaultdict as dict

s = input()
a = []
for c in s:
    a.append(int(c))

cnt = dict(int)
d = 1
a.reverse()
y = 0
cnt[y] += 1
ans = 0
for x in a:
    y += d*x
    y %= 2019
    ans += cnt[y]
    cnt[y] += 1
    d *= 10
    d %= 2019

print(ans)

Solution (Python):
S = input()

S = S[::-1]

T = [0]
t = 0
a = 1
for i in range(len(S)):
    t += int(S[i])*a
    t %= 2019
    a *= 10
    a %= 2019
    T.append(t)
from collections import Counter
c = Counter(T)
num = 0
for key in c:
    num +=(c[key]*(c[key]-1))//2

print(num)

Solution (Python):
s=input()[::-1]
n=len(s)
b=[0]
m=0
d=1
for i in range(n):
  m+=int(s[i])*d
  m%=2019
  d*=10
  d%=2019
  b.append(m)
from collections import Counter
c=Counter(b)
ans=0
for i in range(2020):ans+=c[i]*(c[i]-1)//2
print(ans)

Solution (Python):
n=input()
p=2019
t=1
y=0
c=[0]*p
for x in map(int,n[::-1]):
  y+=t*x
  y%=p
  c[y]+=1
  t*=10
  t%=p
print(sum(i*(i-1)//2 for i in c)+c[0])

Solution (Python):

S = input()
N = len(S)

P = 2019

if P not in [2,5]:

    dic = {}
    dic[0] = 1
    now = 0
    ans = 0

    loop = 0
    for i in range(N-1,-1,-1):
        now += int(S[i]) * pow(10,loop,P)
        now %= P
        if now in dic:
            ans += dic[now]
            dic[now] += 1
        else:
            dic[now] = 1
        loop += 1

    print (ans)

elif P == 2:

    ans = 0
    for i in range(N):

        if int(S[i]) % 2 == 0:
            ans += i+1

    print (ans)

else:

    ans = 0

    for i in range(N):

        if int(S[i]) % 5 == 0:
            ans += i+1

    print (ans)

Solution (Python):

s = input()
n = len(s)

A = [1]
mod = 2019
for i in range(n-1):
    A.append((A[-1]*10)%mod)

B = [int(s[-1])]
for i in range(1, n):
    B.append((B[-1] + A[i] * int(s[n-i-1])) % mod)



ans = 0
C = [0] * 2019
C[0] += 1
for i in range(n):
    C[B[i]] += 1

for i in range(len(C)):
    ans += (C[i]-1)*C[i]//2

print(ans)

Solution (Python):
p=2019
s=input()
l=len(s)
amari=[0]*l
count=[0]*p

ruijo=1

for i in range(l):
    suji=int(s[l-i-1])
    amari[i]=(suji*ruijo)%p
    ruijo*=10
    ruijo%=p

gen=0
count[0]+=1
for i in range(l):
    gen+=amari[i]
    gen%=p
    count[gen]+=1
    

ans=0

for c in count:
    if(c>1):
        ans+=c*(c-1)//2

print(ans)

Solution (Python):
import sys
from collections import Counter

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

s = list(map(int, list(ns())))
n = len(s)
l = [0]*(n+1)
t = 1
for i in range(n-1, -1, -1):
    l[i] = (l[i+1] + s[i]*t) % 2019
    t = t * 10 % 2019
d = Counter(l)
print(sum(y*(y-1)//2 for y in d.values()))

Solution (Python):
from collections import Counter
s=input()[::-1]
l=[0]*(len(s)+1)
kake=1
for i in range(1,len(s)+1):
    l[i]=l[i-1]+kake*int(s[i-1])
    l[i]%=2019
    kake*=10
    kake%=2019
S=Counter(l);ans=0
for i in S.values():
  ans+=(i*(i-1))//2
print(ans)

Solution (Python):
S = [int(a) for a in input()[::-1]]
m = 2019
N = len(S)
s = 0
p = 1
X = [0] * 2019
X[0] = 1
ans = 0
for a in S:
    s = (s + a * p) % m
    ans += X[s]
    X[s] += 1
    p = p * 10 % m

print(ans)

Solution (Python):
s = input()
n, p = len(s), 2019

ans = 0

d = {i:0 for i in range(p)}
d[0] = 1

ap = 1
if p not in [2, 5]:
    pre = 0
    for si in s[::-1]:
        si = int(si)
        a = (si * ap + pre) % p
        ans += d[a]
        d[a] += 1
        pre = a
        ap = (ap * 10) % p
else:
    for i, si in enumerate(s):
        if int(si) % p == 0:
            ans += i+1
print(ans)

Solution (Python):
s = input()
n = len(s)

m = 2019
cnt = [0]*(m+1)

ans = 0
p = 1
cur = 0
for i in reversed(range(n)):
    cur += p*int(s[i])
    cur %= m
    p *= 10
    p %= m

    if cur == 0:
        ans += 1
    ans += cnt[cur]
    cnt[cur] += 1

print(ans)

Solution (Python):
def input_int():
    return int(input())

def input_ints():
    return list(map(int, input().split()))

S = input()
N = len(S)
cnt = [0] * 2019
cnt[0] += 1
ans = 0

p = 1
now = 0

for i in reversed(range(N)):
    now = (now + int(S[i]) * p) % 2019
    p = p * 10 % 2019
    ans += cnt[now]
    cnt[now] += 1

print(ans)

Solution (Python):

S = list(map(int, list(input())))

mod = 2019
ss = [0]
tmp = 0
for i, s in enumerate(S[::-1]):
    tmp += s * pow(10, i, mod)
    tmp %= mod
    ss.append(tmp)

cnts = [0] * 2019
ans = 0
for s in ss:
    ans += cnts[s]
    cnts[s] += 1

print(ans)

Solution (Python):
from collections import defaultdict
s = input()
n = len(s)
a = [0]*n
p=2019
r = defaultdict(int)
a = int(s)
r[a%p]+=1
for i in range(n):
    a = (a%p-int(s[i])%p*pow(10,(n-1-i),p))%p
    r[a]+=1

ans = 0
cnt=1
for i in r.values():
    ans+=i*(i-1)//2
print(ans)

Solution (Python):
from collections import defaultdict

S = list(map(int, input()))
mod = [0] * len(S)
cur = 0
factor = 1
for i, n in list(enumerate(S))[::-1]:
    cur = (cur + n * factor) % 2019
    factor = factor * 10 % 2019
    mod[i] = cur
ans = 0
cnt = defaultdict(int)
for i in range(len(S)):
    ans += cnt[mod[i]]
    cnt[mod[i]] += 1
ans += cnt[0]
print(ans)

Solution (Python):
from collections import defaultdict

s = input()

cnt = defaultdict(int)
cnt[0] += 1
tmp = 0
for i, c in enumerate(s[::-1]):
    c = int(c)
    tmp = (tmp + c * pow(10, i, 2019)) % 2019
    cnt[tmp] += 1


print(sum(c * (c - 1) // 2 for c in cnt.values()))

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 2019

def solve():
    a = list(map(int, input()))
    n = len(a)
    for i in range(n):
        a[i] *= pow(10,n-i-1,mod)
        a[i] %= mod
    s = [0]+list(accumulate(a))
    d = [0]*mod
    ans = 0
    for i in s:
        j = i%mod
        ans += d[j]
        d[j] += 1
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
S=input()[::-1]
N=len(S)
X=[0 for i in range(N+1)]
tmp=1
for i in range(N):
    X[i+1]=X[i]+(tmp*int(S[i]))
    X[i+1]%=2019
    tmp=tmp*10
    tmp%=2019
D=dict()
for i in range(N+1):
    if X[i] in D:
        D[X[i]]+=1
    else:
        D[X[i]]=1
ans=0
for k in D:
    i=D[k]
    ans+=(i*(i-1))//2
print(ans)

Solution (Python):
from collections import Counter
S = input()[::-1]

memo = [0]
d = 0
mod = 2019

for s in S:
    tmp = int(s) * pow(10, d, mod) % mod
    tmp = memo[-1] + tmp
    memo.append(tmp % mod)
    d += 1

c = Counter(memo)
ans = sum(v * (v - 1) // 2 for v in c.values())
print(ans)

Solution (Python):
import sys;input=sys.stdin.readline

P = 2019
S=input().strip()
N = len(S)
if P in {2, 5}:
    r=0
    for i in range(N):
        if not int(S[i])%P:
            r+=i+1
    print(r)
else:
    S = S[::-1]
    r=0
    from collections import defaultdict
    d=defaultdict(int)
    d[0] += 1
    R=0
    X=1
    for i in range(N):
        r += int(S[i])*X
        R += d[r%P]
        X = (X*10)%P
        d[r%P]+=1
    print(R)

Solution (Python):


import sys
readline = sys.stdin.readline
read = sys.stdin.read


s = input()

MOD = 2019
d = [0]*MOD
d[0] = 1
r = 0
t = 1
for i in reversed(s):
    r += int(i)*t
    r %= MOD
    t *= 10
    t %= MOD
    d[r] += 1
    
print(sum(i*(i-1)//2 for i in d))