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:
S = list(map(int, list(input()[::-1])))

N = len(S)
P = 2019
C = [0] * P
B = 1
t = 0
ans = 0
for i in range(N):
    C[t] += 1
    t = (t + S[i] * B) % P
    ans += C[t]
    B = B * 10 % P
print(ans)

Submission status: Accepted

Solution code:
s = str(input())
L = len(s)
dict = [0] * 2019
dict[0] += 1
num = 0
for i in range(L-1, (-1), (-1)):
    num += (int(s[i]) * pow(10,(L-i-1), 2019))%2019
    amari = num % 2019
    dict[amari] += 1
ans = 0
for j in range(2019):
    ans += (dict[j]*(dict[j]-1))/2
print(int(ans))

Submission status: Accepted

Solution code:
## coding: UTF-8

S = input()[::-1] #文字列型で受け取る
N = len(S)
#print(S)

remainder = [0] * 2019
tmp = 0
rad = 1 # *10**(i) % 2019
for i in range(N):
    r = int(S[i])
    tmp += r*rad
    tmp %= 2019
    #print(tmp)
    remainder[tmp] += 1
    rad *= 10
    rad %= 2019

    #print(S[i:], int(S[i:])%2019)
    #remainder[int(S[i:])%2019]+= 1
remainder[0] += 1
#print(-1)



answer = 0
for i in range(2019):
    p = remainder[i]
    answer += p*(p-1)/2
print(int(answer))

Submission status: Accepted

Solution code:
S = input()
size = len(S)
ans = 0
d = [0]*2019
pre = ''
ln = 0
v = 1
  
for i in range(1,size+1):
  md = (ln +(int(S[-1*i])*v))%2019
  d[md] += 1
  ln = md
  v *= 10
  v %= 2019

d[0] += 1
for i in range(2019):
  ans += d[i]*(d[i]-1)/2 #1~(n-1)までの和

print(int(ans))

Submission status: Accepted

Solution code:
s = input()
counts = [0]*2019
counts[0] += 1
num = 0
d = 1
for c in reversed(s):
    d %= 2019 
    num += int(c)%2019 * d
    counts[num % 2019] += 1
    d *= 10
ans = 0
for count in counts:
    ans += count*(count -1) // 2
print(ans)

Submission status: Accepted

Solution code:
S=input()[::-1]
l=len(S)
t=0
p=0
 
ss=[0]*2019
ss[0]=1
d=1
for i in S:
    p=(p+int(i)*d)%2019
    d*=10
    d%=2019
    ss[p]+=1
 
for c in ss:
    t+=c*(c-1)//2
print(t)

Submission status: Accepted

Solution code:
s=input()
n=len(s)
s=s[::-1]
cnt_mod=[0]
m=0
d=1
for i in range(n):
  m+=int(s[i])*d
  m%=2019
  d*=10
  d%=2019
  cnt_mod.append(m)

from collections import Counter
c=Counter(cnt_mod)
ans=0
for v in c.values():
  ans+=v*(v-1)//2
print(ans)

Submission status: Accepted

Solution code:
def main():
    s = list(map(int, list(input())))
    r = [0]*len(s)
    r[0] = int(s[-1])
    for i in range(1,len(s)):
        temp = s[-(1+i)]*pow(10,i,2019)
        r[i] = (temp+r[i-1])%2019

    ans = 0
    cts = [0]*2019
    for i in r:
        ans+=cts[i]
        cts[i]+=1
    
    ans+=cts[0]

    print(ans)

main()

Submission status: Accepted

Solution code:
s = input()
counts = [0]*2019
counts[0] += 1
num = 0
d = 1
for c in reversed(s):
    num += int(c) * d
    counts[num % 2019] += 1
    d *= 10
    d %= 2019
ans = 0
for count in counts:
    ans += count*(count -1) // 2
print(ans)

Submission status: Accepted

Solution code:
S = input()[::-1]
digits = 1
num, ans = 0, 0
mod_list = [0] * 2019
mod_list[0] = 1

