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.



Sample input:
1817181712114


Sample output:
3

Submission status: Accepted

Solution code:

import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

H, W = map(int, input().split())

L, R = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
D = list(map(int,input().split()))

L = list(map(int,input().split()))
R = list(map(int,input().split()))

T = list(map(int,input().split()))

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''


S = input()

N = len(S)

# 右からi桁目までの余り
accum = [int(S[N - 1 - i]) for i in range(N)]

base = 1
for i in range(N-1):

    base*=10
    base %= 2019

    accum[i+1] = (accum[i] + base * accum[i+1]) % 2019






# 余りの整理
count = [0] * 2019

for a in accum:
    count[a] += 1



# ペア数のカウント
ans = 0
for c in count:
    ans += (c*c - c)/2

ans += count[0]

print(int(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict
def solve():
    S = input()
    d = defaultdict(int) 

    cur = 0
    tenFactor = 1
    d[cur] += 1
    for i in range(len(S)):
        cur = (cur + int(S[-i-1]) * tenFactor) % 2019
        tenFactor = tenFactor * 10 % 2019
        d[cur] += 1
    
    ans = 0
    for i in range(2019+1):
        ans += d[i] * (d[i]-1) // 2
    
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
S = str(input())
N = len(S)
ans1 = [0] * 2019
ans2 = 0

T = [0] *  (N + 1)
T[N] = 0
ans1[0] += 1

P = 1
for i in range(N - 1, -1, -1):
  #print(i)
  T[i] = (T[i + 1] + P * int(S[i])) % 2019
  ans1[T[i]] += 1
  P = 10 * P % 2019

for i in range(2019):
  x = ans1[i]
  ans2 += x * (x - 1) / 2
  
#print(ans1[0])
#print(T)
print(int(ans2))

Submission status: Accepted

Solution code:
arr = [0 for i in range(2019)]
arr[0] = 1

s = input()
n = len(s)

num = 0
for i,ele in enumerate(s[::-1]):
    num += int(ele) * pow(10, i, 2019)
    arr[num%2019] += 1


ans = 0
for m in arr:
    if m==0: continue
    ans += m*(m-1)//2

print(ans)

Submission status: Accepted

Solution code:
s = input()
n = len(s)
ans = 0
now = 0
mp = [0 for i in range(2019)]
mp[0] += 1
tmp = [0 for i in range(2019)]

id = [0 for i in range(2019)]
for i in range(2019):
    id[i] = i * 10 % 2019

for c in s:
    now *= 10;
    now += ord(c) - ord("0")
    now %= 2019

    ans += mp[now]
    mp[now] += 1
    for i in range(2019):
        tmp[id[i]] = mp[i]
    for i in range(2019):
        mp[i] = tmp[i]

print(ans)

Submission status: Accepted

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------

S = input()
S = S[::-1]

m = 2019

A=[0]*m
A[0]=1

a = 0
ans=0
for i,s in enumerate(S):
	a = a + (int(s) * pow(10,i,m))
	a %= m
	
	ans += A[a]
	A[a] += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
S = str(input())
N = len(S)

#smod = [int(S[i:])%2019 for i in range(N)]
smod = [0]
tmod = 0
keta = 1
for i in range(N):
    temp = tmod + int(S[(N-1)-i])*keta
    #print(temp)
    tmod = temp%2019
    smod.append(tmod)
    keta = keta*10%2019


cmod = Counter(smod)
#print(cmod)

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

Submission status: Accepted

Solution code:
mod2019=[0]*2019
mod2019[0]=1
t=input()
n=len(t)
s=[]
for i in range(n):
  s.append(int(t[i]))
x=1
y=0
for i in reversed(range(n)):
  y+=s[i]*x
  mod2019[y%2019]+=1
  x=(x*10)%2019
ans=0
for i in range(2019):
  ans+=mod2019[i]*(mod2019[i]-1)
print(ans//2)

Submission status: Accepted

Solution code:
import sys, math
from pprint import pprint
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

S = rs()
#S = '1'*200000

mods = []
n = 0
e = 0
for i in reversed(range(len(S))):
	n += int(S[i]) * pow(10,e,2019)
	#e = (e*10) % 2019
	e += 1
	#n = n % 2019
	mods.append(n % 2019)
mods.append(0)
import collections
cnt = collections.Counter(mods)
ans = 0
for k, c in cnt.items():
	ans += c*(c-1)//2
print(ans)

Submission status: Accepted

Solution code:
S = input()

N = len(S)
table = [-1] * N
T = [-1] * N
prev = 0
for i, s in enumerate(reversed(S)):
    prev += (int(s) * pow(10, i, 2019)) % 2019
    prev %= 2019
    T[i] = prev

DP = [0] * 2019
for t in T:
    DP[t] += 1

ans = DP[0]
for num in DP:
    ans += num * (num - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import defaultdict
    dic = defaultdict(int)

    input = sys.stdin.readline

    s = str(input().rstrip())
    m = 0
    before_m = 0.1

    for i in range(1, len(s) + 1):
        before_m = int(before_m*10)%2019
        m_ad = (int(s[-i]) * before_m) % 2019
        m = (m_ad + m) % 2019
        dic[m] += 1

    ans1 = 0

    for x in dic.values():
        if x > 1:
            ans1 += x * (x - 1) // 2
    ans2 = dic[0]

    print(ans1 + ans2)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter

s = list(input())
ls = len(s)
T = [0] * (ls+1)
modL = [0]
cnt = 0
pad = 1

for i in reversed(range(0, ls)):
    T[i] = T[i+1] + int(s[i]) * pad
    modL.append(T[i] % 2019)
    pad = pad * 10 % 2019

ans = 0
for c in Counter(modL).values():
    ans += c * (c - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
S = input()
N = len(S)
a = []
for s in S:
    a.append(int(s))
MOD = 2019

cur = 0
cten = 0
li = [0 for i in range(MOD)]
for aa in reversed(a):
    if cten==0:
        cten = 1
    else:
        cten = (cten*10)%MOD
    cur = (aa*cten+cur)%MOD
    li[cur] += 1
    # print(cur)

sm = 0
for l in li:
    sm += l*(l-1)//2
sm += li[0]
print(sm)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
S = input()
P =2019
ans = 0

count = [0] * P
count[0] = 1
u = 0
for i, s in enumerate(reversed(S)):
    u = (int(s) * pow(10, i, P) + u) % P
    ans += count[u]
    count[u] += 1
print(ans)

Submission status: Accepted

Solution code:
s = list(input())[::-1]
l = [0]*2019 
l[0] = 1
ten = 1
mod = 2019
now = 0
ans = 0
for i in range(len(s)):
    a = int(s[i])*ten
    now = (now+a)%mod
    ans += l[now]
    l[now] += 1
    ten *= 10
    ten %= 2019
print(ans)

Submission status: Accepted

Solution code:
S = input().strip()
A = [0 for _ in range(len(S))]
A[-1] = int(S[-1])%3
for i in range(2,len(S)+1):
    A[-i] = (A[-i+1]+int(S[-i]))%3
B = [0 for _ in range(len(S))]
B[-1] = int(S[-1])%673
a = 1
for i in range(2,len(S)+1):
    a = (a*10)%673
    B[-i] = (int(S[-i])*a+B[-i+1])%673
C = {}
for i in range(len(S)):
    a = A[i]
    b = B[i]
    if (a,b) not in C:
        C[(a,b)] = 0
    C[(a,b)] += 1
if (0,0) in C:
    C[(0,0)] += 1
cnt = 0
for c in C:
    n = C[c]
    cnt += (n*(n-1))//2
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
S = input()
list_amari = [0 for i in range(2019)]
amari_prev = 0
X = 1

for i in range(len(S)):
  amari = (int(S[-i-1])*X+amari_prev)%2019
  list_amari[amari] += 1
  amari_prev = amari
  X = (10*X)%2019

count = list_amari[0]
for v in list_amari:
  count += v*(v-1)//2

print(count)

Submission status: Accepted

Solution code:
def main():
    S = list(input())
    N = len(S)

    P = 2019
    num = [0] * P
    num[0] = 1
    now, ans = 0, 0
    _10 = 1
    for s in S[::-1]:
        now = (now + int(s)*_10) % P
        _10 *= 10
        _10 %= P
        ans += num[now]
        num[now] += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
s=list(input())
s=s[::-1]
for i in range(len(s)):
    s[i]=int(s[i])
data=[0]
x=0
for i in range(len(s)):
    x=pow(10,i,2019)*s[i]+x
    x=x%2019
    data.append(x)
from collections import Counter
data=dict(Counter(data))
ans=0
for key in data.values():
    ans+=(key)*(key-1)//2
print(ans)

Submission status: Accepted

Solution code:
def main():
  s=input()[::-1]
  l,mod=len(s),2019
  x=[0]*mod
  x[0]=1
  a,t=0,1
  for i in range(l):
    a = (a + int(s[i])*t) % 2019
    x[a]+=1
    t=(t*10)%mod
  ans=sum([i*(i-1)//2 for i in x])
  print(ans)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys, math
from pprint import pprint
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

S = rs()

mods = []
n = 0
e = 1
for i in reversed(range(len(S))):
	n += int(S[i]) * e
	e = (e*10) % 2019
	n = n % 2019
	mods.append(n)
mods.append(0)
import collections
cnt = collections.Counter(mods)
ans = 0
for k, c in cnt.items():
	ans += c*(c-1)//2
print(ans)

Submission status: Accepted

Solution code:
s = input()
n = len(s)
table = [0 for _ in range(n + 1)]
for i in range(n):
    table[-2 - i] = (int(s[-1 - i]) * pow(10, i, 2019) + table[-1 - i]) % 2019
count = [0 for _ in range(2019)]
ans = 0
for t in table:
    if count[t] != 0:
        ans += count[t]
    count[t] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections
from math import ceil

ma = lambda : map(int,input().split())
ni = lambda : int(input())
s = input()
n = len(s)
l = [0]*(n+1)
d = 1
mod = 2019
for i in range(1,n+1):
    l[i] = (l[i-1] + int(s[-i])*d)%mod
    d = d*10%mod

co = collections.Counter(l)
ans = 0
for cnt in co.values():
    ans+=cnt*(cnt-1)//2
print(ans)

Submission status: Accepted

Solution code:
a,*d=[0]*2020
for i in map(int,input()):
  p=[0]*2019
  for j in range(2019):p[(j*10+i)%2019]+=d[j]
  d=p
  d[i]+=1
  a+=d[0]
print(a)

Submission status: Accepted

Solution code:
def main():
    s = input()[::-1]
    sum_digits = 0
    cnts = [0] * 2019
    cnts[0] = 1
    d = 1
    for c in s:
        sum_digits += int(c) * d
        sum_digits %= 2019
        # print(sum_digits)
        d *= 10
        d %= 2019
        cnts[sum_digits] += 1
    ans = 0
    for i, cnt in enumerate(cnts):
        # if cnt > 0: print(i, cnt)
        ans += cnt * (cnt - 1) // 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input()
if(len(s) < 5):
    print(0)
else:
    t = [0]*2019
    t[0] = 1
    p = 0
    temp = 0
    temp2 = 1
    for i in range(1,len(s)+1):
        temp2 *= 10
        temp2 %= 2019
        t[(temp + temp2*int(s[-i]))%2019] += 1
        temp += temp2*int(s[-i])
    for i in range(2019):
        p += (t[i]*(t[i]-1))//2
    print(p)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod = 2019
def main():
    s = input().rstrip()
    n = len(s)
    d = {}
    d[0] = 1
    ten = 1
    T = 0
    for x in reversed(s):
        T += ten*int(x)
        ten *= 10
        T %= mod
        ten %= mod
        if T in d:
            d[T] += 1
        else:
            d[T] = 1

    print(sum(i*(i-1)//2 for i in d.values()))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
S = list(input())
N = len(S)


l = [0] * 2019
l[0] = 1
m = 1
temp = 0
for i in range(N-1, -1, -1):
    temp += int(S[i]) * m
    temp %= 2019
    l[temp] += 1
    m *= 10
    m %= 2019

ans = 0

for i in range(0, 2019):
    ans += l[i] * (l[i]-1) // 2

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

s = input()
n = len(s)
mod = 2019
DP = [0 for i in range(n+2)]
DP[n+1] = 0

num = 1
for i in reversed(range(n)):
    DP[i] = (DP[i+1] + int(s[i])*(num))%mod
    num = num*10%mod
DP.pop(-1)

arr = defaultdict(int)
for dp in DP:
    arr[dp]+=1

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

Submission status: Accepted

Solution code:
s = input()

MOD = 2019
#0を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))

Submission status: Accepted

Solution code:
S = input()[::-1]
ans = 0
dp = [0] * 2019
dp[0] = 1
val = ''
m = 0
x_10 = 1
for s in S:
    m = (m + int(s) * x_10) % 2019
    dp[m] += 1
    x_10 = (x_10 * 10) % 2019
for i in dp:
    ans += i * (i-1) // 2
print(ans)

Submission status: Accepted

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

MOD = 2019
T = [1] + [0] * 2018
d, p = 0, 1
for c in reversed(s):
	d = (d + p * int(c)) % MOD
	p = p * 10 % 2019
	T[d] += 1

print(sum(x * (x - 1) // 2 for x in T))

Submission status: Accepted

Solution code:
s = input()[::-1]
 
sum_of_digits = 0
 
cnts = [0] * 2019
 
cnts[0] = 1
 
d = 1
 
for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    cnts[sum_of_digits] += 1
 
ans = 0

for cnt in cnts:
    ans += cnt * (cnt - 1) // 2
 
print(ans)

Submission status: Accepted

Solution code:
s = input()
n = len(s)
m = 2019
a = 0
r = [0 for _ in range(m+1)]
r[0] = 1
z = 0
for i in range(0,n):
    z = (int(s[n-i-1])*pow(10,i,m) + z)%m
    a += r[z]
    r[z] += 1
print(a)

Submission status: Accepted

Solution code:
s = str(input())
s=s[::-1]
mod = 2019
li = [0]*(len(s)+1)
cnt=1
for i in range(len(s)):
    li[i+1]=li[i] + int(s[i]) * cnt
    li[i+1]%=mod
    cnt*=10
    cnt%=mod
import collections
A=collections.Counter(li[1:]);ans=0
for u,v in A.items():
    ans+=v*(v-1)//2
    if u==0:
        ans+=v
print(ans)

Submission status: Accepted

Solution code:
S = input()
count = 0
l = [0] * 2019 #mod2019 は0~2018まで
l[0] = 1
mod = 2019
tmp = 0

for i in range(1, len(S) + 1):
    tmp = (tmp + int(S[len(S) - i]) * pow(10, i - 1, mod)) % mod
    #print(tmp)
    l[tmp] += 1

#print(l)
for j in range(2019):
    if l[j] >= 2:
        count += l[j] * (l[j] - 1) // 2

print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict

S = input()

D = defaultdict(int)
D[0] += 1
x = 0
d = 1
for s in reversed(S):
  x = (x + int(s) * d) % 2019
  D[x] += 1
  d = (d * 10) % 2019

print(sum(x * (x-1) // 2 for x in D.values()))

Submission status: Accepted

Solution code:
def d_multiple_of_2019():
    from collections import Counter
    S = [int(ch) for ch in input()]

    p = 2019  # ABC158-E のソースコードを流用するため
    s = S[::-1]
    u = [0] * len(S)
    u[0] = s[0] % p

    power = 1
    for i in range(1, len(S)):
        power *= 10
        power %= p
        u[i] = u[i - 1] + power * s[i]
        u[i] %= p
    count = Counter(u)
    return sum(v * (v - 1) // 2 for v in count.values()) + count[0]

print(d_multiple_of_2019())

Submission status: Accepted

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

res = 0
cnt = [0] * 2019
for i in range(n):
    res = (res + int(s[n-1-i]) * pow(10, i, 2019)) % 2019
    cnt[res] += 1

ans = 0
for c in cnt:
    ans += c * (c-1) // 2
ans += cnt[0]

print(ans)

Submission status: Accepted

Solution code:
s = str(input())
ans = [0]*2020
a = 0
po = 0
aaa = 0
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

for i in range(len(s)):
    a += int(s[len(s)-i-1]) * power_func(10,po,2019)
    a = a % 2019
    ans[a] += 1
    po += 1
    if a == 0:
        aaa += 1
for i in range(2020):
    aaa += ans[i] * (ans[i]-1)//2
print(aaa)

Submission status: Accepted

Solution code:
from collections import defaultdict
S = input()
n = len(S)
N = defaultdict(int)
x = 0
for i in reversed(range(n)):
    x += int(S[i])*pow(10,(n-i-1),2019)
    x %= 2019
    N[x] += 1
ans = N[0]
for j in N.values():
    ans += j*(j-1)//2
print(ans)

Submission status: Accepted

Solution code:
s=input()
t=len(s)
ans=0
ruiseki=[int(s[-1]) for i in range(t)]
for i in range(1,t):
    ruiseki[i]=(ruiseki[i-1]+int(s[-1-i])*pow(10,i,2019))%2019
from collections import Counter
ans+=ruiseki.count(0)
C=Counter(ruiseki)
for x in C.values():
    ans+=x*(x-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

s = input()
n = len(s)
mod = 2019
DP = [0 for i in range(n+2)]
DP[n+1] = 0

for i in reversed(range(n)):
    DP[i] = (DP[i+1] + int(s[i])*(pow(10,n-i-1,mod)))%mod
DP.pop(-1)

arr = defaultdict(int)
for dp in DP:
    arr[dp]+=1

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

Submission status: Accepted

Solution code:
from collections import defaultdict

S = tuple(map(int, list(input())))
MOD = 2019

d = defaultdict(int)
d[0] = 1

tmp = 0
for i, s in enumerate(reversed(S)):
    tmp = (tmp + s * pow(10, i, MOD)) % MOD
    d[tmp] += 1
print(sum(v * (v - 1) // 2 for v in d.values()))

Submission status: Accepted

Solution code:
from sys import stdin
s = stdin.readline().rstrip()
n = len(s)
dic = {}
dic[0] = 1
now = 0
mul = 1
for i in range(n-1,-1,-1):
    now = (now+(10*mul)*int(s[i]))%2019
    if now in dic:
        dic[now] += 1
    else:
        dic[now] = 1
    mul *= 10
    mul %= 2019
print(sum(dic[i]*(dic[i]-1)//2 for i in dic))

Submission status: Accepted

Solution code:
s = input()
ans = 0
tmp = 0
mods = [0]*2019
mods[0] = 1
order = 1
for i in reversed(s):
    tmp += int(i) * order
    mods[tmp % 2019] += 1
    order *= 10
    order %= 2019
ans = sum(n*(n-1)//2 for n in mods)
print(int(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict
S = input()
N = len(S)

D=defaultdict(int)
D[0]=1
ans=0
prev=0

for i,s in enumerate(reversed(S)):
    cur=(prev+pow(10,i,2019)*int(s))%2019
    ans+=D[cur]
    D[cur]+=1
    prev=cur
print(ans)

Submission status: Accepted

Solution code:
s = input()
n = len(s)
p = 2019
ans = 0

num_rem = [0] * p
t = 1
mod = 0
num_rem[mod] = 1
for i in range(n):
    mod = (mod + int(s[-i-1])*t)%p
    num_rem[mod] += 1
    t = (10*t)%p
for m in num_rem:
    ans += (m*(m-1))//2
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple


def solve(s: str) -> int:
    modulo = 2019
    remainders = defaultdict(int, {0: 1})
    power = 1
    curr = 0
    LOG.debug((s))
    result = 0
    for i in range(len(s) - 1, -1, -1):
        c = int(s[i])
        curr = (power * int(c) + curr) % modulo
        power = (power * 10) % modulo
        result += remainders[curr]
        remainders[curr] += 1
    LOG.debug((remainders))
    return result


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    S = input()
    # values = list(map(int, input().split()))
    # values = []
    # for _ in range(N):
    #     values.append(input().split())
    result = solve(S)
    print(result)


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result))


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Accepted

Solution code:
s = input()

lst = [0 for i in range(2019)]
lst[0] = 1

amari = 0
tmp = 1
for i in range(1, len(s)+1):
    amari = (amari + int(s[-i])*tmp) % 2019
    lst[amari] += 1
    tmp = (tmp*10) % 2019

ans = 0
for i in range(2019):
    num = lst[i]
    ans += num * (num-1) // 2

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(S: str):
    s = [0] * 2019
    s[0] = 1
    ret = 0
    for c in S:
        cc = int(c)
        n = [0] * 2019
        for k, v in enumerate(s):
            kk = (k * 10 + cc) % 2019
            n[kk] += v
            if kk == 0:
                ret += v
        s = n
        n[0] += 1
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = str(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    s = S()
    d = defaultdict(int)
    tmp = 0
    ans = 0
    d[0] = 1
    for i, si in enumerate(s[::-1]):
        tmp += int(si) * pow(10, i, 2019)
        tmp %= 2019
        ans += d[tmp]
        d[tmp] += 1
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import collections
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


s=list(input())
s=s+[0]
mod=0
ans=[]
count=0
n=len(s)
p=2019

for i in range(n):
    mod+=(pow(10,i,p)*int(s[n-i-1]))%p
    mod%=p
    ans.append(mod)

ans = collections.Counter(ans)
ans=ans.most_common()
for i in range(len(ans)):
    if ans[i][1]>=2:
        count+=combinations_count(ans[i][1],2)

print(count)

Submission status: Accepted

Solution code:
s=list(input())
s=[int(i) for i in s]
now=0
c=[0]*2019
c[0]=1
for n,i in enumerate(s[::-1]):
    now+=i*pow(10,n,2019)
    c[now%2019]+=1
ans=0
for k in range(2019):
    ans+=c[k]*(c[k]-1)//2
print(ans)

Submission status: Accepted

Solution code:
s=list(map(int,list(input())))[::-1]
n=len(s)
chk=[0]*2019
chk[0]=1
t,m,ans=1,0,0
for i in s:
    m=(m+t*i)%2019
    ans+=chk[m]
    chk[m]+=1
    t=t*10%2019
print(ans)

Submission status: Accepted

Solution code:
M = 2019
dp = [0] * M
s = input()
x = 0
for c in s:
    c = int(c)
    dp2 = [0] * M
    for j in range(M):
        index = (j*10 + c) % M
        dp2[index] += dp[j]
    dp = dp2
    dp[c] += 1
    x += dp[0]
print(x)

Submission status: Accepted

Solution code:
s=input()
a,b=0,[0]*2019
b[0]+=1
for i in range(len(s)-1,-1,-1):
    a=(a+int(s[i])*pow(10,len(s)-i-1,2019))%2019
    b[a]+=1
c=0
for i in b:
    c+=i*(i-1)
print(c//2)

Submission status: Accepted

Solution code:
from sys import stdin

S = stdin.readline().rstrip()
N = len(S)
Sp = S

res_map = [0 for _ in range(N)]

aa_list2 = [1]
for i in range(1,N):
    aa_list2.append((aa_list2[i-1]*10)%2019)

res_map[N-1] = int(S[N-1])
index=1


for i in range(N-2,-1,-1):
    res_map[i] = (int(S[i])*aa_list2[index] + res_map[i+1])%2019
    index+=1

aa_table = [0 for i in range(2019)]
for i in range(len(res_map)):
    aa_table[res_map[i]]+=1

aa_table[0]+=1

tot = 0
for i in range(2019):
    tot+=int((aa_table[i]-1)*aa_table[i]/2)

print(tot)

Submission status: Accepted

Solution code:
def main(S=None):
    if not S:
        S = input()
    r = [0]*2019
    r[0] = 1
    tmp = 0
    base = 1
    for s in S[::-1]:
        s = int(s) * base
        base *= 10
        base %= 2019
        tmp += s
        tmp %= 2019
        r[tmp] += 1
    count = 0
    for v in r:
        count += v*(v-1)//2
    print(count)
    return count


if __name__ == "__main__":
    # assert main("1817181712114") == 3
    # assert main("14282668646") == 2
    # assert main("2119") == 0
    main()

Submission status: Accepted

Solution code:
s=input()
ans=0
u=0
l=[0]*2019
l[0]=1
for i,n in enumerate(map(int,s)):
  u=(u+n*pow(10,len(s)-i,2019))%2019
  l[u]+=1
for i in l:
  ans+=i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

M = 2019

Ss = input().rstrip()

As = [0]
A = 0
d = 1
for S in reversed(Ss):
    A += int(S) * d
    A %= M
    As.append(A)
    d = (d*10) % M

As.reverse()
#print('As:', As)

cnt = Counter(As)

ans = 0
for A, num in cnt.items():
    ans += num*(num-1)//2

print(ans)

Submission status: Accepted

Solution code:
def main():
    MOD=2019
    S=input()[::-1]
    count=[1]+[0]*MOD
    r,tmp=0,1
    for i in S:
        r += int(i)*tmp
        r %= MOD
        tmp *= 10
        tmp %= MOD
        count[r] += 1

    print(sum([i*(i-1)//2 for i in count]))

main()

Submission status: Accepted

Solution code:
N = 2019
cnt = [0] * N
S = input()
ans = 0
for s in S:
    s = int(s)
    new = [0] * N
    for n in range(N):
        idx = (10 * n + s) % N
        new[idx] += cnt[n]
    cnt = new
    cnt[s] += 1
    ans += cnt[0]
print (ans)

Submission status: Accepted

Solution code:
s = input()
n = len(s)
p = 0
ten = 1
cnt = [0] * 2019
cnt[0] = 1
ans = 0
for i in reversed(s):
    p = (p + int(i) * ten) % 2019
    ans += cnt[p]
    cnt[p] += 1
    ten = ten * 10 % 2019

print(ans)

Submission status: Accepted

Solution code:
S = input()
if len(S) < 4:
    print(0)
    exit(0)
dp = [0]*2019
dp[0] = 1
s = int(S[-1])
dp[s] = 1
ans = 0
for k in range(len(S)-2,-1,-1):
    s = int(S[k])*(pow(10,len(S)-k-1,2019)) + s
    s %= 2019
    dp[s] += 1
for e in dp:
    ans += e*(e-1)//2
print(ans)

Submission status: Accepted

Solution code:
a = [int(c) * pow(10, i, 2019) % 2019 for i, c in enumerate(reversed(input()))]
s = [0]
for x in a:
  s += [(s[-1] + x) % 2019]
cnt, ans = [0] * 2019, 0
for x in s:
  ans += cnt[x]
  cnt[x] += 1
print(ans)

Submission status: Accepted

Solution code:
S = input()
MOD =2019
count = [0]*MOD
r = 0
t = 1
for i in reversed(S):
    r += int(i) * t
    r %= MOD
    t *= 10
    t %= MOD
    count[r] += 1

count[0] += 1
print(int(sum(i*(i-1)/2 for i in count)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
s = input()[::-1]
n = len(s)
cs = [0] * (n + 1)
ten = 1
for i in range(n):
    cs[i + 1] = int(s[i]) * ten % 2019
    ten = ten * 10 % 2019
for i in range(n):
    cs[i + 1] = (cs[i + 1] + cs[i]) % 2019
cnt = [0] * 2019
for i, x in enumerate(cs):
    cnt[x] += 1
ans = sum(x * (x - 1) // 2 for x in cnt)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import Counter

S = list(input())
S = list(map(int, S))
mod = 2019
s = [S.pop()]
d = 1
for i in S[::-1]:
    d = (d * 10) % mod
    s.append((i * d) % mod)

acc = list(accumulate(s)) + [0]
acc = [i % mod for i in acc]
answer = sum(i * (i - 1) // 2 for i in Counter(acc).values())
print(answer)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
import collections
s=input()
n=len(s)
a=[]
x=0
p=1
for i in range(n):
	j = n-1-i
	c = int(s[j])
	p %= 2019
	x += (p*c)%2019
	p *= 10
	x %= 2019
	a.append(x)
c=collections.Counter(a)
ans = 0
for k,v in c.items():
	if k==0:
		ans += v
	ans += v*(v-1)//2
print(ans)