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:
a = input()
n = len(a)

s = 0 # s[0]の余り
c = [0] * 2019 # c[i] = 余り i の個数
c[s] += 1
d = 1 # 10**i mod 2019

for i in range(n):
    s = (s + d * int(a[n-i-1])) % 2019 # s[i+1]の余り
    d = d * 10 % 2019 #10**(i+1) mod 2019
    c[s] += 1

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

S = input().rstrip()
n = len(S)
l = [0]*2019
d = 10

t = int(S[n-1])
l[t%2019] += 1

l[0] += 1

for i in range(n-2, -1, -1):
    t += int(S[i])*d%2019
    l[t%2019] += 1 
    d *= 10
    d %= 2019

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.readline
    s = list(input()[:-1])[::-1]
    N = len(s)
    p10 = [1]
    tmp = 1
    for _ in range(N - 1):
        tmp = tmp * 10 % 2019
        p10.append(tmp)
    mod = []
    tmp = 0
    for num, p in zip(s, p10):
        tmp = (tmp + int(num) * p) % 2019
        mod.append(tmp)

    mod.sort()
    mod.insert(0, 0)

    ans = 0
    count = 1
    for i in range(1, N + 1):
        if mod[i] == mod[i - 1]:
            count += 1
        else:
            ans += count * (count - 1) // 2
            count = 1
    ans += count * (count - 1) // 2
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
s=input()
n=len(s)
a=0
t=1
d=[1]+[0]*2018

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

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

print(ans)

Submission status: Accepted

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

lst = []
num = 1
pow10 = [1]
for _ in range(len(s) - 1):
    num = num * 10 % 2019
    pow10.append(num)

num = 0
for s_num, p10 in zip(s, pow10):
    num = (num + (int(s_num) * p10)) % 2019
    lst.append(num)
lst.sort()

total = 0
cnt = 1
before = 0
for num in lst:
    if before == num:
        cnt += 1
    else:
        total += cnt * (cnt - 1) // 2
        cnt = 1
    before = num
total += cnt * (cnt - 1) // 2
print(total)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    S = input().rstrip()
    counter = defaultdict(int)
    mod = 2019
    counter[0] += 1
    num = 0
    d = 1
    for c in S[::-1]:
        num += int(c) * d
        num %= mod
        counter[num] += 1
        d *= 10
        d %= mod
    ans = 0
    for v in counter.values():
        ans += (v * (v-1)) // 2
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()
A = [0 for i in range(2019)]
x = 0
q = 1
for i in range(len(S)):
    p = i + 1
    a = (int(S[-p]))
    b = a*q%2019
    x = (x+b) % 2019
    A[x] += 1
    q = q*10%2019
