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 = input()
n = len(s)
p = 2019
 
 
 
digit_rm = [0 for _ in range(n)]
for i in range(n):
	digit_rm[i] = (int(s[n-1-i]) * pow(10, i, p) ) % p
 
remain = [0 for _ in range(n)]
for i in range(n):
	if i == 0:
		remain[i] = digit_rm[i]
	else:
		remain[i] = (remain[i-1] + digit_rm[i]) % p
 
pcnt = [0 for _ in range(p)]
 
for i in remain:
	pcnt[i] += 1
 
if 10 % p == 0:
	ans = 0
	for i in range(n):
		if int(s[n-1-i]) % p == 0:
			ans += n - i
	print(ans)
else:
	ans = pcnt[0]
	for num in pcnt:
		if num != 0:
			ans += num * (num - 1) // 2
 
	print(ans)

Submission status: Accepted

Solution code:
import collections
s = input()
mods = [0]
crt = 0
ans = 0
if len(s) <= 4:
    print(0)
    exit()
# for i in range(len(s)):
#     crt = crt*10+int(s[i])
#     crt %= 2019
#     mods.append(crt)
# print(mods)
for i in range(len(s)-1,-1,-1):
    crt = crt+int(s[i])*pow(10, (len(s)-i-1), 2019)
    crt %= 2019
    mods.append(crt)
#print(mods)
mods_count = collections.Counter(mods)
mods_count = list(mods_count.values())
for i in range(len(mods_count)):
    tar = mods_count[i]
    ans += tar*(tar-1)//2
print(ans)

Submission status: Accepted

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

ak10k = [(pow(10,n-k-1,m)*int(s[k]))%m for k in range(0,n)]+[0]

ruiseki=[0]*n
ruiseki[0]=ak10k[0]
for i in range(1,n):
    ruiseki[i]=(ruiseki[i-1]+ak10k[i])%2019

from collections import Counter
c = Counter(ruiseki)

