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:
from collections import Counter

S = input()
MOD = 2019
mods = [0]
r = 0
for i, c in enumerate(S[::-1]):
    r += int(c) * pow(10, i, MOD)
    mods.append(r % MOD)

counter = Counter(mods)
# print("counter: {}".format(counter))

ans = 0
for v in counter.values():
    ans += v * (v-1) // 2

print(ans)

Submission status: Accepted

Solution code:
import collections
S=str(input())

T=[0 for i in range(len(S))]
T[0]=int(S[-1])

for i in range(1,len(S)):
    T[i]=(pow(10,i,2019)*int(S[len(S)-1-i])+T[i-1])%2019
    
cnt=0
T_di=collections.Counter(T)

for key in T_di.keys():
    x=T_di[key]
    cnt+=x*(x-1)/2
    if key==0:
        cnt+=x

print(int(cnt))

Submission status: Accepted

Solution code:
from collections import defaultdict
S = list(input())[::-1]
n = len(S)
d = defaultdict(int)
d[0] += 1
res = 0
for i, s in enumerate(S):
    res += int(s)*pow(10, i, 2019)
    res %= 2019
    d[res] += 1

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

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:
from collections import defaultdict
S = list(input())[::-1]
n = len(S)
d = defaultdict(int)
d[0] += 1
res = 0
for i, s in enumerate(S):
    res += int(s)*pow(10, i, 2019)
    res %= 2019
    d[res] += 1

ans = 0
for k in d.keys():
    dk = d[k]
    ans += dk*(dk-1)//2
print(ans)

Submission status: Accepted

Solution code:
M=2019;t=1;p=r=0;c=[1]+[0]*M
for x in input()[::-1]:p+=int(x)*t;p%=M;t=t*10%M;r+=c[p];c[p]+=1
print(r)

Submission status: Accepted

Solution code:
S = input()
mS, m10, mSd = [0], 1, {}
for i in range(len(S)):
    mS.append((mS[-1] + int(S[-(i + 1)]) * m10) % 2019)
    m10 = (m10 * 10) % 2019
for s in mS[1:]:
    mSd[s] = mSd.get(s, 0) + 1