ans = A[0]
for i in range(2019):
    ans += A[i]*(A[i]-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = input()
S=0
mod_count=[0]
ans=0
i=0
for X in N[::-1]:
  S = int(X)*pow(10,i,2019) % 2019
  S=mod_count[i]+S
  mod_count.append(S%2019)
  i+=1

c = Counter(mod_count)
ans = sum(Y * (Y-1)/2 for Y in c.values())
print(int(ans))

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit

MOD = 2019

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


S = np.int32(list(input().rstrip()))
print(f(S))

Submission status: Accepted

Solution code:
from collections import Counter

S = str(input())

memo = [0]
d = 0
mod = 2019


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

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

Submission status: Accepted

Solution code:
MOD=2019
S=input()
N=len(S)
nums=[0]*N
nums[-1]=int(S[-1])%MOD
for i in range(-2, -N-1, -1):
  nums[i]=(int(S[i])*pow(10, -(i+1), MOD)+nums[i+1])%MOD

a=[0]*2019
for i in range(N):
  a[nums[i]]+=1
  
print(a[0]+sum([(a[i]*(a[i]-1))//2 for i in range(2019)]))

Submission status: Accepted

Solution code:
s = input()[::-1]
num = 0
last = 0
d = 1
count={}
for k in range(2019):
    count[k] = 0
    
count[0] =1  # 割り切れるとき

for i in s:
    num = (int(i) * d + num)%2019
    
    d *= 10
    d %= 2019
    count[num] += 1
    
ans = 0
for j in range(2019):
    ans += count[j] * (count[j]-1) //2
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod = 2019
s = input().rstrip()
n = len(s)
mod_list = [0]
for i in range(n - 1, -1, -1):
    mod_list.append((mod_list[-1] + int(s[i]) * pow(10, n - 1 - i, mod)) % mod)
from collections import Counter
c = Counter(mod_list)
ans = 0
for i in c.keys():
    ans += c[i] * (c[i] - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

S = input()
MOD = 2019
dp = np.zeros(MOD, dtype=np.int64)
dp[0] = 1

def hoge(dp, s):
    T = dp.copy()
    dp[s:] = T[:-s]
    dp[:s] = T[-s:]

ans = 0
for i, s in enumerate(S[::-1]):
    hoge(dp, (int(s) * pow(10, i, MOD)) % MOD)
    ans += dp[0]
    dp[0] += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

S = input()
MOD = 2019
dp = np.zeros(MOD, dtype=np.int64)
dp[0] = 1

@njit
def hoge(dp, s):
    T = dp.copy()
    dp[s:] = T[:-s]
    dp[:s] = T[-s:]

ans = 0
for i, s in enumerate(S[::-1]):
    hoge(dp, (int(s) * pow(10, i, MOD)) % MOD)
    ans += dp[0]
    dp[0] += 1
print(ans)

Submission status: Accepted

Solution code:

S=list(input())
mod=2019
S=list(reversed(S))
N=len(S)
A=[0]*(N)
p=1
for i in range(N):
    if i==0:
        p=1
    else:
        p*=10
        p%=mod
    now=(int(S[i])*p)%mod
    A[i]=now
    #print(now)
rui=[0]*(N+1)
for i in range(1,N+1):
    rui[i]=(rui[i-1]+A[i-1])%mod
total=[0]*2019
for r in rui:
    total[r]+=1
ans=0
for t in total:
    ans+=t*(t-1)//2
print(ans)

Submission status: Accepted

Solution code:
#dpでできないかな？
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
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

s=SI()
n=len(s)
beki=[0 for i in range(n+1)]
beki[0]=1
for i in range(n):
    beki[i+1]=(beki[i]*10)%2019
#print(beki)

#k=int(s)
dp=[0 for i in range(n)]
dp[-1]=int(s[-1])
#print(dp[3])
for i in range(n-1):
    j=n-i-1
    #print((dp[j]+int(s[j-1])*beki[i+1])%2019)
    dp[j-1]=(dp[j]+int(s[j-1])*beki[i+1])%2019

#print(dp)
ans=0
u=Counter(dp)
#print(u)
for i in u:
    if i==0:
        ans+=(u[i]*(u[i]+1))//2
    else:
        ans+=(u[i]*(u[i]-1))//2
print(ans)

Submission status: Accepted

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

mods = [0]*2019
mods[0] += 1
f = 0
for i in range(len(S)):
    f = (f+pow(10,i,2019)*int(S[i]))%2019
    mods[f] += 1

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

Submission status: Accepted

Solution code:
from sys import stdin
def nC2(n):
    return n*(n-1)//2

def main():
    #入力
    readline=stdin.readline
    s=readline().strip()

    d=dict()
    p=1
    t=0
    for i in range(len(s)-1,-1,-1):
        n=int(s[i])
        m=(n*p+t)%2019
        t=m
        p*=10
        p%=2019
        if m not in d:
            d[m]=1
        else:
            d[m]+=1
        
    if 0 in d:
        ans=d[0]
    else:
        ans=0
    for v in d.values():
        ans+=nC2(v)
    print(ans)
    
if __name__=="__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s =list(str(input()))
s = [int(c) for c in s]
s.reverse()

n = len(s)
p = 2019

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

temp = 0
cum = [0]*n
for i in range(n):
    temp += s[i]*power(10, i, p)
    temp = temp%p
    cum[i] = temp
cum = [0]+cum

#print(cum)

d = {}
ans = 0
for i in range(n+1):
  if cum[i] not in d:
    d[cum[i]] = 1
  else:
    ans += d[cum[i]]
    d[cum[i]] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

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

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

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
s = list(map(int,list(input())))

t = 0
cusum = []
for i in range(len(s))[::-1]:
  t += s[i]*pow(10,len(s)-i-1,2019)
  t %= 2019
  cusum.append(t)
  
counter = Counter(cusum)

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

print(ans)

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 2019

from collections import defaultdict

S = list(input())
dic = defaultdict(int)
dic[0] += 1

ans = 0
x = 0
count = 0
for s in S[::-1]:
    x += int(s) * pow(10, count, MOD)
    x %= MOD
    ans += dic[x]
    dic[x] += 1
    count += 1

print (ans)

Submission status: Accepted

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

memo = defaultdict(int)
memo[0] += 1

mod = 2019
d = 1
val = 0

for s in S[::-1]:
    s = int(s)
    val += s * d
    val %= mod
    memo[val] += 1
    d *= 10
    d %= mod

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

Submission status: Accepted

Solution code:
S = input()
M = 2019

cnt = [0] * M
cnt[0] = 1
N = 0
ans = 0
for i, n in enumerate(map(int, S[::-1])):
    N = (N + n * pow(10, i, M)) % M
    ans += cnt[N]
    cnt[N] += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    S = input()
    n = len(S)
    p = 2019 # 法p
    # (1) a≡b,c≡dならばa+c≡b+d
    # (2) aと法pが互いに素である時、ab≡acならばb≡c
    # ex).S=1817181712114(idxは最下位が0とする), n=len(S)
    # 4≡4%p <- modp[0]
    # 14=10+4≡10%p+modp[0] <- modp[1]
    # 114=100+14≡100%p+modp[1] <- modp[2]
    # 2114=2000+114≡2000%p+modp[2] <- modp[3]
    # ...
    # 1817181712114≡100000000000%p+modp[n-2] <- modp[n-1]
    # したがって、S[1:4]=21%pについては
    # 2100=2114-14≡modp[3]-modp[1]
    # ここでaとpが互いに素なので(a=100,p=7)
    # 2100≡21 が言える
    # よって21≡modp[3]-modp[1]
    # 一般化すると、
    # S[i:j+1]≡modp[j]-modp[i]
    # すなわちmodp[j]==modp[i]となるi,jを選んだ時、S[i:j+1]はpで割り切れるという事になる

    # Sをreverseする
    S = [S[i] for i in range(n-1,-1,-1)]
    # modpを作成
    modp_counter = [0] * p
    modp = 0
    modp_counter[0] = 1 # 割り切れるやつが入る場所の初期値を1にしておかないと、1つ割り切れるやつがきたときにpair_count+=0となってしまう(pair_count+=1になるべきなのに)
    pair_count = 0
    d = 1
    for s in S:
        modp = (int(s)*d%p+modp)%p
        pair_count += modp_counter[modp]
        modp_counter[modp] += 1
        d *= 10
        d %= p # 計算量削減
    print(pair_count)


main()

Submission status: Accepted

Solution code:
S = input()
mod = 2019

cs_mods = {0:1}
cumsum = 0
count = 0
for i, s in enumerate(S[::-1]):
    cumsum = (cumsum + int(s) * pow(10, i, mod)) % mod
    cs_mods.setdefault(cumsum, 0)
    # count += cs_mods[cumsum]
    cs_mods[cumsum] += 1

# count = 0
for k, v in cs_mods.items():
    count += v*(v-1)//2

print(count)

Submission status: Accepted

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

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

from collections import Counter
L = Counter(L)

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

Submission status: Accepted

Solution code:
def solve(s):
    mod = 2019
    counts = [0]*mod
    counts[0] = 1
    result = 0
    suffix = 0
    power_of_ten = 1
    for char in s[::-1]:
        digit = int(char)
        suffix = (suffix + digit*power_of_ten) % mod
        result += counts[suffix]
        counts[suffix] += 1
        power_of_ten = 10 * power_of_ten % mod

    return result


if __name__ == "__main__":
    print(solve(input()))

Submission status: Accepted

Solution code:
def main():
    mod = 2019
    count = [0] * 2019
    count[0] = 1
    s = input().strip()
    digit = 1
    current = 0
    for c in s[::-1]:
        current = (current + int(c) * digit) % mod
        count[current] += 1
        digit = digit * 10 % mod
    return sum([n * (n - 1) // 2 for n in count if n > 1])


print(main())

Submission status: Accepted

Solution code:
S=input()

p,q=0,1
dp = {0:1}
mod = 2019

for i in range(len(S)-1,-1,-1):
  p = (p+int(S[i])*q)%mod
  if p not in dp:dp[p]=0
  dp[p]+=1
  q= (q*10)%mod

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

Submission status: Accepted

Solution code:
s=input()
a=[0]*2019
a[0]+=1
pot=1
v=0
ans=0
for i in range(len(s)-1,-1,-1):
	digit=int(s[i])
	v=(v+digit*pot)%2019
	pot=(pot*10)%2019
	ans+=a[v]
	a[v]+=1

print(ans)

Submission status: Accepted

Solution code:
S = input()
S = S[::-1]
#簡単にするためにひっくり返す
N = len(S)

A=[0]*2019
number=0
A[0]=1
#０を２０１９で割った余りは０
d=1

ans=0

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

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
string = input()
n = len(string)

# 文字列を反転する
string = string[::-1]

# 2019と10は互いに素
# 累積和に対してmod 2019をとったものの配列
S = [0]
d = 10
for i in range(n):
    t = int(string[i])*d+S[i]
    t = t % 2019
    S.append(t)
    d = (d * 10) % 2019

# Sの中で要素が一致する時の組み合わせの数を数える
count = 0
d = defaultdict(int)
for key in S:
    d[key] += 1

# print(S, d.values())

for j in d.values():
    if j >=2:
        count += j*(j-1)//2

# 愚直に探すと時間が足りない
# n=int(s)//2019
# for i in range(6, n+1):
#     count += s.count(str(2019 * i))
#     print(str(2019 * i))
print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S = input()
S = S[::-1]
d = 1
mods = [0]
counter = [0]*2019
counter[0] += 1
for s in S:
  s = int(s)
  mods.append((mods[-1]+s*d)%2019)
  counter[mods[-1]] += 1
  d *= 10
  d %= 2019

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

Submission status: Accepted

Solution code:
S = input()
S = S[::-1]
d = 1
mods = [0]
counter = [0]*2019
counter[0] += 1
result = 0
for s in S:
  s = int(s)
  mods.append((mods[-1]+s*d)%2019)
  counter[mods[-1]] += 1
  result += counter[mods[-1]] - 1
  d *= 10
  d %= 2019

print(result)

Submission status: Accepted

Solution code:
from collections import Counter
mod = 2019
s = list(input())
ln = len(s)

ms = [0]*(ln+1)
ms[ln] = 0
cr = 1
for i in range(ln):
  ms[ln-1-i] = (ms[ln-i] + cr*int(s[ln-1-i])) % mod
  cr = (cr*10) % mod

cnts = Counter()
for i in ms:
  cnts[i] += 1
ans = 0
for k,v in cnts.items():
  if v >= 2:
    ans += int(v*(v-1)/2)
print(ans)

Submission status: Accepted

Solution code:
m = 2019
C = [0]*m
C[0] = 1
s = list(input())
now = 0
cnt = 0
while s:
  now += pow(10, cnt, m) * int(s.pop())
  now %= m
  C[now] += 1
  cnt += 1
ans = 0
for c in C:
  ans += c*(c-1)//2
print(ans)

Submission status: Accepted

Solution code:
s=input()
n=len(s)
mod=2019
sum=0
p=1
d={}
d[0]=1
for i in range(n-1,-1,-1):
    sum=(sum+int(s[i])*p)%mod
    if sum in d:
        d[sum]+=1
    else:
        d[sum]=1
    p=(p*10)%mod
ans=0
for v in d.values():
    ans+=(v*(v-1))//2
print(ans)

Submission status: Accepted

Solution code:
s = input()
n = len(s)
res = 0
sum = 0
c = {}
c[0] = 1
p = 1
for i in range(n - 1, -1, -1):
    sum = (sum + int(s[i]) * p) % 2019
    if sum in c:
        res += c[sum]
    p = (p * 10) % 2019
    c[sum] = c.get(sum, 0) + 1

print(res)

Submission status: Accepted

Solution code:
s = input()
d={0:1}
suf=0
pot=1
ans=0
for i in range(len(s)-1,-1,-1):
    dig=int(s[i])
    suf=(suf+dig*pot)%2019
    pot=(pot*10)%2019
    if suf in d:
        ans+=d[suf]
        d[suf]+=1
    else:
        d[suf]=1
print(ans)

Submission status: Accepted

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

l = [0 for i in range(2019)]
n = len(s)
l[0] = 1
prev = 0
digit = 1
for c in s:
    t = (int(c) * digit + prev) % 2019
    l[t] += 1
    digit = (digit * 10) % 2019
    prev = t

res = 0
for i in l:
    res += i * (i-1) // 2

print(res)

Submission status: Accepted

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

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

print(ans) # 答えの出力

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
import sys
import itertools
import collections

INF = 1145141919


def solve(S: int):
    l = list(reversed(str(S)))
    a = [int(l[c]) * pow(10, c, 2019) for c in range(len(l))]

    def list_cumsum(l):
        return list(itertools.accumulate(l))
    s = [n % 2019 for n in list_cumsum([0]+a)]

    return sum([sum(range(v)) for v in collections.Counter(s).values()])


def main():

    sys.setrecursionlimit(10 ** 6)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
import sys
import itertools
import collections

INF = 1145141919


def solve(S: int):
    l = list(reversed(str(S)))
    a = [int(l[c]) * pow(10, c, 2019) for c in range(len(l))]

    def list_cumsum(l):
        return list(itertools.accumulate(l))
    s = [n % 2019 for n in list_cumsum([0]+a)]

    return sum([int(v * (v-1) / 2) for v in collections.Counter(s).values()])


def main():

    sys.setrecursionlimit(10 ** 6)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def function(S):
    S = S[::-1]
    mods = [0]*2019 # mod 2019の余り0~2018の数
    mods[0] += 1 # 自身が割れる場合
    # MEMO : int(c) * 10^n % 2019 をまともに計算するとTLE
    # １つ前の桁のmodを利用する
    num = 0
    digit = 1
    for c in S:
        num = (int(c) * digit + num) % 2019
        digit = (digit * 10) % 2019
        mods[num] += 1
    
    result = 0
    for m in mods:
        result +=  m * (m-1) // 2

    return str(result)

if __name__ == '__main__':
    print(function(input()))

Submission status: Accepted

Solution code:
from collections import defaultdict

s=input()
d=defaultdict(int)

dp=0
d[0]+=1
r=1
for i in range(len(s)-1,-1,-1):
	dp+=int(s[i])*r
	dp%=2019
	d[dp]+=1
	r*=10
	r%=2019
	
res=0

l=list(d.values())
for a in l:
	res+=a*(a-1)//2
	
print(res)

Submission status: Accepted

Solution code:
s=input()

d=[0]*2019
dp=0
d[0]+=1
l=len(s)
r=1

for i in range(l):
	dp+=int(s[l-1-i])*r
	dp%=2019
	r*=10
	r%=2019
	d[dp]+=1

res=0

for a in d:
	res+=a*(a-1)//2
	
print(res)

Submission status: Accepted

Solution code:
s = list(input())
mods = [0]*(len(s))
countRemainder = [0] * 2019
cnt = 0


m = 1
mod = 0
for i in range(len(s)):
    mod += int(s[len(s) - i - 1]) * m

    mod %= 2019
    m *= 10
    m %= 2019

    countRemainder[mod] += 1

countRemainder[0] += 1

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

print(cnt)

Submission status: Accepted

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

#slist = [(s%(10**i))%2019 for i in range(n+1)]
#print(slist)


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)
SUM = [0] * (N + 1)
MOD = 2019

r = 1  # 10のi乗を2019で割った余り
S = S[::-1]
for i in range(N):
    A = r * int(S[i])
    SUM[i + 1] = (SUM[i] + A) % MOD
    r = r * 10 % MOD

cnt = [0] * 2019
ans = 0
for x in SUM:
    ans += cnt[x]
    cnt[x] += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    mod=2019
    S=input()[::-1]
    l=[0]
    m=1
    for i in range(len(S)):
        l.append((l[-1]+m*int(S[i]))%mod)
        m=m*10%mod
    ll=[0]*2019
    for i in l:
        ll[i]+=1
    ans=0
    for i in range(2019):
        ans+=ll[i]*(ll[i]-1)//2
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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]
N = len(S)
l = [0]*2019
l[0] = 1
n = 0
d = 1

for i in range(N):
    n += int(S[i]) * d
    r = n % 2019
    l[r] += 1
    d = 10*d % 2019
    
out = 0    
for m in l:
    out += (m*(m-1))//2 
print(out)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import collections as coun
sys.setrecursionlimit(10000000)
s=input()
n=len(s)
def mod10(x):
    return (10**(x%224))%2019
dp=[-1]*n
tmp=0
for i in reversed(range(n)):
    if i==n-1:
        dp[i]=int(s[i])
    else:
        dp[i]=(dp[i+1]+int(s[i])*pow(10,n-1-i,2019))%2019

#print(dp)
p=-1
for i in range(len(dp)-1):
    if dp[i]==dp[i+1]:
        dp[i]=p
        p=p-1

#print(dp)

c=coun.Counter(dp)
sum=0
for v in c.values():
    sum+=v*(v-1)//2
#print(sum)
for i in dp:
    if i==0:
        sum+=1
#print(sum)
if dp[-1]==0:
    sum=sum-1
print(sum)

Submission status: Accepted

Solution code:
S=input()

mod=2019
D={}
S=S[::-1]
now=0

for i in range(len(S)):
    if (int(S[i])*pow(10,i,mod)+now)%mod not in D:
        D[(int(S[i])*pow(10,i,mod)+now)%mod]=1
    else:
        D[(int(S[i])*pow(10,i,mod)+now)%mod]+=1
    now=(int(S[i])*pow(10,i,mod)+now)%mod
#print(D)
ans=0
for k,v in D.items():
    if k==0:
        v+=1
    ans+=v*(v-1)//2
print(ans)

Submission status: Accepted

Solution code:
S = input()
n = len(S)
dp = {0:1}
q = 1
p = 0
for i in range(n):
    p += int(S[n-1-i])*q
    q *= 10
    q = q % 2019
    p = p % 2019
    if p not in dp:
        dp[p] = 1
    else:
        dp[p] += 1
print(sum(dp[i]*(dp[i]-1)//2 for i in dp))

Submission status: Accepted

Solution code:
from collections import Counter
S = list(input())
S.reverse()
L = len(S)
dp = [0] * (L+1)
tmp = 0
for i in range(L):
    tmp += int(S[i]) * pow(10, i, 2019)
    tmp %= 2019
    dp[i] = tmp

c = Counter(dp)
ans = 0
for i, v in c.items():
    ans += v * (v-1) // 2

print(ans)

Submission status: Accepted

Solution code:
S=input()
dp = {0:1}

p=0
q=1

for i in range(len(S)-1,-1,-1):
  p += (int(S[i])*q)
  p = p%2019
  q *= 10
  q = q%2019
  if p not in dp:
    dp[p]=0
  dp[p]+=1

#print(dp)
c = 0
for v in dp:
  c += dp[v]*(dp[v]-1)//2
print(c)

Submission status: Accepted

Solution code:
S = input()

S = S[::-1]
result = 0
t = [0] * 2019
m = 1
n = 0
for i in range(len(S)):
    t[n] += 1
    n += int(S[i]) * m
    n %= 2019
    result += t[n]
    m *= 10
    m %= 2019
print(result)

Submission status: Accepted

Solution code:
def main():
    S = input()[::-1]
    ans = 0
    mods = [0] * 2019
    mods[0] = 1
    current = 0
    x = 1
    for s in S:
        current = (current + x * int(s)) % 2019
        mods[current % 2019] += 1
        x = x * 10 %2019
    
    for i in mods:
        ans += i*(i-1)//2
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def find(S):
    S = S[::-1]
    number = [0] * 2019
    ans = 0
    cur = 0
    power = 1
    for i in range(len(S)):
        
        cur += power * int(S[i])
        power *= 10
        power %= 2019
        cur %= 2019
        ans += number[cur]
        if cur == 0:
            ans += 1
        number[cur] += 1
        
    return ans

print(find(input()))

Submission status: Accepted

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

d = 1
M = []
for s in S:
    M.append(int(s)*d % 2019)
    d *= 10
    d %= 2019

S = [0]
for m in M:
    S.append((S[-1]+m) % 2019)

C = collections.Counter(S)

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

Submission status: Accepted

Solution code:
S = input()
 

dp = [0]*2019
c = 0
dp[0] = 1

p = 0
q = 1
for i in range(len(S)):
  p += int(S[len(S)-1-i])*q
  p %= 2019
  q *= 10
  q %= 2019
  dp[p] += 1
 
for j in dp:
  c += j * (j-1) // 2
print(c)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def main():
    S = input()[::-1]
    ans = 0
    mods = [0] * 2019
    mods[0] = 1
    current = 0
    x = 1
    for s in S:
        current = (current + x * int(s)) % 2019
        ans += mods[current % 2019]
        mods[current % 2019] += 1
        x = x * 10 % 2019
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
ss=input().rstrip()

x=1
y=0
mod=[0]*3000
ans=0
mod[0]=1
for i in range(len(ss)):
  s=ss[i*(-1)-1]
  n=int(s)
  y=(y+x*n)%2019
  ans+=mod[y]
  mod[y]+=1
  x=(x*10)%2019
print(ans)

Submission status: Accepted

Solution code:
S = input()[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1
current = 0
x = 1
for s in S:
    current = (current + x * int(s)) % 2019
    ans += mods[current % 2019]
    mods[current % 2019] += 1
    x = x * 10 % 2019
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

s = input()

d = [ int( 0 ) ] * 2019
d[ 0 ] = int( 1 )
r = int( 0 )
t = int( 1 )

for si in reversed( s ):
#    print( si )

    r = int( si ) * t + r
    r = r % 2019

    t = t * 10
    t = t % 2019

    d[ r ] = d[ r ] + 1

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

print( ans )

Submission status: Accepted

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

T=[]
T.append(0)
tmp=""
d=[0 for _ in range(2019)]
d[0]=1
r=0
t=1
for i in range(N):
    s=S[N-1-i]
    r+=int(s)*t
    r%=2019
    t*=10
    t%=2019
    d[r]+=1

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

print(ans)

Submission status: Accepted

Solution code:
S=input()
N=len(S)
#「連続する区間」についての問題では、”累積和的なもの”をとるのが定石である。
#Sの連続する区間が、右からa文字分から、右からb文字分を取り除いたものであるとき
#その区間の整数が2019の倍数になるということは、s[a]とs[b]を2019で割ったあまりが等しい
#十分条件であることは分かったが、必要条件であるのか
#結論として必要条件でもある
#なぜなら2019と10は互いに素であるからである。

T=[]
T.append(0)
tmp=""
d=[0 for _ in range(2019)]
d[0]=1
r=0
t=1
for i in range(N):
    s=S[N-1-i]
    r+=int(s)*t
    r%=2019
    t*=10
    t%=2019 
    d[r]+=1

ans=0

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

Submission status: Accepted

Solution code:
#ABC164d
def main():
    s = input()
    MOD = 2019
    d = [ 0 for i in range(MOD)]
    # print(d)
    ans = 0
    k = 0
    d[0] = 1
    s = s[::-1]
    # print(s)
    p = 1
    for i in s:
        # print(p,i,k)
        # print('pnosiki')
        # print(p * int(i) + k)
        k = (p * int(i) + k) % MOD
        # print('k:')
        # print(k)
        ans += d[k]
        d[k] += 1
        p = (p * 10) % MOD
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
import sys

# input = lambda : sys.stdin.readline().rstrip()

S = input()
n = len(S)

M = []
m = 0

for i in range(len(S)-1,-1, -1):
    
    m = (pow(10, n-i, 2019) * int(S[i]) + m) % 2019
    M.append(m)
    
    # print(S[i:n], m)

M.append(0)  # S[n:n] = "" = 0 が抜けるので、付け加える

c = Counter(M)

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

print(int(sum))

Submission status: Accepted

Solution code:
#  =========     /\       /|    |====/|
#      |        /  \       |    |   / |
#      |       /____\      |    |  /  |
#      |      /      \     |    | /   |
#  ========= /        \  =====  |/====|  
#  code

def main():
    s = input()
    MOD = 2019
    d = [ 0 for i in range(MOD)]
    ans = 0
    k = 0
    d[0] = 1
    s = s[::-1]
    p = 1
    for i in s:
        k = (p * int(i) + k) % MOD
        ans += d[k]
        d[k] += 1
        p = (p * 10) % MOD
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
S = input()[::-1]
N = len(S)
mod = [1] * N
#mod[i]=S[i]*10**i % 2019
for i in range(1, N):
    mod[i] = mod[i - 1] * 10 % 2019
for i in range(N):
    mod[i] *= int(S[i])
cumsum = [0] * N
cumsum[0] = mod[0]
for i in range(1, N):
    cumsum[i] = (cumsum[i - 1] + mod[i]) % 2019
cnt = collections.Counter(cumsum)
ans = cnt[0]
for i in range(2019):
    c = cnt[i]
    ans += c * (c - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
mod = 2019
s = input()
n = len(s)
w = 0
d = {}
p = 1
for i in reversed(range(n)):
	w += int(s[i]) * p
	p *= 10
	w %= mod
	p %= mod
	if w in d:
		d[w] += 1
	else:
		d[w] = 1
if 0 in d:
	d[0] += 1
else:
	d[0] = 1
o = 0
for x in d:
	o += d[x] * (d[x] - 1) // 2
print(o)

Submission status: Accepted

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

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