ans=sum(cc*(cc-1)//2 for cc in c.values()) + c[0]

print(ans)

Submission status: Accepted

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

S = input()

P = 2019
N = len(S)

def solve_2(S):
    ind = (i for i, x in enumerate(S, 1) if x % 2 == 0)
    return sum(ind)

def solve_5(S):
    ind = (i for i, x in enumerate(S, 1) if x % 5 == 0)
    return sum(ind)

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


print(solve(S,P))

Submission status: Accepted

Solution code:
def main():
    import sys

    S = list(input())
    N = len(S)

    # c = 0
    # for i in range(0, N-3):
    #     for j in range(i+4, N+1):
    #         num = int(''.join(S[i:j]))
    #         if num % 2019 == 0:
    #             c += 1
    #             print(num)
    # print(c)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import fractions
import collections
import itertools
from collections import deque
d=collections.deque()
S=list(input())
N=len(S)
cnt=0

amari=[0]*(N+1)
num=0
for i in range(N):
    d.append(int(S[i]))
#print(d)
for i in range(N):
    n=d.pop()
    num=(num+pow(10,i,2019)*n)%2019
    amari[i+1]=num
#print(amari)
#c=collections.Counter(amari)
#values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
amari.sort()
#for i in range(len(key)):
#    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#xprint(l)
buf=0
#print(amari)
c=collections.Counter(amari)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
#for i in range(len(key)):
#    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#xprint(l)
for i in range(len(values)):
    cnt=cnt+(values[i]*(values[i]-1))//2
print(cnt)

Submission status: Accepted

Solution code:
s = list(map(int, list(input())))[::-1]

sum = 0
cnt = [0] * 2019
cnt[0] = 1
n = len(s)
#print(s)
for i in range(n):
    d = s[i] * pow(10, i, 2019)
    sum = (sum + d) % 2019
    cnt[sum] += 1
ans = 0
for i in range(2019):
    ans += cnt[i] * (cnt[i]-1)//2

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

mod = 2019
inv10 = 202
S = list(map(int, input()[:-1]))
N = len(S)
H = []
v = 0
d = 1
cusum = 0
M = [0] * mod
M[0] += 1
ans = 0
for c in S:
    h = c*d % mod
    d = d * inv10 % mod
    cusum = (cusum+h) % mod
    ans += M[cusum]
    M[cusum] += 1
print(ans)

Submission status: Accepted

Solution code:
S = input()

ten = [0] * (len(S) + 1)
ten[1] = 1
for i in range(1, len(S)):# ten の前計算
    ten[i + 1] = ten[i] * 10 % 2019

accum = [0] * (len(S) + 1)
for i, v in enumerate(S[::-1]):
    accum[i + 1] = (int(v) * ten[i + 1] + accum[i]) % 2019

import numpy as np
bc = np.bincount(accum)
res = (bc * (bc - 1) // 2).sum()
print(res)

Submission status: Accepted

Solution code:
import collections

s=input()
l=len(s)
cnt=collections.defaultdict(int)
cnt[0]+=1
tmp=0
for i in range(l):
  tmp+=int(s[l-1-i])*pow(10,i,2019)
  tmp%=2019
  cnt[tmp]+=1
ans=0
for key in cnt.keys():
  ans+=(cnt[key]*(cnt[key]-1))//2
print(ans)

Submission status: Accepted

Solution code:
mod_673 = [1] * 672
for i in range(1,672):
    mod_673[i] = (mod_673[i -1] * 10) % 673

S = input()
S = S[::-1]
A = [0] * (len(S) + 1)
B = [0] * (len(S) + 1)
x = 0
Ans = [[0] * 3 for i in range(673)]
for i in range(1, len(S) + 1):
    A[i] = (A[i - 1] + int(S[i - 1]) * mod_673[(i - 1) % 672]) % 673
    B[i] = (B[i - 1] + int(S[i - 1])) % 3

for i in range(len(S) + 1):
    Ans[A[i]][B[i]] += 1

for i in range(673):
    for j in range(3):
        y = Ans[i][j]
        x += y * (y - 1) // 2

print(x)

Submission status: Accepted

Solution code:
S=input()

from collections import defaultdict
d=defaultdict(int)

n=len(S)
b=0
for i in range(n):
    a=int(S[n-i-1])
    b+=a*pow(10,i,2019)
    b%=2019
    d[b]+=1

ans=0

for k,v in d.items():
    if k==0:
        ans+=v
    ans+=v*(v-1)//2

print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache



S=input()
count=[0 for i in range(2019)]
length=len(S)
#S=int(S)
S=S+'0'
S=S[::-1]
_S=0

base=1
for i,s in enumerate(S):
    _S=base*int(s)+_S
    count[_S%2019]+=1
    base*=10
    base=base%2019
    _S=_S%2019



retval=0
for key in range(2019):
    retval+=count[key]*(count[key]-1)//2


print(retval)

Submission status: Accepted

Solution code:

S = list(map(int, list(input())))
N = len(S)
P = 673

cnt = [[0,0,0]  for i in range(P)]
cnt[0][0] = 1
rem1 = 0
rem2 = 0
ans = 0


for i in range(N):
    rem1 = (int(S[-i - 1]) * pow(10, i, P) + rem1) % P
    rem2 = (int(S[-i - 1]) * pow(10, i, 3) + rem2) % 3
    ans += cnt[rem1][rem2]
    cnt[rem1][rem2] += 1

print(ans)

Submission status: Accepted

Solution code:
a = input()

def int2019(s):
    s = [int(i) for i in s]
    modTable = [0] * 2019
    total = 0
    for i in range(len(s)):
        nextTable = [0] * 2019
        for j in range(2019):
            nextTable[(j * 10 + (s[i])) % 2019] = modTable[j]

        nextTable[(s[i]) % 2019] += 1
        total += nextTable[0]
        modTable = nextTable

    return total


print(int2019(a))

Submission status: Accepted

Solution code:
from collections import defaultdict
s = input()
n, p = len(s), 2019

dd = defaultdict(int)
dd[0] = 1
prev = 0

for i in range(n-1, -1, -1):
    d = int(s[i]) * pow(10, n-i, p)
    prev = (prev + d) % p
    dd[prev] += 1

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

Submission status: Accepted

Solution code:
p = 2019 
D = input()
n=(len(D))
out = 0


if 10 % p == 0:
    for i in range(n):
        if int(D[i]) % p == 0:
            out += i + 1
else:
    mod = 0
    count = [0] * p
    ten = 1
    count[mod] += 1
    for i in range(n):
        mod = (mod + int(D[n-i-1]) * ten) % p
        ten = ten * 10 % p
        count[mod] += 1
    for c in count:
        out += (c * (c - 1)) // 2
print(out)

Submission status: Accepted

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

m=[0]*2019
m[0]=1
ans=0

sm=0
d=1
for i in range(N):
    sm=(sm+S[N-1-i]*d)%2019
    m[sm] += 1
    d=(d*10)%2019

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

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
def main():
    S = list(map(int, input()))
    S = S[::-1]
    T = [0] * len(S)
    P = 2019
    T[0] = S[0] % P
    power = 1
    for i in range(1, len(S)):
        power *= 10
        power %= P
        T[i] = T[i-1] + power * S[i]
        T[i] %= P
    counter = Counter(T)
    ans = sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#MLE注意！ not は使わず !=
#0や1のケースに注意

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n = input().rstrip()
    n = n[::-1]
    res = [0]*2019
    res[0] += 1
    b = 1
    c = 0
    for i in range(len(n)):
        a = int(n[i])
        c += a*b
        c %= 2019
        res[c] += 1
        b = b*10%2019
    ans = 0
    for i in res:
        if i>=2:
            ans += i*(i-1)//2
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S=input()
p=2019
h=0
d=1
t=0
c=[0]*p
c[0]=1
for s in reversed(S):
  m=int(s)*d%p
  h=(h+m)%p
  t+=c[h]
  c[h]+=1
  d=d*10%p
print(t)

Submission status: Accepted

Solution code:
# for i in range(10):
# 	print( 10 ** i % 2019)



s = list(map(int, list(input())))
n = len(s)
MODULO = 2019

power = 1
prefix_ = [0 for _ in range(n+1)]
for i in range(n-1, -1, -1):
	prefix_[i] = (prefix_[i+1] + power*s[i]) % MODULO
	power *= 10
	power %= MODULO

seen = {}
ans = 0
for item in prefix_:
	ans += seen.get(item, 0)
	seen[item] = seen.get(item, 0) + 1

# print(s)
# print("prefix_", prefix_)
# print("unique", len(set(prefix_)))
# print("all", len(prefix_))
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
 
 
def solve2(s):
    ans = 0
    for i, c in enumerate(s):
        if c in '02468':
            ans += i + 1
    return ans
 
 
def solve5(s):
    ans = 0
    for i, c in enumerate(s):
        if c in '05':
            ans += i + 1
    return ans
 
 
def solve_other(s, p):
    reminders = defaultdict(lambda: 0)
    tmp = 0
    mul = 1
    for c in s[::-1]:
        c = int(c)
        tmp = (tmp + c * mul) % p
        mul = mul * 10 % p
        reminders[tmp] += 1
    reminders[0] += 1
    ans = 0
    for r, cnt in reminders.items():
        ans += cnt * (cnt - 1) // 2
    return ans
 
 

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


if p == 2:
    print(solve2(s))
elif p == 5:
    print(solve5(s))
else:
    print(solve_other(s, p))

Submission status: Accepted

Solution code:
S = list(str(input()))
S = [int(s) for s in S]
n = len(S)

S.reverse()

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

cum1 = [-1]*(n+1)
cum1[0] = 0
for i in range(n):
    temp = cum1[i]+S[i]*power(10, i, 673)
    cum1[i+1] = temp%673
#print(cum1)

cum2 = [-1]*(n+1)
cum2[0] = 0
for i in range(n):
    temp = cum2[i]+S[i]*power(10, i, 3)
    cum2[i+1] = temp%3
#print(cum2)

d = {}
ans = 0
for i in range(n+1):
    c1 = cum1[i]
    c2 = cum2[i]
    if (c1, c2) in d:
        ans += d[(c1, c2)]
        d[(c1, c2)] += 1
    else:
        d[(c1, c2)] = 1
print(ans)

Submission status: Accepted

Solution code:
import collections
p = 2019
s=input()
n=len(s)
arr=[int(s[i]) for i in range(len(s))] #文字列の各文字をそれぞれ数字に変換しておく
if p==2 or p==5: #P=2,5のときは10を割り切るので連続部分列の右端のみを見ればよい
 ans=0
 for i in range(n):
   if arr[i]%p==0:
     ans+=i+1
 print(ans)
else: #Pが2でも5でもないとき
 dic=collections.defaultdict(int)
 tmp=0
 for i in range(n-1,-1,-1): #右端の要素を右端とする連続部分列のあまりを順に求める
   tmp+=arr[i]*pow(10,n-1-i,p)
   tmp%=p
   dic[tmp]+=1
 ans=0
 rem=0 #調べるあまりの値(初期値は0)
 for i in range(n-1,-1,-1):
   ans+=dic[rem]
   rem+=arr[i]*pow(10,n-1-i,p) #調べるあまりの値に(i番目の要素)*10^(n-1-i)を加える
   rem%=p
   dic[rem]-=1 #右端の要素が右端、i番目の要素が左端となる連続部分列のあまりの個数を1減らす
 print(ans)

Submission status: Accepted

Solution code:
S = input()
N = len(S)
P = 2019
num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1
print(ans)

Submission status: Accepted

Solution code:
p = 2019
s = [int(i) for i in input()]
p_cnt = 0
 
s = s[::-1]
div_dic = dict(zip(range(p), [0] * p))
tmp = 0

for i in range(len(s)):
    tmp += s[i] * pow(10, i, p)
    tmp %= p
    div_dic[tmp] += 1

for v in div_dic.values():
    p_cnt += v * (v - 1)
p_cnt //= 2
p_cnt += div_dic.get(0)
 
print(p_cnt)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
S = [int(i) for i in input()]

def solve(S):
    n = len(S)
    cum = [0]*(n+1)
    mods = [0]*n
    mods[0] = 1
    for i in range(1,n):
        mods[i] = mods[i-1]*10%2019
    for i in range(n):
        cum[i+1] = (cum[i]+S[n-1-i]*mods[i])%2019
    c = [0]*2019
    for i in range(n+1):
        c[cum[i]] += 1
    ans = 0
    for v in c:
        ans += v*(v-1)//2
    return ans
print(solve(S))

Submission status: Accepted

Solution code:
S=input()
a=0
b=[0]*2019
No=[None]*2019
for i in S:
    l=No.copy()
    k=int(i)
    for j in range(2019):
        l[(j*10+k)%2019]=b[j]
    l[k]+=1
    a+=l[0]
    b=l
print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
S=list(map(int,input()))
N=len(S)
P=2019
num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + S[i] * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1

print(ans)

Submission status: Accepted

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

cur_mod = 0
ten_mod = 1
mod[0] = 1
for c in s[::-1]:
  cur_mod = (cur_mod + int(c) * ten_mod) % 2019
  ten_mod = (ten_mod * 10) % 2019
  mod[cur_mod] += 1

count = 0
for m in mod:
  count += m * (m - 1) // 2

print(count)

Submission status: Accepted

Solution code:
p = 2019
s = list(map(int, list(input())))[::-1]

sum = 0
cnt = [0] * p
cnt[0] = 1
n = len(s)
for i in range(n):
    d = s[i] * pow(10, i, p)
    sum = (sum + d) % p
    cnt[sum] += 1

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


print(ans)

Submission status: Accepted

Solution code:
import sys

M = 2019
S = sys.stdin.readline().rstrip()
N = len(S)

dmod = [0] * (N + 1)
amod = [0] * (N + 1)
tenmod = 1
prev_amod = 0
mcnt = [0] * 2019
ans = 0
for i in range(N, -1, -1):
    d = ord(S[i]) - ord("0") if i < N else 0
    dmod[i] = d * tenmod % M
    amod[i] = (dmod[i] + prev_amod) % M
    ans += mcnt[amod[i]]
    mcnt[amod[i]] += 1
    tenmod = tenmod * 10 % M
    prev_amod = amod[i]
print(ans)

Submission status: Accepted

Solution code:
s = map(int,raw_input())
dp = [0] * 2019
count = 0
for j in range(len(s)):
    ndp = [0] * 2019
    ndp[s[j]] += 1
    for k in range(len(dp)):ndp[(10*k + s[j]) % 2019] += dp[k]
    count += ndp[0]
    dp = ndp

print count

Submission status: Accepted

Solution code:
import collections
s = map(int,raw_input())

dp = [0] * 2019
count = 0
for j in range(len(s)):
    ndp = [0] * 2019
    ndp[s[j]] += 1
    for k in range(len(dp)):
        ndp[(10*k + s[j]) % 2019] += dp[k]
    count += ndp[0]
    dp = ndp[::]

print count

Submission status: Accepted

Solution code:
# x^n % mod
def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

  return (x * K) % mod


MOD = 2019
array = [0] * (MOD+1)

array[0] = 1

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

n = 0
for i in range(len(s)):
  n += int(s[i]) * pow(10,i,MOD)
  n %= MOD
  array[n] += 1
  
ans = 0
for i in range(len(array)):
  if array[i] == 1 or array[i] == 0:
    continue
  
  tmp = array[i] * (array[i]-1) // 2
  ans += tmp
  
print(ans)

Submission status: Accepted

Solution code:


s = input()
n = len(s) 

rs = [1]*n
for i in range(1,n):
  rs[i] = rs[i-1]*10 %2019
  
ls = [0]*2019
ls[0]+=1

r = 0
for i in range(n-1,-1,-1):
  r += int(s[i]) * (rs[n-i-1])
  r %= 2019
  ls[r] += 1

ans = 0
for a in ls:
  ans += a*(a-1)//2
print(ans)

Submission status: Accepted

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

mod = 0
count = [0]* P
ten = 1
count[mod] += 1
for i in range(N):
    mod = (mod + int(S[N-i-1]) * ten) % P
    ten = ten * 10 % P
    count[mod] += 1

res = 0
for c in count:
    res += (c * (c - 1)) // 2

print(res)

Submission status: Accepted

Solution code:
S = input()
N = len(S)
P = 2019
 
res = 0
mp = [0]*P
mp[0] = 1
cur = 0
p10 = 1
for c in S[::-1]:
    cur = (cur + int(c)*p10) % P
    res += mp[cur]
    mp[cur] += 1
    p10 *= 10
    p10 %= P
 
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def power_func(a, b, 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

S = input()
ansl = [0]*2019
temp = 0
for i in range(len(S)):
    temp = (temp+int(S[-i-1])*power_func(10,i,2019))%2019
    ansl[temp]+=1
ans = (ansl[0]+1)*ansl[0]/2

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

print(int(ans))

Submission status: Accepted

Solution code:
s = list(input())
n = len(s)
mod = 2019
cnt = [0 for _ in range(mod)]
cnt[0] = 1
r = 0
rs = []
for i in range(n - 1, -1, -1):
    r += int(s[i]) * pow(10, n - 1 - i, mod)
    r %= mod
    cnt[r] += 1
ans = sum([cnt[i] * (cnt[i] - 1) // 2 for i in range(mod)])
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
s = input()
n=len(s)
res = [0] * (len(s)+1)
i = 1
res10p = 1
for c in reversed(s):
    res[i] = (res[i-1] + res10p*int(c))%2019
    i = i+1
    res10p = res10p*10%2019

dic = Counter(res)
cnt = 0
for v in dic.values():
    if v >= 2:
#        print(v)
        cnt += v * (v-1) // 2
print(cnt)

Submission status: Accepted

Solution code:
S = input()
N = len(S)
S_ = []
P = 2019
num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1

print(ans)

Submission status: Accepted

Solution code:
k=2019
s=map(int,list(input()))
ans=0

inv10=202
inv=10
total=0
S=[0]*k
S[0]=1
for i,p in enumerate(s):
    inv*=inv10
    inv%=k
    total+=p*inv
    total%=k
    ans+=S[total]
    S[total]+=1
"""
for i,s in enumerate(S):
    if s>0:
        print(i,s)
"""
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

S = input()
N = len(S)
q = deque(S)

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

S = S[::-1]
m = [0]
for i in range(N):
    c = int(S[i])
    n = (c * mod10[i] + m[i]) % 2019
    m.append(n)


modCnt = [0] * 2020

for num in m:
    modCnt[num] += 1

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

print(ans)

Submission status: Accepted

Solution code:
s=input()
n=len(s)
mod=[0]*(n+1)
s=s[::-1]
for i in range(n):
	mod[i+1]=(mod[i]+pow(10,i,2019)*int(s[i])%2019)%2019
mod.sort()
cnt=1
ans=0
for i in range(n):
	if mod[i]==mod[i+1]:
		cnt+=1
	else:
		ans+=cnt*(cnt-1)//2
		cnt=1
ans+=cnt*(cnt-1)//2
print(ans)

Submission status: Accepted

Solution code:
import math
s = input()
ls = [(ord(s[len(s) - i - 1]) - ord('0')) for i in range(len(s))]
cnt = [0 for _ in range(2019)]
cur = 0
ans = 0
power = 1
cnt[0] = 1
for i in ls:
    cur = (cur + power * i) % 2019
    ans = ans + cnt[cur]
    cnt[cur] = cnt[cur] + 1
    power = (power * 10) % 2019

print(ans)

Submission status: Accepted

Solution code:
S = list(input())

for i in range(len(S)):
    S[i] = int(S[i])

A = [S[len(S)-1]]
mod = 2019
for i in range(1,len(S)):
    A.append((S[len(S)-i-1]*pow(10,i,mod)+A[i-1]) % mod)

from collections import  Counter

c = Counter(A)

ans = c[0]

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

print(ans)

Submission status: Accepted

Solution code:
import sys, copy, math, heapq, bisect
from itertools import accumulate
from collections import deque, defaultdict, Counter
sys.setrecursionlimit(500000)

S = list(input())[::-1]
N = len(S)
D = [1]
for i in range(N):
    D.append(D[-1]*10%2019)
M = [(int(S[i])*D[i])%2019 for i in range(N)]
SS = [M[0]]
for i in range(1,N):
    SS.append((SS[-1]+M[i])%2019)
count = [0]*2019
for i in range(N):
    count[SS[i]] += 1

ans = 0
for c in range(len(count)):
    if c==0:
        ans += count[c]
    ans += (count[c] * (count[c] - 1)) // 2

print(ans)

Submission status: Accepted

Solution code:
import collections

S = list(map(int, list(input())))[::-1]
S = [(S[i] * pow(10, i, 2019)) % 2019 for i in range(len(S))]
for i in range(1, len(S)):
    S[i] = (S[i] + S[i-1]) % 2019 

C = collections.Counter(S)
ans = 0
for x in C.keys():
    if x == 0:
        ans += C[0] + C[0] * (C[0] - 1) // 2
    else:
        ans += C[x] * (C[x] - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
def modpow(d, b, p, mod=2019):
    ret = 1
    while p > 0:
        if p % 2 == 1:
            ret = ret * b % mod
        b = b * b % mod
        p //= 2
    return (d * ret) % mod


S = input()
C = [0]
for i in range(len(S)):
    C.append((C[-1] + modpow(int(S[-(i + 1)]), 10, i)) % 2019)
Cd = {}
for c in C[1:]:
    Cd[c] = Cd.get(c, 0) + 1
print(Cd.get(0, 0) + sum([v * (v - 1) // 2 for v in Cd.values()]))

Submission status: Accepted

Solution code:
S = list(map(int, input()))
n = len(S)
S = S[::-1]
#print(S)
Smod = [S[i] * pow(10, i, 2019) %2019 for i in range(n)]
Scum = [0]*n
Scum[0] = Smod[0]
#print(Smod)

for i in range(1, n):
  Scum[i] = (Scum[i-1] + Smod[i])%2019
#print(Scum)
from collections import Counter
c = Counter(Scum)
#print(c)
ans = 0
for k in c:
  if k!=0 or k==0:
    ans += c[k]*(c[k] - 1)//2
    #print(k, c[k], ans)
    
for i in range(n):
  if Scum[i]==0:
    ans += 1
    #print(ans)
    
print(ans)

Submission status: Accepted

Solution code:
MOD=2019

S=list(int(s) for s in input()[::-1])
T=[S[0]]
for i in range(1,len(S)):
    T.append(T[-1]+S[i]*pow(10,i,MOD))
cnt={}
for i in range(2019):
    cnt[i]=0
for t in T:
    cnt[t%MOD]+=1
ans=0
for i in range(2019):
    c=cnt[i]
    if c>=2:
        ans+=c*(c-1)//2
ans+=cnt[0]
print(ans)

Submission status: Accepted

Solution code:
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
#%%code
def resolve():
    S=input()
    n=len(S)
    
    S2=[0]*n
    digit=0
    for i in range(n-1,-1,-1):
        s=int(S[i])
        S2[i]=(s*pow(10,digit,2019))%2019
        digit+=1
    #print(S2)

    S3=[0]*n;subsum=0
    for j,s2 in enumerate(S2):
        subsum+=s2;subsum%=2019;S3[j]=subsum
    S3.append(0)
    #print(S3)

    from collections import Counter
    c=Counter(S3).values()
    ans=0
    for k in c:
        if k>1:
            ans+=(k*(k-1))//2
    print(ans)
#%%submit!
resolve()

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import Counter

S = list(input())
S = list(map(int, S))
s = [0] * len(S)
mod = 2019
s[-1] = S[-1]
d = 1
for i in range(len(s) - 2, -1, -1):
    d = (d * 10) % mod
    s[i] = (S[i] * d) % mod

acc = list(accumulate(s[::-1]))[::-1] + [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:
S_str=str(input())
S=int(S_str[-1])
N=len(S_str)

mod=[0]*2019
mod[0]=1
now=S%2019
mod[now]+=1

for i in range(N-1)[::-1]:
    #print(i+1,S,S%2019)
    next=pow(10,N-1-i,2019)
    next=(next*int(S_str[i]))%2019
    now=(now+next)%2019
    mod[now]+=1

    

def culc(x):
    return x*(x-1)//2


ans=0
for j in range(len(mod)):
    ans+=culc(mod[j])

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

S = input()
N = len(S)
MOD = 2019

rems = [0] * N
rems[-1] = int(S[-1]) % MOD
last = int(S[-1])
tens = 1
for i in range(N - 1):
    tens = tens * 10 % MOD
    last = int(S[N - 2 - i]) * tens + last
    rems[N - 2 - i] = last % MOD
pos = defaultdict(int)
for i in range(N):
    r = rems[i]
    pos[r] += 1
ans = pos[0]
for i in range(MOD):
    ans += pos[i] * (pos[i] - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
def run():
    S = input()
    mods = [[] for _ in range(2019)]
    mods[0].append(0)

    tmp = 0
    tmp10 = 1
    for i in range(1, len(S)+1):
        if i == 1:
            tmp10 = 1
        else:
            tmp10 = (tmp10 * 10) % 2019
        tmp = (tmp10* int(S[-i]) + tmp)% 2019
        mods[tmp].append(i)

    count = 0
    for ns in mods:
        l = len(ns)
        count += l * (l-1) // 2
    print(count)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
def pow_with_mod(x, n, m):
    if n == 0:
        return 1

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

    return (K * x) % m

def main():
    import sys
    S=sys.stdin.readline().strip()
    N=len(S)
    L=[0]*2019
    now=0
    for i in range(N):
        now+=int(S[-i-1])*pow_with_mod(10, i, 2019)
        now%=2019
        L[now]+=1  
    print(L[0]+sum([x*(x-1)//2 for x in L]))
main()

Submission status: Accepted

Solution code:
S = input()
l = len(S)
d = {}

m = 0

ans = 0
for i in range(l):
    m  = (m + int(S[l-1-i]) * pow(10,i,2019)) % 2019
    if m in d:
        d[m] += 1
    else:
        d[m] = 1

for k, v in d.items():
    if v >= 2:
        ans += int(v * (v-1)/2)
    if k == 0:
        ans += v
print(ans)

Submission status: Accepted

Solution code:
p = 2019
s = list(map(int, list(input())))[::-1]
n = len(str(s))

sum = 0
cnt = [0] * p
cnt[0] = 1
n = len(s)
for i in range(n):
    d = s[i] * pow(10, i, p)
    sum = (sum + d) % p
    cnt[sum] += 1

ans = 0
if p in [2, 5]:
    if p == 2:
        ok_list = [0, 2, 4, 6, 8]
    if p == 5:
        ok_list = [0, 5]

    for i in range(n):
        d = s[i]
        if d in ok_list:
            ans += n - i
           
else:
    for i in range(p):
        ans += cnt[i] * (cnt[i]-1) // 2


print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import defaultdict

s = ns()
n = len(s)
m = 1
c = [0] * (n + 1)

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

ans = 0
dic = defaultdict(int)
for i in range(n, -1, -1):
    ans += dic[c[i]]
    dic[c[i]] += 1

print(ans)

Submission status: Accepted

Solution code:
S=list(input())
S.reverse()
N=len(S)
R=[0]*N
R10=[0]*N
m=2019
K=0

R10[0]=1
R[0]=int(S[0])%m
for i in range(1,N):
    R10[i]=(R10[i-1]*10)%m
    R[i]=(R[i-1]+int(S[i])*R10[i])%m
d={}
for i in range(2019):
    d[i]=0

for i in range(N):
    d[R[i]]+=1
ans=0
for i in range(2019):
    if i == 0:
        ans += d[i]
        ans +=d[i]*(d[i]-1)//2
    else:
        ans +=d[i]*(d[i]-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
mods = Counter([(0, 0)])
ten_i_mod3 = 1
temp3 = 0
ten_i_mod673 = 1
temp673 = 0
for digit in reversed(input()):
    digit = int(digit)
    temp3 += digit * ten_i_mod3
    temp673 += digit * ten_i_mod673
    temp3 %= 3
    temp673 %= 673
    mods[(temp3, temp673)] += 1
    ten_i_mod3 *= 10
    ten_i_mod673 *= 10
    ten_i_mod3 %= 3
    ten_i_mod673 %= 673
ans = 0
for key in mods:
    n = mods[key]
    ans += n * (n - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
s=input()

l=[1]

for i in range(2018):
    l.append(0)

ss=0
for i in range(len(s)):#ss=s[len(s)-i-1::]
    ss=(int(s[len(s)-i-1])*pow(10,i,2019)+ss)%2019
    l[ss]+=1
n=0
for i in range(2019):
    n+=l[i]*(l[i]-1)//2

print(int(n))

Submission status: Accepted

Solution code:
from collections import Counter


S = input()
N = len(S)

L = [0] * (N + 1)
s = 0
for i in range(N):
    s += int(S[N - 1 - i]) * pow(10, i, 2019)
    L[i + 1] = (s % 2019)

C = Counter(L)
cnt = 0
for key in list(C.keys()):
    k = C[key]
    cnt += (k * (k - 1)) // 2

print(cnt)

Submission status: Accepted

Solution code:
S=input()
P=2019

answer=0
mod_table=[0]*P
mod_table[0]=1
revS=S[::-1]
  
modp=0
mod10=1
for i in range(len(S)):
  mod10=(mod10*10)%P
  #modp=(10*modp+int(revS[i]))%P
  modp=(modp+mod10*int(revS[i]))%P
  mod_table[modp]+=1
    
#print(mod_table)
for i in range(P):
  answer+=mod_table[i]*(mod_table[i]-1)//2
  
print(answer)

Submission status: Accepted

Solution code:
S = input()
mod = [0] * 2019
res = 0
for c in S:
    m = int(c)
    new_mod = [0] * 2019
    for i, n in enumerate(mod):
        new_mod[(i*10 + m) % 2019] = n
    new_mod[m] += 1
    mod = new_mod
    res += mod[0]
print(res)

Submission status: Accepted

Solution code:
S = list(input())

MOD = 2019
S.reverse()
cnt = 1
temp = 0
ans = [0]*2019
for i in S:
    temp += int(i)*cnt % MOD
    temp %= MOD
    ans[temp] += 1
    cnt *= 10
    cnt %= MOD

ans[0] += 1

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