for c in S:
  num += int(c) * digits
  mod_list[num % 2019] += 1
  digits *= 10
  digits %= 2019

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

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    for i in range(len_S):
        for j in range(i+3,len_S):
            if j == i+3:
                mod = int(S[len_S-j-1:len_S-i])%3
            else:
                mod = (mod+int(S[len_S-j-1]))%3
            if mod == 0:
                _ = int(S[len_S-j-1:len_S-i])
                if _%673==0:
                    cnt += 1
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    #main()

    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    mod_arr = [0] * 2019
    mod_arr[0] += 1

    num, dec = 0, 1
    for s in S[::-1]:
        num += int(s)*dec
        num %= 2019
        dec *= 10
        dec %= 2019
        mod_arr[num] += 1

    for i in range(2019):
        if mod_arr[i] > 0:
            cnt += mod_arr[i]*(mod_arr[i]-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
p = 2019
s = input()
n = len(s)
M = [0]*(p)
M[0] = 1
m = 0
d = 1

for i in range(n):
  m = (m + int(s[-i-1])*d ) % p  
  M[m] += 1
  d = (d*10) % p
  
ans = 0  
for m in M:
  if m>=2:
    ans += m*(m-1)//2
    
print(ans)

Submission status: Accepted

Solution code:
s = input()[::-1]
d = 1
num = 0
ans = 0
mod_list = [0] * 2019
mod_list[0] = 1

for char in s:
    num += int(char) * d
    mod_list[num % 2019] += 1
    d *= 10
    d %= 2019

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

print(ans)

Submission status: Accepted

Solution code:
s = input()[::-1]
d = 1
num = 0
ans = 0
mod_list = [0] * 2019
mod_list[0] = 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d %= 2019
    mod_list[num % 2019] += 1

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

print(ans)

Submission status: Accepted

Solution code:
s = input()
l = len(s)
mod = [1] + [0 for _ in range(2019)]
ml = [0 for _ in range(l + 1)]
ans = 0

tmp = 0
for idx, degit in enumerate(s[::-1]):
    m = int(degit) * pow(10, idx, 2019)
    m = (m + tmp) % 2019
    tmp = m
    ans += mod[m]
    mod[m] += 1

print(ans)

Submission status: Accepted

Solution code:
s=input()
s=s[::-1]
memo=[0]*2019
memo[0]=1
current=0

for i in range(len(s)):
    current+=int(s[i])*pow(10,i,2019)
    current%=2019
    memo[current]+=1

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

Submission status: Accepted

Solution code:
S = input()
lmax = len(S)
modulo = list([0]*2019)
mod10 = 10%2019
mod = int(S[-1])%2019
modulo[mod] += 1
for s in reversed(S[:-1]):
    mod = (mod + mod10*int(s))%2019
    modulo[mod] += 1
    mod10 = (mod10*10)%2019
ans = sum(list(map(lambda x: x*(x-1)//2, modulo)))+modulo[0]
print(ans)

Submission status: Accepted

Solution code:
S = input()

p = 2019
N = len(S)
t = [0]*(N+1)
for i in range(N-1,-1,-1):
  k = (int(S[i]) * pow(10,N-i-1,p))%p
  t[i] = (t[i+1]+k)%p
t= t[:N]
cnt = [0]*p
for i in range(N):
  cnt[t[i]]+=1
ans = 0
for i in range(p):
  m = cnt[i]
  if i == 0 and m > 0:
    ans +=  (m*(m+1))//2
  else:
    ans += (m*(m-1))//2
print(ans)

Submission status: Accepted

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


_MOD = {0: 1}
amari = 0
a = 1
ans = 0

for i in S:
    amari = (amari + int(i) * a) % 2019
    a = (a * 10) % 2019  #表示桁 1あたりの余
    if amari in _MOD:
        _MOD[amari] = _MOD[amari] + 1
    else:
        _MOD[amari] = 1
    
for amari in _MOD:
    m = _MOD[amari]
    ans += (m * (m - 1)) // 2

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
s = input()
n = len(s)
mod = [0] * (n+1)

def pow_k(x, n):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x % 2019
        x = x ** 2 % 2019
        n //= 2

    return K * x % 2019

rui = 0
for i in range(n):
    rui = (int(s[n-1-i]) * pow_k(10, i) + rui) % 2019
    mod[n-1-i] = rui
    
b = Counter(mod)
c = list(b.values())
c.sort(reverse = True)

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

print(ans)

Submission status: Accepted

Solution code:

S=input()[::-1]
l=len(S)
t=0
p=0

ss=[0]*2019
ss[0]=1
d=1
for i in S:
    p=(p+int(i)*d)%2019
    d*=10
    d%=2019
    ss[p]+=1

for c in ss:
    t+=c*(c-1)//2
print(t)

Submission status: Accepted

Solution code:
S=input()
R_S=S[::-1]
ans=0
count=[1]+[0]*2018
remainder=0

i=0
while i<len(S):
    remainder+=int(R_S[i])*pow(10,i,2019)
    remainder=remainder%2019
    ans+=count[remainder]
    count[remainder]+=1
    i+=1

print(ans)

Submission status: Accepted

Solution code:
# 君指先跃动の光は、私の一生不変の信仰に、唯私の超电磁炮永生き！
from sys import stdin, stdout
import math
import bisect
from collections import defaultdict
import datetime
import random

s = stdin.readline().strip()
cnt = 0
# s = ''
# for i in range(200000):
#     s += str(random.randint(1, 9))
    
# print('start')

d = defaultdict(int)
d[0] = 1
# starttime = datetime.datetime.now()
now = 0
mul = 1
for each in s[::-1]:
    now = (int(each) * mul + now) % 2019
    cnt += d[now]
    d[now] += 1
    mul = (mul * 10) % 2019
stdout.writelines(str(cnt) + '\n')
# stoptime = datetime.datetime.now()
# print(stoptime - starttime)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 2019


def resolve():
    s = input()
    n = len(s)
    s = s[::-1]

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

    D = Counter(ruiseki)

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

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
s=input()



"""
◆エッセンス1：割り切れるとは、二つに分けた数字のmodが一緒
例)
1817181712114の
18171が2019で割り切れるかどうかを判断する。

18171は(181712114-2114)/10000となるので、
181712114mod2019＝2114mod2019の時、2019で割り切れる。

1817181712114mod2019
 817181712114mod2019
  17181712114mod2019
   7181712114mod2019
    181712114mod2019
     81712114mod2019
      1712114mod2019
       712114mod2019
    　　・・・・
とmodを調べていき、値が同じペアは割り切れる。
"""

"""
◆エッセンス2：大きい数字は都度modを取る

これだけでもループは1回になるんだけど、
|S|が長すぎてTLEとなってしまう（|S|は10**5）
1234567 mod 2019
=(1*10**7)mod2019 + (234567mod2019)
=(1*10mod2019 * 10**6mod2019)+ (234567mod2019)

10**nを毎回modを取ることで、計算する数字の長さを短くする。

"""



#modの値を保持する配列
cnt=[0]*2019
#mod2019 =0 は、それ一つで割り切れるので。引き算をする必要が無い。
cnt[0]=1

#10の倍数を保持する
fac=1
ss=0
for i in range(len(s)):
    #後ろの数字から順番にとってくる
    ss += int(s[len(s)-i-1])*fac
    ss%=2019
    fac=fac*10
    fac%=2019
    cnt[ss]+=1
    

result=0
for c in cnt:
    result+=c*(c-1)//2

print(result)

Submission status: Accepted

Solution code:
s = input()[::-1]
n = len(s)
x = 1
tot = 0 # 累積和
cnt = [0 for i in range(2019)] # 累積和の値になる個数

ans = 0
for i in range(n):
    # print('======={}======'.format(i))
    cnt[tot] += 1
    tot += int(s[i])*x
    # print(tot)
    tot %= 2019
    # print(tot)
    ans += cnt[tot]
    # print('ans:', ans)
    x = x*10%2019

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 2019


def resolve():
    s = input()
    n = len(s)
    s = s[::-1]

    ruiseki = 0
    cnt = [0] * mod
    ans = 0
    for i in range(n):
        cnt[ruiseki] += 1
        ruiseki += int(s[i]) * pow(10, i, mod)
        ruiseki %= mod
        ans += cnt[ruiseki]

    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
s = input()

arr = []
amari = [0 for i in range(2019)]
amari[0] +=1
ans = 0
cnt = 0
keta = 1
for i in range(len(s)):
    cnt = (cnt + int(s[-(i+1)]) * keta) % 2019
    arr.append(cnt)
    keta =keta * 10 % 2019

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

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import defaultdict
S = list(input().rstrip())
r = 1
i=len(S)
acc=0
dd = defaultdict(int)
dd[0]+=1
for s in S[::-1]:
    acc+=r*int(s)
    acc%=2019
    r*=10
    r%=2019

    dd[acc]+=1
ans=0
for i in dd.values():
    ans+=(i*(i-1))//2
print(ans)

Submission status: Accepted

Solution code:
s = input()
s = s[::-1]
l = len(s)
count = [0] * 2019
res = 0
count[res] = 1
d = 1
for i in s:
    res += int(i) * d
    res %= 2019
    count[res] += 1
    d *= 10
    d %= 2019
print(int(sum([m*(m-1)/2 for m in count])))

Submission status: Accepted

Solution code:
s = input()
s = s[::-1]
n = len(s)

num = [0]*2019
num[0] = 1
number = 0
d = 1

for i in s:
    number += int(i)*d
    num[number%2019] += 1
    d *= 10
    d %= 2019

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
s=input()
s=s[::-1]
n=len(s)

count=[0]*2019
count[0]=1
num,d=0,1

for i in s:
  num+=int(i)*d
  num%=2019
  d*=10
  d%=2019
  count[num]+=1

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

Submission status: Accepted

Solution code:
s = input()[::-1]
counts = [0] * 2019
counts[0] = 1
num, d = 0, 1
result = 0

for i in s:
    num += int(i) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1
    
for cnt in counts:
    result += cnt*(cnt-1)//2
    
print(result)

Submission status: Accepted

Solution code:
s=input()
s=s[::-1]
n=len(s)
count=[0]*2019
count[0]=1
num,d=0,1

for i in s:
  num+=int(i)*d
  num%=2019
  d*=10
  d%=2019
  count[num]+=1

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

Submission status: Accepted

Solution code:
mod = 2019
cnt = [0 for i in range(2019)]
cnt[0] = 1
x = 0
ten = 1
ans = 0

for s in input()[::-1]:
    x = (x + int(s) * ten) % mod
    ans += cnt[x]
    cnt[x] += 1
    ten *= 10
    ten %= mod

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

for i in countArray:
    count += (i * (i - 1)) // 2
print(count)

Submission status: Accepted

Solution code:
s = input()
MOD = 2019
cnt = [0]*MOD
cnt[0] = 1
cum = 0
for n, x in enumerate(reversed(s)):
    cum = (cum + int(x)*pow(10, n, MOD)) % MOD
    cnt[cum] += 1
print(sum(v*(v-1)//2 for v in cnt))

Submission status: Accepted

Solution code:
from collections import defaultdict

s = input()
n = len(s)
MOD = 2019

dd = defaultdict(int)
dd[0] += 1
prev = 0
for i in reversed(range(n)):
    x = (prev + int(s[i])*pow(10, n-i, MOD)) % MOD
    dd[x] += 1
    prev = x

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

Submission status: Accepted

Solution code:
s = input()

mod = [0]*2019
mod[0] = 1
t, a, n = 0 , 1, len(s)
s = s[::-1]
for i in range(n):
    t = (t + int(s[i])*a) % 2019
    a = a * 10 % 2019
    mod[t] += 1
ans = 0
for i in range(2019):
    ans += mod[i]*(mod[i]-1)//2
print(ans)

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main2():
	#a = int(input())
	#b , c = IN()
	s =  input()
	#s='1'*3000
	s=[int(c) for c in s]
	ll=len(s)
	ret_count=0
	for i in range(1):#ll-2):
		v = s[i]
		vs=[v]
		for c in s[i+1:]:
			v = (v * 10 + c) % 2019
			vs.append(v)
			if v == 0:
				ret_count += 1
		else:
			pa(vs)	
	print(ret_count)
				
def main():
	#a = int(input())
	#b , c = IN()
	s =  input()
	#s='1'*3000
	s=[int(c) for c in s]
	s=s[::-1]
	ll=len(s)
	cc=[0]*2019
	p=0
	tt=1
	cc[0]=1
	for i, v in enumerate(s):
		tt *= 10
		tt %= 2019
		p += tt*v
		p %= 2019
		cc[p] += 1
	
	ret = 0
	for v in cc:
		ret += v *(v-1)//2
	print(ret)	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
s = input()
#s = '9' * 200000

mod = [1] + [0]*2018
t, a, n = 0 , 1, len(s)
s = s[::-1]
for i in range(n):
    t = (t + int(s[i])*a) % 2019
    a = a * 10 % 2019
    mod[t] += 1
ans = 0
for i in range(2019):
    ans += mod[i]*(mod[i]-1)//2
print(ans)

Submission status: Accepted

Solution code:
s = input()
#s = '9' * 200000

mod = [1] + [0]*2018
t = 0
a = 1
n = len(s)
s = s[::-1]
for i in range(n):
    t = (t + int(s[i])*a) % 2019
    a = a * 10 % 2019
    mod[t] += 1
ans = 0
for i in range(2019):
    ans += mod[i]*(mod[i]-1)//2
print(ans)

Submission status: Accepted

Solution code:
S = input()

ls =[0 for i in range(2019)]
ls[0] += 1
p_amari = 0
ret = 0
len_s = len(S)
for i in range(len_s) :
	p_amari = ( int(S[len_s-1-i]) * pow(10, i, 2019) + p_amari ) % 2019
	ret += ls[p_amari]
	ls[p_amari] += 1
print(int(ret))

Submission status: Accepted

Solution code:
# multiple
line = input()
ln = 0
d = 1
counts=[0]*2019
for i in range(1,len(line) + 1):
    ti1 = (ln +(int(line[-1*i])*d))%2019
    counts[ti1] += 1
    ln = ti1
    d *= 10
    d %= 2019
total = 0
counts[0] +=1
for i in range(len(counts)):
    total += counts[i]*(counts[i] - 1)/2
print(int(total))

Submission status: Accepted

Solution code:
s = input()
dic = {}
for i in range(2019):
  dic[i] = 0
dic[0] = 1
m = 0
decimal = 1
for j in range(1, len(s)+1):
  m += int(s[-j]) * decimal
  m %= 2019
  dic[m] += 1
  decimal *= 10
  decimal %= 2019

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

Submission status: Accepted

Solution code:
s=input()
s_rev=s[::-1]

mod_count=[0]*2019
mod_count[0]=1
d=1
num=0

for char in s_rev:
  num=num+int(char)*d
  num=num%2019
  d=d*10
  d=d%2019
  #print(type(num),type(mod_count))
  mod_count[num]=mod_count[num]+1

ans=0
for cnt in mod_count:
  ans=ans+cnt*(cnt-1)/2
  
print(int(ans))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

lines = 1
inp = list()

for _ in range(lines):
    inp.append(sys.stdin.readline().strip())


s = inp[0]
n = len(s)

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

b = 0
d = 1

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

result = 0

for v in tmp.values():
    result += int(v * (v - 1) / 2)

print(result)

Submission status: Accepted

Solution code:
S = input()

count = 0
mod_check = [0] * 2019
mod_check[0] = 1
check_S = 0
d = 1
for i in reversed(S):
    check_S += int(i) * d
    check_S %= 2019
    mod_check[check_S] += 1
    d *= 10
    d %= 2019
    count += 1
mod_match = 0
for x in mod_check:
    mod_match += x * (x - 1) // 2
print(mod_match)

Submission status: Accepted

Solution code:
s = input()
mod = 2019
mod_lst = [0]*mod
mod_lst[0] =1
x = 0
t = 1
for i in reversed(s):
    x += int(i) * t
    y = x % mod
    t *= 10
    t %= mod
    mod_lst[y] += 1


count = 0
for j in mod_lst:
    a = j*(j-1)//2
    count += a
print(count)

Submission status: Accepted

Solution code:
s = input()
l = len(s)
c = 2019
tm = 1
ti = int(s[-1])
co = [0]*2019
co[ti] += 1
for i in range(1, l):
    tm = tm*10 % c
    ti += int(s[l-i-1]) * tm
    ti = ti % c
    co[ti] += 1
if co[0] != 0:
    co[0] += 1
print(sum([i*(i-1)//2 for i in co]))

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にいれる
S = input()[::-1]
#各modの値を数えるためのリスト
counts = [0]*2019
#mod==0になったら1つだけでも2019の倍数になっているので初めから＋１しておく
counts[0] = 1
#numはSの各桁の数字、dは桁数（1の位、10の位、、）
num,d = 0,1
for i in S:
    num += int(i)*d
    num %= 2019
    d *= 10
    #ここがポイント。かける桁数の値も先にmodを計算してからかけると計算量が減らせる。
    d %= 2019
    counts[num] += 1

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

print(ans)

Submission status: Accepted

Solution code:
s = str(input())
cnt = [0]*2019
cnt[0] += 1

si = [0] * (len(s)+1) #mod2019の累積和用に
tmp = 0
for i in range(1,len(s)+1): #累積和の作成
    tmp += int(s[-i])%2019 * pow(10,i-1,2019)#ここでpowを使わないとTLEする
    si[i] = tmp % 2019
    cnt[si[i]] += 1

ans = 0
for b in cnt:#aがb回出てきたよ
    ans += b*(b-1)//2

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
s = str(input())

si = [0] * (len(s)+1) #mod2019の累積和用に
tmp = 0
for i in range(1,len(s)+1): #累積和の作成
    tmp += int(s[len(s)-i])%2019 * pow(10,i-1,2019)
    si[i] = tmp % 2019

c = Counter(si)
ans = 0
for b in list(c.values()):#aがb回出てきたよ
    ans += b*(b-1)//2

print(ans)

Submission status: Accepted

Solution code:
s = str(input())
N = len(s)
array = [0]*2019
array[0] += 1
count = 0
d = 1
r = 0
for i in reversed(range(0, N)):
    #x = s[i:N]
    #y = int(x)
    r = ( r + int( s[i] ) * d ) % 2019
    d = d * 10 % 2019
    array[r] += 1
for i in array:
    count += i*(i-1)/2
print(int(count))

Submission status: Accepted

Solution code:
s=input().rstrip()
ans=[0 for i in range(2019)]
tmp=0
a=1
rs=reversed(s)
for i in rs:
    ans[tmp%2019]+=1
    tmp=(tmp+int(i)*a)%2019
    a*=10
    a%=2019
ans[tmp%2019]+=1
count=0
for i in ans:
    count+=int(i*(i-1)/2)
print(count)

Submission status: Accepted

Solution code:
s = input()[::-1]
m = [0]*2019
m[0] = 1
d = 1
t = 0
for i in s:
    t += int(i)*d
    t %= 2019
    m[t] += 1
    d = (d*10)%2019


def c2(n):
    return n*(n-1)//2
print(sum([c2(i) for i in m]))

Submission status: Accepted

Solution code:
s = input()[::-1]
counts = [0] * 2019
counts[0] = 1
num, d = 0, 1
for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1
ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans)

Submission status: Accepted

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

res = 0
cnt = {0: 1}
now = 0
p = 1
for i in range(len(s)):
    now = (now + int(s[i]) * p) % 2019
    res += cnt.get(now, 0)
    p = (p * 10) % 2019
    cnt[now] = cnt.get(now, 0) + 1

print(res)

Submission status: Accepted

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

res = 0
cnt = {0: 1}
now = 0
p = 1
for i in range(len(s)):
    now = (now + (10 * p) * int(s[i])) % 2019
    cnt[now] = cnt.get(now, 0) + 1
    p = (p * 10) % 2019

print(sum(cnt[k] * (cnt[k] - 1) // 2 for k in cnt))

Submission status: Accepted

Solution code:
s = input()

dp = [0] * 2019
dp2 = [0] * 2019
ans = 0
for i in s:
    i = int(i)

    for j in range(2019):

        dp2[(10*j + i) % 2019] += dp[j]
    dp2[i] += 1
    dp = dp2[:]
    dp2 = [0] * 2019
    # print(dp)
    ans += dp[0]

print(ans)

Submission status: Accepted

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

ans = 0
amari = [0] * 2019
amari[0] = 1
follow = 0
POW = 1

for i in reversed(S):
  follow += int(i) * POW
  follow %= 2019
  amari[follow] += 1
  POW *= 10
  POW %= 2019
  
print(sum( i * (i-1) // 2 for i in amari ))

Submission status: Accepted

Solution code:
S = input()

modList = [0] * 2019 # あまりは0～2018の2019個

ans = 0

modList[0] = 1 # 解答でいうT(n)=0 の場合

# 最大20万回ループ、時間かかるならＤＰする？
# ↓ではTLEになった
# for i in range(len(S)):
#     m = int(S[i:]) % 2019
#     modList[m] += 1

# ↓　これでもTLEになった
# T = 0
# for i in range(1,len(S)+1):
#     # T += int(S[-i]) * 10**i
#     T += int(S[-i]) * ((10**i) % 2019)
#     modList[T % 2019] +=1

T = 0
a = 1
for s in S[::-1]:
    T = T+int(s) * a
    modList[T%2019]+=1
    a*=10
    a%=2019
#print(modList)

for j in modList:
    if j <= 1:
        continue
    else:
        ans += j*(j-1)/2

print(int(ans))

Submission status: Accepted

Solution code:
S=input()[::-1]
l=[0]*2019
a=1
d=0

# 問題はここ
# 順番に見ていって、角桁の数字のmod2019をとっている。
for s in S:
  d=d+int(s)*a
  l[d%2019]+=1
  a*=10
  a%=2019

# それぞれの組み合わせで、modの計算値が同じな組み合わせを計算している
ans=l[0]
for i in l:
  if i>=2:
    ans+=i*(i-1)//2
    
print(ans)

Submission status: Accepted

Solution code:
m=2019
l=[0]*m
a=b=0
k=1
for c in input():l[b%m]+=1;b-=int(c)*k;a+=l[b%m];k=k*202%m
print(a)

Submission status: Accepted

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

length = len(S)
dp = [0] * (length + 2)

times = 1
for x in range(1, length + 1):
    dp[x] += dp[x - 1]
    dp[x] %= 2019
    dp[x] += int(S[x - 1]) * times
    dp[x] %= 2019
    times *= 10
    times %= 2019


cnt = [0] * 2020
for x in range(length + 1):
    cnt[dp[x]] += 1

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

print(ans)

Submission status: Accepted

Solution code:
s = str(input()[::-1])
n=len(s)
mlist,m,d=[],0,1
  
for ss in s:
  m += int(ss) * d
  m %= 2019
  d *= 10
  d %= 2019
  mlist.append(m)
  
l=sorted(mlist)
l.append(2020)
pre,count,ans=0,0,0
for ll in l:
  if pre==ll:
    count+=1
  else:
    ans+=count*(count+1)//2
    pre=ll
    count=0
print(ans)

Submission status: Accepted

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

cnt = [0] * 2019
cnt[0] = 1
m = 0
d = 1
for i in S:
  m += int(i) * d
  m %= 2019
  cnt[m] += 1
  d *= 10
  d %= 2019

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

Submission status: Accepted

Solution code:
import time

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

#start = time.time()#計測始
ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
#end = time.time()#計測終
#print(f"{end-start}sec.")#計測出力

Submission status: Accepted

Solution code:
# coding: utf-8
S = input()
ans = 0
P = 2019
N = len(S)
S = S[::-1]
cnt = [0 for _ in range(P)]
cnt[0] = 1
v = 0
bai = 1
for i in range(N):
    v += int(S[i]) * bai
    v %= P
    bai *= 10
    bai %= P
    cnt[v] += 1
for i in range(P):
    ans += ((cnt[i] - 1) * cnt[i]) // 2
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
S = input()
ans = 0
P = 2019
N = len(S)
S = S[::-1]
cnt = [0 for _ in range(P)]
cnt[0] = 1
v = 0
bai = 1
for i in range(N):
    v = (v + int(S[i]) * bai) % P
    bai *= 10
    bai %= P
    cnt[v] += 1
for i in range(P):
    ans += ((cnt[i] - 1) * cnt[i]) // 2
print(ans)

Submission status: Accepted

Solution code:
s = input()[::-1]
mod_cnt = [0] * 2019
mod_cnt[0] = 1
t = 0
d = 1
for c in s:
    t += int(c) * d
    t %= 2019
    mod_cnt[t] += 1
    d *= 10
    d %= 2019
print(sum([m * (m - 1) // 2 for m in mod_cnt]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
s = input().strip()
c = 0
chk = [0]*2019
for i,si in enumerate(s[::-1]):
  c += int(si)*pow(10,i,2019)
  chk[c%2019] += 1
ans = chk[0]
for i in chk:
  ans += i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
S = input()
ans = 0
P = 2019
N = len(S)
S = S[::-1]
dp = [0 for _ in range(N)]
d = {}
for i in range(N):
    dp[i] = int(S[i]) * pow(10, i, P) % P
for i in range(N-1):
    dp[i+1] += dp[i]
    dp[i+1] %= P
dp[-1] %= P
for i in range(N):
    if dp[i] not in d:
        if dp[i] == 0:
            ans += 1
        d[dp[i]] = 1
    else:
        if dp[i] == 0:
            ans += 1
        ans += d[dp[i]]
        d[dp[i]] += 1
print(ans)

Submission status: Accepted

Solution code:
s = input()
sr = s[::-1]
mod = [0]*2019
mod[0] += 1
T = 0
d = 1 
for s in sr:
  T = T + int(s) * d
  T %= 2019
  mod[T] += 1
  d = (d * 10) % 2019
  
res = [m*(m-1)//2 for m in mod]
print(sum(res))

Submission status: Accepted

Solution code:
S = list(map(int,input()))[::-1] #逆順

counter = 0
amari = [0]*2019
amari[0] = 1

s,d = 0,1

for i in S:
    s += i *d
    amari[s%2019] += 1
    d *= 10
    d %= 2019


for i in range(2019):
    counter += amari[i] * (amari[i]-1) / 2


print(int(counter))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

S=sys.stdin.readline().strip()
S=S[::-1]
#Lの先頭の0を入れるのは、何も数を選択しない状態はmod2019がゼロになるの意味
#19行目でx=0の際に、ans+=C[x]で1足されることになるので都合が良い
L=[0] 
val=0
for i,x in enumerate(S):
    val+=pow(10,i,2019)*int(x)
    L.append(val%2019)

C=defaultdict(lambda: 0)    #mod2019の値の出現個数を記録
ans=0
for x in L:
    ans+=C[x]   #自分とmod2019の結果が同じ値となる出現個数をansに足す
    C[x]+=1     #自分のmod2019の値を出現個数に+1カウント
print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N=sys.stdin.readline().strip()
N=N[::-1]
#Lの先頭の0を入れるのは、何も数を選択しない状態はmod2019がゼロになるの意味
#19行目でx=0の際に、ans+=C[x]で1足されることになるので都合が良い
L=[0] 
val=0
for i,x in enumerate(N):
    val+=pow(10,i,2019)*int(x)
    L.append(val%2019)

C=defaultdict(lambda: 0)    #mod2019の値の出現個数を記録
ans=0
for x in L:
    ans+=C[x]   #自分とmod2019の結果が同じ値となる出現個数をansに足す
    C[x]+=1     #自分のmod2019の値を出現個数に+1カウント
print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N=sys.stdin.readline().strip()
N=N[::-1]
#Lの先頭の0を入れるのは、何も数を選択しない状態はmod2019がゼロになるの意味
#19行目でx=0の際に、ans+=C[x]で1足されることになるので都合が良い
L=[0] 
val=0
for i,x in enumerate(N):
    val+=pow(10,i,2019)*int(x)
    L.append(val%2019)

C=defaultdict(lambda: 0)    #mod2019の出現個数を記録
ans=0
for x in L:
    ans+=C[x]   #自分とmod2019の結果が同じ値となる個数をansに足す
    C[x]+=1     #自分のmod2019の値を出現回数に+1カウント
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:
def main():
    s = input()[::-1]

    sum_of_digits = 0

    cnts = [0] * 2019

    cnts[0] = 1

    d = 1

    for i in range(len(s)):
        sum_of_digits += int(s[i]) * d
        d *= 10
        d %= 2019
        sum_of_digits %= 2019
        cnts[sum_of_digits] += 1


    ans = 0

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

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
def main():
    mod=2019
    S=input().strip()
    l=len(S)
    M=[0]*(l+1)
    p=1
    for i in range(1,l+1):
        x=int(S[l-i])
        M[i]=(M[i-1]+x*p)%mod
        p*=10
        p%=mod
    print(sum(m*(m-1)//2 for m in Counter(M).values()))
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
s=str(input())
n=len(s)
m=2019
d=[0]
for i in range(n):
    d.append((d[-1]+int(s[n-i-1])*pow(10,i,m))%m)
p=defaultdict(int)
ans=0
for i in d:
    ans+=p[i]
    p[i]+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
def main():
    mod=2019
    S=input().strip()
    l=len(S)
    M=[0]*(l+1)
    p=1
    for i in range(1,l+1):
        x=int(S[l-i])
        M[i]=(M[i-1]+x*p)%mod
        p*=10
        p%=mod
    C=Counter(M)
    ans=0
    for m in C.values():
        ans+=m*(m-1)//2
    print(ans)
    
if __name__=='__main__':
    main()