print(mSd.get(0, 0) + sum([v * (v - 1) // 2 for v in mSd.values()]))

Submission status: Accepted

Solution code:
M=2019;t=1;p=0;c=[0]*M;r=0
for x in(input()+'0')[::-1]:p+=int(x)*t;p%=M;r+=c[p];c[p]+=1;t=t*10%M
print(r)

Submission status: Accepted

Solution code:
s = input()
n = len(s)
s_cu = [0] * (n+1)
counter = [0] * 2019
counter[0] += 1
for i in range(n):
    s_cu[i+1] = (int(s[n-i-1]) * pow(10,i,2019) + s_cu[i]) % 2019
    counter[s_cu[i+1]] += 1

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

print(ans)

Submission status: Accepted

Solution code:
mod=2019
s=input()

d={}
temp=1
cnt=0
we=0
d[0]=1
for i in range(len(s)):
  we=(we+int(s[-1-i])*temp)%mod
  temp=temp*10%mod
  
  if we not in d:
    d[we]=1
  else:
    d[we]+=1

#print(d)
for i in d:
  cnt+=(d[i]*(d[i]-1))//2
print(cnt)

Submission status: Accepted

Solution code:
#input
S = str(input())[::-1]

#output
from collections import Counter
#2019 = 3 * 673
N = len(S)
#上からi桁目までの数を決めた時2019の個数をdp[i]とする。
dp = [0] * (N)
dp[0] = int(S[0])
times =10
for i in range(N-1):
    dp[i+1] = dp[i] + times * int(S[i+1])
    dp[i+1] %= 2019
    times *= 10
    times %= 2019

T = Counter(dp)

answer = T[0]

for t in T.values():
    answer += t*(t-1)//2

print(answer)

Submission status: Accepted

Solution code:
M=2019;t=1;p=0;c=[0]*M;r=0
for x in(input()+'0')[::-1]:p=(int(x)*t%M+p)%M;r+=c[p];c[p]+=1;t=t*10%M
print(r)

Submission status: Accepted

Solution code:
M=2019
S=input()+'0'
t = 1
p=0
mcnt = [0] * 2019
ans = 0
for x in S[::-1]:
    dm = int(x) * t % M
    am = (dm+p) % M
    ans += mcnt[am]
    mcnt[am]+=1
    t=t*10%M
    p=am
print(ans)

Submission status: Accepted

Solution code:
p=d=2019
z=[0]*p
for i,j in enumerate(input()[::-1]):
	d=d+int(j)*pow(10,i,p)
	z[d%p]+=1
r=z[0]
for i in z:
	r+=i*(i-1)//2
print(r)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

S = list(map(int, list(input())))
#print(S)
mod = 2019
mod_list = [0]
#last = 0
ten = 1

for num in S[::-1]:
    yo = (num * ten + mod_list[-1]) % mod
    #print(yo)
    mod_list.append(yo)
    #last = yo
    ten = (ten * 10) % mod

cnt = [0]*2019

for yo in mod_list:
    cnt[yo] += 1

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

print(ans)

Submission status: Accepted

Solution code:
s=input()
n=len(s)
s_int=[0]*n
x=(pow(10,n-1))%2019
for i in range(n):
    s_int[i]=(int(s[i])*x)%2019
    x=(x*202)%2019
t=[0]*(n+1)
t[0]=int(s)%2019
for i in range(1,n):
    t[i]=t[i-1]-s_int[i-1]
    t[i]%=2019
t.sort()
t_set=sorted(list(set(t)))
tcnt=[0]*len(t_set)
num=0
for i in range(n+1):
    if t_set[num]==t[i]:
        tcnt[num]+=1
    else:
        num+=1
        tcnt[num]+=1
sum=0
for i in range(len(tcnt)):
    sum+=(tcnt[i]*(tcnt[i]-1))//2
print(sum)

Submission status: Accepted

Solution code:
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


# https://atcoder.jp/contests/abc158/submissions/10664809
S = sys.stdin.buffer.readline().decode().rstrip()
N = len(S)
P = 2019


def solve25():
    ans = 0
    for i, c in enumerate(S):
        if int(c) % P == 0:
            ans += i + 1
    return ans


if P in (2, 5):
    ans = solve25()
    print(ans)
    exit()

# U[i]: int(S[i:]) % P
U = [0] * N
n = 0
p = 1
for i, c in reversed(list(enumerate(S))):
    n += int(c) * p
    n %= P
    U[i] = n
    p *= 10
    p %= P

counts = [0] * P
for u in U:
    counts[u] += 1

ans = counts[0]
for i in reversed(range(N)):
    # U[i] を引いたときに 0 (mod P) となる数
    counts[U[i]] -= 1
    ans += counts[U[i]]
print(ans)

Submission status: Accepted

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

li = [0] * n
li[0] = int(s[-1])

for i in range(n-1):
    t = int(s[-i-2])
    li[i+1] = (li[i] + t * pow(10, i+1, 2019)) % 2019

dict1 = {}
for i in li:
    if i in dict1:
        dict1[i] += 1
    else:
        dict1[i] = 1

ans = 0

for v in dict1.values():
    ans += v * (v-1) // 2

if 0 in dict1:
    ans += dict1[0]

print(ans)

Submission status: Accepted

Solution code:
p=d=2019
z=[0]*p
for i,j in enumerate(input()[::-1]):
	d+=int(j)*pow(10,i,p)
	z[d%p]+=1
r=z[0]
for i in z:
	r+=i*(i-1)//2
print(r)

Submission status: Accepted

Solution code:
import collections
n = str(input())
ans,m,div = 0,0,[]
for i,j in enumerate(reversed(n)):
    m=(m+int(j)*pow(10,i,2019))%2019
    div.append(m)
div.append(0)
c = collections.Counter(div)
values, counts = zip(*c.most_common())
for i in range(0,len(counts)):
    ans += counts[i] *(counts[i]-1) /2
print(int(ans))

Submission status: Accepted

Solution code:
p=d=2019
z=[0]*p
for i,j in enumerate(input()[::-1]):
	d=d+int(j)*pow(10,i,p)
	z[d%p]+=1
r=z[0]
for i in range(p):
	r+=z[i]*(z[i]-1)//2
print(r)

Submission status: Accepted

Solution code:
s=[int(j) for j in input()][::-1]
c=[0]*2019
tmp=0
c[0]+=1
t=1
import numpy as np
for i in s:
    tmp+=t*i
    c[tmp%2019]+=1
    t=t*10%2019
c=np.array(c)
ans=c*(c-1)//2
print(ans.sum())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import collections
s = (input())

"""
n = len(s)
ans = 0
for i in range(n-4):
    for j in range(i+4,n+1):
        if int(s[i:j]) % 2019 == 0:
            ans += 1
print(ans)
"""

n = len(s)
ans = 0
l = 0
#r = l
num = int(s)

tmp = [0 for _ in range(n+1)]
#ten = [0 for _ in range(n)]
tmp1 = 0
#val = 1
for i in range(0,n):
    #ten[i] = val
    tmp1 += (int(s[n-i-1]) * pow(10, i, 2019))
    tmp[i+1] = tmp1 % 2019
    #val = (val * 10) % 2019
#print(tmp)

c = collections.Counter(tmp)
#print(c)
for i in range(0, 2020):
    a = c[i]
    if a > 0:
        ans += ((a * (a - 1)) // 2)
print(ans)

Submission status: Accepted

Solution code:
p=d=2019
z=[0]*p
for i,j in enumerate(input()[::-1]):
	d=(d+int(j)*pow(10,i,p))%p
	z[d]+=1
r=z[0]
for i in range(p):
	r+=z[i]*(z[i]-1)//2
print(r)

Submission status: Accepted

Solution code:
p=2019
s,a,d,z=input()[::-1],0,0,[0]*p
for i,j in enumerate(s):
	d=(d+int(j)*pow(10,i,p))%p
	z[d]+=1
r=z[0]
for i in range(p):
	r+=z[i]*(z[i]-1)//2
print(r)

Submission status: Accepted

Solution code:
def main():
  n, d, mods = 0, 1, [1]+[0]*2019
  for i in reversed(input()):
    n = (n+int(i)*d)%2019
    d = d*10%2019
    mods[n] += 1
  print(sum([int(i*(i-1)/2) for i in mods]))
main()

Submission status: Accepted

Solution code:
p=2019
s,a,d,z=input()[::-1],0,0,[0]*p
for i,j in enumerate(s):
	d=(d+(int(j)*pow(10,i,p)))%p
	z[d]+=1
r=z[0]
for i in range(p):
	l=z[i]
	r+=l*(l-1)//2
print(r)

Submission status: Accepted

Solution code:
def main():
  n, d, mods = 0, 1, [1] + [0] * 2019
  for i in reversed(input()):
    n = (n + int(i) * d) % 2019
    d = d * 10 % 2019
    mods[n] += 1
  print(sum([i * ( i - 1 ) // 2 for i in mods]))
main()

Submission status: Accepted

Solution code:
p=2019
s,a,d,z=input()[::-1],0,0,[0]*p
for i,j in enumerate(s):
	d=(d+(int(j)*pow(10,i,p)))%p
	z[d]+=1
r=z[0]
for i in range(p):
	r+=z[i]*(z[i]-1)//2
print(r)

Submission status: Accepted

Solution code:
S = str(input())
l = len(S)
mod = [0] * 2019
dp = 0
pw = 1
for i in range(l):
    mod[dp % 2019] += 1
    dp = dp + pw * int(S[-1-i])
    pw = (pw * 10) % 2019
mod[dp % 2019] += 1
cnt = 0
for i in range(2019):
    cnt += (mod[i]*(mod[i]-1))//2
print(cnt)

Submission status: Accepted

Solution code:
S=str(input())
n=len(S)
mod=2019
ans=0
mod_set=[0]*mod
mod_set[0]+=1
ten=1
k=0
for i in range(n-1,-1,-1):
    k=(k+ten*int(S[i]))%mod
    mod_set[k]+=1
    ten=(ten*10)%mod

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

Submission status: Accepted

Solution code:
p=2019
s,a,d,z=reversed(input()),0,0,[0]*p
for i,j in enumerate(s):
	d=(d+(int(j)*pow(10,i,p)))%p
	z[d]+=1
r=z[0]
for i in range(p):
	r+=z[i]*(z[i]-1)//2
print(r)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


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


def main():
    S = input().strip()[::-1]
    MOD = 2019
    T = [0, int(S[0])]
    t10 = 1
    for s in S[1:]:
        t10 *= 10
        t10 %= MOD
        T.append((T[-1] + int(s) * t10) % MOD)

    # print(T)

    cT = Counter(T)
    # print(cT)
    ans = 0
    for k in T:
        cT[k] -= 1
        ans += cT[k]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()
M = 2019
dp = [0] * M
dp[0] = 1
t = 0
for i, s in enumerate(S[::-1]):
    t = (t + int(s) * (pow(10, i, M))) % M
    dp[t] += 1

r = 0
for d in dp:
    r += d * (d - 1) // 2

print(r)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
s = input()
mods = [0]*2019
mods[0] += 1
# for i in range(len(s)):
#     value = int(s[i:])
#     mods[value % 2019] += 1
base = 1
value = 0
for c in map(int, reversed(s)):
    value += (c*base) % 2019
    base = (base * 10) % 2019
    # value = int(s[i:])
    mods[value % 2019] += 1
print(sum([mod*(mod-1)//2 for mod in mods]))

Submission status: Accepted

Solution code:
string=input()
length=len(string)
mod=[1]+[0]*2018
s=0
for i in range(length):
  s=(s+int(string[-1-i])*pow(10,i,2019))%2019
  mod[s]+=1
print(sum([i*(i-1)//2 for i in mod]))

Submission status: Accepted

Solution code:
import math

def readInt():
	return int(input())

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

def readChars():
	return input().split()

s = reversed(input())

ai = 0
si = 0

p = 2019
countarr = [0]*2019

for i, j in enumerate(s):
	ai = (int(j)*pow(10,i,p))%p
	si = (si+ai)%p
	countarr[si]+=1

res = countarr[0]
for i in range(p):
	c = countarr[i]
	res += c*(c-1)//2

print(res)

Submission status: Accepted

Solution code:
S = input()
m = 2019
dp = [0]*m
dp[0] = 1

acc, d = 0,1

for s in S[::-1]:
    acc = (acc + d*int(s)) % m
    dp[acc] += 1
    d = (d*10) % m

print(str(sum([n*(n-1)//2 for n in dp])))

Submission status: Accepted

Solution code:
def main():
  n, mods = 0, [1]+[0]*2019
  d = 1
  for j in map(int, input()[::-1]):
    n = (n+int(j)*d)%2019
    d = d*10%2019
    mods[n] += 1
  print(sum([i*(i-1)//2 for i in mods]))
main()

Submission status: Accepted

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

MOD = 2019
mod_cnt = [0]*MOD
mod_cnt[0] = 1
k = 0.1
t = 0
for i in range(1, N+1):
    k = int(k * 10) % MOD
    t = (t + k * int(S[-i])) % MOD
    mod_cnt[t] += 1
ans = 0
for cnt in mod_cnt:
    ans += (cnt * (cnt-1)) // 2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict
s = input()
mod = 2019
dct = defaultdict(int)
dct[0] = 1
x = 0
d = 1
for c in s[::-1]:
    x = (x+int(c)*d)%mod
    d = d*10%mod
    dct[x] += 1
ans = 0
for v in dct.values():ans += v*(v-1)//2
print(ans)

Submission status: Accepted

Solution code:
def main():
  n, mods = 0, [1]+[0]*2019
  d = 1
  for i, j in enumerate(reversed(input())):
    # n = (n+int(j)*pow(10, i, 2019))%2019
    n = (n+int(j)*d)%2019
    d=d*10%2019
    mods[n] += 1
  print(sum([i*(i-1)//2 for i in mods]))
main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

import random

def main():
    s = list(map(int, S()[::-1]))
    N = len(s)
    P = 2019
    ans = 0
    cnts = [0] * P
    cnts[0] = 1
    A = [0] * N
    D = [0] * N

    for i in range(N):
        d = s[i] * pow(10, i, P)
        A[i] = d % P
        if i == 0:
            D[i] = A[i]
        else:
            D[i] = (D[i-1] + A[i]) % P
        # sum_of_d = (sum_of_d + d) % p
        # cnts[sum_of_d] += 1

    for d in D:
        cnts[d] += 1

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  k=1
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*k)%2019
      k*=10
      k=k%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def main():
  n, mods = 0, [1]+[0]*2019
  for i, j in enumerate(reversed(input())):
    n = (n+int(j)*pow(10, i, 2019))%2019
    mods[n] += 1
  print(sum([i*(i-1)//2 for i in mods]))
main()

Submission status: Accepted

Solution code:
def main():
  n ,mods = 0, [1]+[0]*2019
  for i, j in enumerate(reversed(input())):
    n = (n+int(j)*pow(10, i, 2019))%2019
    mods[n] += 1
  print(sum([i*(i-1)//2 for i in mods]))
main()

Submission status: Accepted

Solution code:
def main():
  import collections
  s = input()
  r = []
  x = 0
  for i in range(len(s)):
    x += int(s[-i-1])*pow(10,i,2019)
    x %= 2019
    r.append(x)
  d = collections.Counter(r) 
  ans = 0
  if 0 in d:
    ans += d[0]
  for k,v in d.items():
    if v >= 2:
      ans += v*(v-1)//2
  print(ans)

main()

Submission status: Accepted

Solution code:
S = str(input())
h = [int(x) for x in list(S)]
N = len(h)
a = [0] * 2019
a[0] = 1
T = 0
r = 1
c = 0
for i in range(N-1, -1, -1):
    T = (T + h[i] * r) % 2019
    r = r * 10
    r = r % 2019
    c += a[T]
    a[T] += 1
print(c)

Submission status: Accepted

Solution code:
def main():
  n,mods=0,[1]+[0]*2019
  for i,j in enumerate(reversed(input())):
    n=(n+int(j)*pow(10,i,2019))%2019
    mods[n]+=1
  print(sum([i*(i-1)//2 for i in mods]))
main()

Submission status: Accepted

Solution code:
s = list(map(int,input()))
d = [0 for _ in range(2019)]
r = 0
x = 1
for si in reversed(s):
  r += si*x
  r %= 2019
  d[r] += 1
  x *= 10
  x %= 2019
ans = d[0]
for v in d:
  if v >= 2:
    ans += v*(v-1)//2
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np


def solve(S):
    dp = np.zeros(2019, np.int64)
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % 2019
        dp = np.roll(dp, x)
        answer += dp[0]
        pow10 *= 10
        pow10 %= 2019
    return answer


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i4[:],)')(solve)
    cc.compile()


try:
    from my_module import solve
except:
    cc_export()
    exit()

S = np.array(list(read().rstrip()), dtype=np.int32) - ord('0')
print(solve(S))

Submission status: Accepted

Solution code:
n=0
mods=[1]+[0]*2019
for i,j in enumerate(reversed(input())):
  n=(n+int(j)*pow(10,i,2019))%2019
  mods[n]+=1
print(sum([i*(i-1)//2 for i in mods]))

Submission status: Accepted

Solution code:
S = input()
N = len(S)
mod = 2019
num = [0 for i in range(2019)]
num[0] = 1
t = 1
rem = 0

for i in reversed(S):
    rem += int(i) * t
    rem %= mod
    t *= 10
    t %= mod
    num[rem] += 1

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

Submission status: Accepted

Solution code:
n=0
mods=[0]*2019
mods[0]=1
for i,j in enumerate(reversed(input())):
  n=(n+int(j)*pow(10,i,2019))%2019
  mods[n]+=1
print(sum([i*(i-1)//2 for i in mods]))

Submission status: Accepted

Solution code:
s=input()
n=0
ans=0
A=[0]*2019
A[0]=1
for i,j in enumerate(reversed(s)):
  n=(n+int(j)*pow(10,i,2019))%2019
  #print(i,n)
  A[n]+=1
for i in A:
  ans+=i*(i-1)//2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s = input()
mods = [0]*2019
mods[0] = 1
accu = 0
for i, j in enumerate(reversed(s)):
    accu += int(j)*pow(10, i, 2019)
    accu %= 2019
    mods[accu] += 1
ans = 0
for i in mods:
    ans += i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
n,ans=0,0
mods=[0]*2019
mods[0]=1
for i,j in enumerate(reversed(input())):
  n=(n+int(j)*pow(10,i,2019))%2019
  mods[n]+=1
for i in mods:ans+=i*(i-1)//2
print(ans)

Submission status: Accepted

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

mod = 2019
d = [0 for i in range(2019)]
d[0] = 1
t = 1
rem = 0

for i in reversed(S):
    rem += int(i) * t
    rem %= mod
    t *= 10
    t %= mod
    d[rem] += 1

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

Submission status: Accepted

Solution code:
from collections import defaultdict


s = input()
n = len(s)

dd = defaultdict(int)

d = [0 for i in range(2019)]
d[0] = 1
tmp = 0
_10 = 1
# print(s, n)
for i in range(n - 1, -1, -1):
    # print(i, s[i])
    # print(int(s[i]), _10)
    tmp += (int(s[i]) * _10) % 2019
    _10 *= 10
    _10 %= 2019
    # print(tmp, tmp % 2019)
    d[tmp % 2019] += 1

# for i in reversed(range(0, n)):
#     print((b[n-i-1]), int(s[i]))
#     tmp += _10 * int(s[i]) % 2019
#     _10 *= 10 % 2019
#     print(tmp, tmp % 2019)
#     a[tmp % 2019] += 1


# count = 0
# for i in range(len(d)):
#     if d[i] >= 2:
#         count += (d[i])*(d[i]-1)//2
# print(count)

# # print(dd)
print(sum(v*(v-1)//2 for v in d))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import collections
s = (input())

"""
n = len(s)
ans = 0
for i in range(n-4):
    for j in range(i+4,n+1):
        if int(s[i:j]) % 2019 == 0:
            ans += 1
print(ans)
"""

n = len(s)
ans = 0
l = 0
#r = l
num = int(s)

tmp = [0 for _ in range(n+1)]
ten = [0 for _ in range(n)]
tmp1 = 0
val = 1
for i in range(0,n):
    ten[i] = val
    tmp1 += (int(s[n-i-1]) * val)
    tmp[i+1] = tmp1 % 2019
    val = (val * 10) % 2019
#print(tmp)

c = collections.Counter(tmp)
#print(c)
for i in range(0, 2020):
    a = c[i]
    if a > 0:
        ans += ((a * (a - 1)) // 2)
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

def main():
    S = input()
    N = len(S)
    memo = [0] * 2019
    now = 0
    ten = [0] * 200100
    ten[0] = 1
    for j in range(len(ten)-50):
        ten[j+1] = ten[j]*10%2019

    for i in range(N):
        now += int(S[-(i+1)])*ten[i]
        now %= 2019
        memo[now] += 1
    
    ans = 0
    for k in range(2019):
        ans += (memo[k] * (memo[k]-1)) // 2

    ans += memo[0]
    #m = collections.Counter(memo)
    #print(m)   
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=0
ans=0
mods=[0]*2019
mods[0]=1
for i,j in enumerate(reversed(input())):
  n=(n+int(j)*pow(10,i,2019))%2019
  mods[n]+=1
for i in mods:ans+=i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    S = input()
    d = defaultdict(int)
    d[0] = 1

    num = 0
    for digit, c in enumerate(S[::-1]):
        num += int(c) * pow(10, digit, 2019)
        num %= 2019
        d[num] += 1
    ans = sum([d[i]*(d[i]-1)//2 for i in range(2019)])
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = 0
ans = 0
mods = [0]*2019
mods[0] = 1
for i, j in enumerate(reversed(input())):
  n = (n+int(j)*pow(10, i, 2019))%2019
  mods[n] += 1
for i in mods: ans += i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve(S):
    dp = [0] * 2019
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % 2019
        newdp = [0] * 2019
        for i in range(2019-x):
            newdp[x+i] += dp[i]
        for i in range(x):
            newdp[i] += dp[2019-x+i]
        answer += newdp[0]
        pow10 *= 10
        pow10 %= 2019
        dp = newdp
    return answer


S = [x - ord('0') for x in read().rstrip()]
print(solve(S))

Submission status: Accepted

Solution code:
S = input()
S = list(map(int, S))

r = 0
pow10 = 1
counter = [0] * 2019
counter[0] = 1
for i in range(1, len(S) + 1):
    r = (r + pow10 * S[-i]) % 2019
    counter[r] += 1
    pow10 *= 10
    pow10 %= 2019

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

print(ans)

Submission status: Accepted

Solution code:
S = input()
N = len(S)
A = [int(S[i]) for i in range(N)]
cnt = [0] * 2019
cnt[0] = 1
p = 1
dp = 0

for i in reversed(range(N)):
    dp = (dp + A[i]*p) % 2019
    cnt[dp] += 1
    p = 10 * p % 2019
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
s = input()
p = 2019
n = 0
ans = 0
mods = [0]*p
mods[0] = 1
for i, j in enumerate(reversed(s)):
  n += int(j)*pow(10, i, p)
  n %= p
  mods[n] += 1
for i in mods:
  ans += i*(i-1)//2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S = input()
S = list(map(int, S))

r = 0
t = 1
d = [0] * 2019
d[0] = 1
for i in range(1, len(S) + 1):
    r = (r + t * S[-i]) % 2019
    d[r] += 1
    t = t * 10 % 2019

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s = list(input())
s.reverse()
r = [0 for _ in range(2019)]
p = 0
for i in range(len(s)):
    p += pow(10, i, 2019) * int(s[i])
    p %= 2019
    r[p] += 1
ans = 0
for i in r:
    if i >= 2:
        ans += ((i - 1) * i) // 2
ans += r[0]
print(ans)

Submission status: Accepted

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

res = 0
tmp = [0] * 2019
tmp[0] = 1
sum_of_digits = 0
d = 1

for c in S:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    tmp[sum_of_digits] += 1

for t in tmp:
    res += (t * (t - 1)) // 2

print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S = input()
if len(S) < 4:
  print(0)
else:
  N = len(S)
  x = 0
  d = [0]*2019
  d[0] = 1
  for i, s in enumerate(reversed(S)):
    x = (x+int(s)*pow(10,i,2019))%2019
    d[x] += 1
  print(sum([m*(m-1)//2 for m in d]))

Submission status: Accepted

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


def solve(S: str):

    l = [0] * 2019
    ps = 0
    d = 1
    for i in range(1, len(S) + 1):
        ps += int(S[-i]) * d
        l[ ps % 2019 ] += 1
        d = d * 10 % 2019

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

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S = input()
mod_list = [0 for i in range(2019)]
mod_list[0] += 1
number = 0
ten_count = 1
for s in S[::-1]:
    number += pow(10, ten_count, 2019) * int(s)
    ten_count += 1
    mod_list[number % 2019] += 1

ans = 0
for i in mod_list:
    if i > 1:
        ans += i * (i - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
S = input()
S = list(map(int, S))

t = 1
r = 0
d = [0] * 2019
d[0] += 1
for n in reversed(S):
    r = (r + n * t) % 2019
    t = t * 10 % 2019
    d[r] += 1

ans = 0
for m in d:
    ans += m * (m-1) // 2

print(ans)

Submission status: Accepted

Solution code:
import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)
S = input()[::-1]
N = len(S)
cnt = [0]*(N+1)
ans = 0
keta = 1
for i in range(N):
    cnt[i] = (cnt[i-1] + int(S[i])*keta)%2019
    keta *= 10
    keta %= 2019
cnt2 = [0]*2020
for i in cnt:
    cnt2[i] += 1
for i in cnt2:
    if i >= 2:
        ans += C(i,2)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
from numba import njit

@njit('(i4[:],)', cache=True)
def solve(S):
    dp = np.zeros(2019, np.int64)
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % 2019
        newdp = np.zeros_like(dp)
        newdp[x:] += dp[:-x]
        newdp[:x] += dp[-x:]
        answer += newdp[0]
        pow10 *= 10
        pow10 %= 2019
        dp = newdp
    return answer


S = np.array(list(read().rstrip()), dtype=np.int32) - ord('0')
print(solve(S))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
from numba import njit

@njit('(i4[:],)')
def solve(S):
    dp = np.zeros(2019, np.int64)
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % 2019
        newdp = np.zeros_like(dp)
        newdp[x:] += dp[:-x]
        newdp[:x] += dp[-x:]
        answer += newdp[0]
        pow10 *= 10
        pow10 %= 2019
        dp = newdp
    return answer


S = np.array(list(read().rstrip()), dtype=np.int32) - ord('0')
print(solve(S))

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    S = args[0]
    m = 2019
    dp = [0]*m
    dp[0] = 1

    acc, d = 0, 1
    for s in S[::-1]:
        acc = (acc+d*int(s)) % m
        dp[acc] += 1
        d = (d*10) % m
    return str(sum([n*(n-1)//2 for n in dp]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))