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 = 31415926535を考えます。
このとき、例えば4番目から8番目までの部分文字列15926が
2019の倍数であるか判定したいというのが本問の主題です。
特定の部分文字列が2019の倍数であるかどうかは、
int(s[[i:j+1]) % 2019 == 0とすればよいのですが、
これを逐一やっていてはO(N^2)の計算量がかかってしまいます。
そこで、この部分文字列を次のようにとらえてみます。
15926=(15926535−535)/10^3
このように考えることの利点は、10^3 が 2019 と
互いに素（最大公約数が 1）であるため、
15926 が 2019 の倍数であるかどうかは、
上式右辺の分子に着目すればよいということです。
したがって、アルゴリズムを設計する際は、
与えられた文字列の右からk番目（0～n)から最右端までの
部分文字列を保持しておけばよいことになります。
分子が 2019 の倍数かどうかは、分子を A−B としたときに、
A mod2019 と B mod2019 の値がそれぞれ等しければ、
元の整数（上式左辺）は 2019 の倍数であると言えます。
'''
s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019#2019で割った余りの個数をカウント
counts[0] = 1#その数が、ちょうど2019で割れた時のために必要

num, d = 0, 1

for char in s:
    num += int(char) * d#1桁目から数字を作る、整数型にする
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1#2019で割った余りの個数を足す1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2
    #余りが同じものを2つ選ぶ組み合わせの数が答

print(ans) # 答えの出力

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8

# 17:36-18:18 give up => kaisetu
# -18:46 - 18:52 chudan
# -20:21


def main():
    S = input() + "0"
    # S = "1" * 10**5 + "0"
    N = len(S)
    S = list(map(int, S))

    q = 2019

    res = [0] * N
    num = 0
    p = 1
    pow_memo = {0: (10**0) % q}
    for i in range(N-2, -1, -1):
        pow_memo[p] = (pow_memo[p-1] * 10) % q
        num = (num + (S[i] % q) * pow_memo[p]) % q
        res[i] = num
        p += 1

    cnt = [0] * q
    for r in res:
        cnt[r] += 1

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

    return ans


print(main())

Submission status: Accepted

Solution code:
S=input()
C,m,T=2019,0,[1]+[0]*2018
for i,s in enumerate(S[::-1]):
  m=(m+int(s)*pow(10,i,C))%C
  T[m]+=1
print(sum(T[i]*~-T[i]//2 for i in range(2019)))

Submission status: Accepted

Solution code:
from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

T = S()

revT = reversed(T)

n, d, mods = 0, 1, [1]+[0]*2019

for i in revT:
    n = (n + int(i)*d)%2019
    d = d*10%2019
    mods[n] += 1

sum = 0
for j in mods:
    sum += j*(j-1)//2

print(sum)

Submission status: Accepted

Solution code:
s = input()

li = []
mod = 2019
tmp = 0

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

li.append(tmp)
li.sort()

tmp = li[0]
t_num = 1
ans = 0

for i in range(1,len(li)):
    if tmp == li[i]:
        t_num += 1
    else:
        ans += t_num*(t_num-1)//2
        t_num = 1
        tmp = li[i]

ans += t_num*(t_num-1)//2

print(ans)

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

S = sys.stdin.readline().strip()
S = S[::-1]

n = len(S)
r = [0] * 2019
acum = [0] * (len(S)+1)
r[0] += 1
for i, s_i in enumerate(S):
    acum[i+1] = int(s_i) * pow(10, i, 2019) + acum[i]
    acum[i+1] %= 2019
    r[acum[i+1]] += 1
# print(acum)

ans = 0
for r_i in r:
    ans += r_i * (r_i - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
S = str(input())

#10**nのmod計算
A = []
p =1
for i in range(len(S)):
  A.append(p)
  p = p*10%2019

#左からi文字以降の数字列のmod計算
X = []
a = 0
for i in range(len(S)):
  a = (a + int(S[len(S)-i-1])*A[i]) %2019
  X.append(a)
X.sort()
flag =1
n = 0

#modが同じになる組み合わせ、またはもともとmodが0になる数字列の個数の総和計算
for i in range(len(X)-1):
  if X[i]==0:
    n +=1
  if X[i]==X[i+1]:
    flag += 1
  else:
    n += int(flag*(flag-1)/2)
    flag = 1
n += int(flag*(flag-1)/2)
if X[len(X)-1]==0:
  n +=1
print(n)

Submission status: Accepted

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

tmp = 0
for i in range(len(S)):
    tmp += int(S[i])*pow(10, i, 2019)
    tmp %= 2019
    dp[tmp] += 1
ans = 0
for i in dp:
    if i >= 2:
        ans += i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
s = input()
from collections import Counter
x = 1
mod = 2019
total = 0
ans = 0
cnt = Counter()
for i in range(len(s)-1,-1,-1):
    cnt[total] += 1
    total = total + int(s[i])*x
    total %= mod
    ans += cnt[total]
    x = x*10%2019
print(ans)

Submission status: Accepted

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

# 余りの累積和
d = [0] * (N+1)
ten = 1
for i in range(N-1, -1, -1):
    a = int(S[i]) * ten % P
    d[i] = (d[i+1] + a) % P 
    ten *= 10
    ten %= P

ans = 0
count = [0] * P
for i in range(N, -1, -1):
    ans += count[d[i]]
    count[d[i]] += 1

print(ans)

Submission status: Accepted

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

s = s[::-1]

x = 1
mod = 2019
total = 0
ans = 0
cnt = Counter()

for i in range(len(s)):
    cnt[total] += 1
    total = total + int(s[i])*x
    total %= mod
    ans += cnt[total]
    x = x*10%mod

print(ans)

Submission status: Accepted

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    s = input()
    n = len(s)
    """
    s = d0d1...dn-1
    Tk = dk...dn-1 とする
    Tn = 0
    Tk = T(k+1) + dk * 10^(n-k-1) で計算可能
    s[i:j] = di...d(j-1)
           = (Ti - Tj) * 10^(n-j)
    s[i:j] ≡ 0 (mod 2019) <=> Ti ≡ Tj (mod 2019) で判定可能
    """

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
s = input()[::-1]
l = len(s)
MOD = 2019
ans = 0
mods = [0] * 2019
mods[0] = 1
num = 0
cnt = 0
d = 1
for i in s:
    num += int(i) * d
    num %= MOD
    mods[num] += 1
    d *= 10
    d %= MOD

for j in mods:
    ans += int(j*(j-1)/2)

print(ans)

Submission status: Accepted

Solution code:
def main():
    s = input()
    n = len(s)
    modlis = [0 for i in range(2019)]
    modlis[0]=1
    t = 0
    m = 1
    for i in range(n):
        t = (t+int(s[n-1-i])*m)%2019
        m = m*10%2019
        modlis[t]+=1

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
import math

S = input()

mm = [0] * (2019)
mm[0] = 1
a = [0] * (len(S) + 1 ) 
T = 0
ten = 1
ll = len(S)
for i in range(ll):
    if i > 0:
        ten = ( ten * 10 ) % 2019
    a[i+1] =  ( a[i] + (int(S[ll-1-i])*ten ) ) % 2019
    mm[ a[i+1] ] += 1
    #print(s)

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
'''
1~9の文字列で構成されたSの中で
i文字目からj文字目までが2019の倍数になっているものの個数を求めよ

terms:
    1<=|S|<=2*10**5

input:
    1817181712114

output:
    3
'''
from collections import defaultdict
import sys
input = sys.stdin.readline
s = input()[:-1]
n=len(s)
arr = [int(s[i]) for i in range(n)]
ans = 0
dic = defaultdict(int)
dic[0] = 1
now = 0
for i in range(n - 1, -1, -1):
    now += arr[i] * pow(10, n - i - 1, 2019)
    now %= 2019
    ans += dic[now]
    dic[now] += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

S = [int(i) for i in input()]
S.reverse()
lst = []
_sum = 0

for i in range(len(S)):
    _sum = (_sum + S[i] * pow(10,i,2019)) % 2019
    lst.append(_sum)
    
C = Counter(lst)    
ans = C[0]

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

Submission status: Accepted

Solution code:
M=2019;a=i=0;d=[0]*M;p=1
for j in input()[::-1]:d[i%M]+=1;i-=int(j)*p;a+=d[i%M];p=p*10%M
print(a)

Submission status: Accepted

Solution code:
s=list(input())
s.reverse()
s_len = len(s)

list = [0 for _ in range(2019)]
ans = 0
mod = 2019
li = [0]
digit = 0
for i in range(s_len):
    li.append((li[i] + int(s[i])*pow(10,digit,mod))%mod)
    digit+=1
for i in range(s_len+1):
    list[li[i]]+=1
for i in range(2019):
    x = list[i]
    ans += x*(x-1)/2
print(int(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    # 右からi文字目から最後の数字までを数値化したものについてmodを計算していく
    mod_count = [1] + [0] * 2019
    tmp_mod_val = 0
    cnt = 0
    i = 0
    for s in reversed(input()):
        tmp_mod_val += int(s) * pow(10, i, 2019)
        tmp_mod_val %= 2019
        cnt += mod_count[tmp_mod_val]
        mod_count[tmp_mod_val] += 1
        i += 1

    print(cnt)


main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    # 入力
    # st = input()

    # 右からi文字目から最後の数字までを数値化したものについてmodを計算していく
    mod_res_dic = {0: 1}
    tmp_mod_val = 0
    # r_st = ''.join(list(reversed(st)))
    cnt = 0
    i = 0
    for s in reversed(input()):
        tmp_mod_val += int(s) * pow(10, i, 2019)
        tmp_mod_val %= 2019
        ls = mod_res_dic.setdefault(tmp_mod_val, 0)
        mod_res_dic[tmp_mod_val] = ls + 1
        i += 1
        if ls > 0:
            cnt += ls

    print(cnt)


main()

Submission status: Accepted

Solution code:
from collections import Counter

MOD = 2019
S = input()[::-1]
n = 0
x = 1
c = Counter()
ans = 0

for s in S:
    c[n] += 1
    n += int(s) * x
    n %= MOD
    ans += c[n]
    x = x * 10 % MOD
    
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    # 入力
    st = input()

    # 右からi文字目から最後の数字までを数値化したものについてmodを計算していく
    mod_res_dic = {0: 1}
    tmp_mod_val = 0
    r_st = ''.join(list(reversed(st)))
    cnt = 0
    for i in range(len(r_st)):
        target_st = r_st[i:i+1]
        tmp_mod_val += int(target_st)*pow(10, i, 2019)
        tmp_mod_val %= 2019
        ls = mod_res_dic.setdefault(tmp_mod_val, 0)
        mod_res_dic[tmp_mod_val] = ls+1
        if ls > 0:
            cnt += ls

    print(cnt)


main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    # 入力
    st = input()

    # 右からi文字目から最後の数字までを数値化したものについてmodを計算していく
    mod_res_dic = {0: [0]}
    tmp_mod_val = 0
    r_st = ''.join(list(reversed(st)))
    cnt = 0
    for i in range(len(r_st)):
        target_st = r_st[i:i+1]
        tmp_mod_val += int(target_st)*pow(10, i, 2019)
        tmp_mod_val %= 2019
        ls = mod_res_dic.setdefault(tmp_mod_val, [])
        ls.append(i-1)
        if len(ls) > 1:
            cnt += len(ls)-1

    print(int(cnt))


main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def main():
    # 入力
    st = input()

    # if len(st) < 4:
    #     print(0)
    #     return

    # 右からi文字目から最後の数字までを数値化したものについてmodを計算していく
    mod_res_dic = {0: [0]}
    tmp_mod_val = 0
    r_st = ''.join(list(reversed(st)))
    cnt = 0
    for i in range(len(r_st)):
        target_st = r_st[i:i+1]
        # mod_res = ((10 ** i) * int(target_st) + tmp_mod_val) % 2019
        tmp_mod_val += int(target_st)*pow(10, i, 2019)
        tmp_mod_val %= 2019
        ls = mod_res_dic.setdefault(tmp_mod_val, [])
        ls.append(i-1)
        if len(ls) > 1:
            cnt += len(ls)-1
        # tmp_mod_val = mod_res

    # print(mod_res_dic)
    # modが同じペアのものについて、iからj文字目までを2019で割り切れるので、その組み合わせを計算
    # cnt = 0
    # for v in mod_res_dic.values():
    #     comb = len(v)
    #     if comb < 2:
    #         continue
    #     cnt += (comb * (comb - 1)) / 2

    print(int(cnt))


main()

Submission status: Accepted

Solution code:
import collections
s = input()
n = len(s)
mod_list = [0]

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

res = collections.Counter(mod_list)
cnt = 0
for d in res.values():
    cnt += int(d*(d-1)/2)
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s = input()

t, a = 0, 1
mod = [0]*2019
mod[0] = 1
s = s[::-1]
n = len(s)
for i in range(n):
    t += int(s[i]) * a
    t %= 2019
    a *= 10  #a *= 2019 <- TLE
    a %= 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()

N=len(S)
count=0
tot=[0]*2019
S=S[::-1]
base=0
#print(S)
for i,s in enumerate(S):
    base+=int(s)*pow(10,i,2019)
    base%=2019
    #tot[base]+=1
    #print(base)
    if base==0:
        count+=1
    count+=tot[base]
    #print(tot[base],i,base)
    tot[base]+=1
#print(tot)    

print(count)

Submission status: Accepted

Solution code:
s = input()

t, a = 0, 1
mod = [0]*2019
mod[0] = 1
s = s[::-1]
n = len(s)
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()
T=len(S)
a=0
d=1
mod=[0]*2019
mod[0]+=1
for i in range(T):
 a+=(int(S[T-i-1])*(d))%2019
 b=a%2019
 mod[b]+=1
 d*=10
 d%=2019
c=0
for i in range(2019):
 if mod[i]>=2:
  c+= mod[i]*(mod[i]-1)/2
print(int(c))

Submission status: Accepted

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

count = [0] * 2019
count[0] = 1

num = 0
d = 1

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


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

print(res)

Submission status: Accepted

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

MOD = 2019

"""
gcd(10, 2019) = 1 互いに素(最大公約数が1)
-> 10のmod2019での逆元(1/10)が存在
"""
S = input().rstrip()
s_list = list(map(int, list(S)))[::-1]

counts = [0] * MOD
counts[0] = 1

num = 0
for i, s_element in enumerate(s_list):
    num += s_element * pow(10, i, MOD)
    num %= MOD
    counts[num] += 1

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

print(ans)

Submission status: Accepted

Solution code:
mod=2019
a=input()

N=len(a)
t=[0]*mod
t[0]=1

w=1
u=0

for i in range(N):
  u=int(a[N-1-i]) * w + u
  v=u % mod
  t[v] += 1
  w *=10
  w %= mod

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

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
now = 0
ans = 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:
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:
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1
MOD = 2019

"""
gcd(10, 2019) = 1 互いに素
-> 10のmod2019での逆元(1/10)が存在
"""
S = input().rstrip()
s_list = list(map(int, list(S)))[::-1]

counts = [0] * MOD
counts[0] = 1

num, d = 0, 1

for s_element in s_list:
    num += s_element * d
    num %= MOD
    d *= 10
    d %= MOD
    counts[num] += 1

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

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

s = s()

mod = 2019
num_int = 0
mod_dict = defaultdict(int)
mod_dict[num_int % mod] += 1
s = s[::-1]
t = 1
for i in range(len(s)):
    num_int += t * int(s[i])
    num_int %= mod
    t *= 10
    t %= mod
    mod_dict[num_int] += 1

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

print(ans)

Submission status: Accepted

Solution code:
def main():
    s = list(input())
    s.reverse()
    MOD = 2019
    tot = 0
    ans = 0
    d = [0 for _ in range(MOD)]
    for i in range(len(s)):
        d[tot] += 1
        x = pow(10, i, MOD)
        p = int(s[i]) * x
        p %= MOD
        tot = (tot + p) % MOD
        ans += d[tot]
    return ans


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
s=input()
N=len(s)
kyonen=2019
ans=0

#alistつくる
alist=[]
for i in reversed(range(N)):
    alist.append((int(s[i])*pow(10,(N-1-i),kyonen))%kyonen)

#累積和とる
ruisekiwa=[0]
for i in range(N):
    ruisekiwa.append((ruisekiwa[-1]+alist[i])%kyonen)

#累積和リストの中から、同じ数字の組み合わせの個数を求める
kazoe=[0]*2019
for i in range(N+1):
    kazoe[ruisekiwa[i]]+=1

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

if ruisekiwa[N]==0:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    S = input()
    s_list = list(map(int, list(S)))[::-1]
    MOD = 2019

    sum_v = 0
    cnt = [0] * MOD
    cnt[0] = 1
    x = 1
    for s in s_list:
        sum_v += s * x
        sum_v %= MOD
        x *= 10
        x %= MOD
        cnt[sum_v] += 1
    print(sum([c * (c - 1) // 2 for c in cnt if c > 1]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    S = input()
    s_list = list(map(int, list(S)))[::-1]
    MOD = 2019

    sum_v = 0
    cnt = [0] * MOD
    cnt[0] = 1
    for i, s in enumerate(s_list):
        sum_v += s * pow(10, i, MOD)
        sum_v %= MOD
        cnt[sum_v] += 1
    print(sum([c * (c - 1) // 2 for c in cnt if c > 1]))

if __name__ == '__main__':
    main()

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
    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)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
s = input()

c = [0 for i in range(2019)]
c[0] = 1
mod = 2019
x = 0
for i,j in enumerate(s[::-1]):
	x = (x + int(j)*pow(10,i,mod))%mod
	c[x] += 1
ans = 0
for i in range(mod):
	ans += (c[i]*(c[i]-1))//2
print (ans)

Submission status: Accepted

Solution code:
import sys
# sys.stdin = open('input.txt')

m = 2019
s = input()
n = len(s)
s = list(map(int, s[::-1]))

x = 1
tot = 0
cnt = [0 for _ in  range(m)]
ans = 0

for i in range(n):
    cnt[tot] += 1
    tot += (s[i] - 0) * x
    tot %= m
    ans += cnt[tot]
    x = x * 10%m

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s = input()

c = [0 for i in range(2019)]
c[0] = 1
mod = 2019
d = 1
x = 0
for i,j in enumerate(s[::-1]):
	x = (x + int(j)*pow(10,i,mod))%mod
	c[x] += 1

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

Submission status: Accepted

Solution code:
S = list(input())
a=[int(x) for x in S] #int型のリストに変換
a.reverse()
#print(a)
l=[0]*2019
l[0]=1
T=0
d=1

for i in a:
    T+=(int(i)*d)
    T%=2019
    l[T]+=1
    d*=10
    d%=2019
result=0
for n in l:
    result+=n*(n-1)/2
print(int(result))

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
import numpy as np
def ConZ(i):
    z_num = i+int(i*(i-1)/2)
    return z_num
#def ConN(i):
    #n_num = int(i*(i-1)/2)
    #return n_num
def cmb(n):
    over = reduce(mul, range(n, n - 2, -1))
    under = reduce(mul, range(1,2 + 1))
    return over // under


S = input()[::-1]
keta = 1
A_num = 0
x = 0
mod = np.array([0]*2019)
for i in range(len(S)):
    A_num += int(S[i:i+1])*keta
    if A_num >= 2019:
        A_num = A_num%2019
    mod[A_num] +=1
    #keta*=10
    keta = keta * 10 % 2019
#print(mod)
x += ConZ(mod[0])
#del mod[0]

for j in range(1,len(mod)):
    x+=cmb(mod[j])
print(x)
#print(int(np.sum(mod* (mod - 1) /2)))

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
import numpy as np
#def ConZ(i):
    #z_num = i+int(i*(i-1)/2)
    #return z_num
#def ConN(i):
    #n_num = int(i*(i-1)/2)
    #return n_num

def cmb(n):
    over = reduce(mul, range(n, n - 2, -1))
    under = reduce(mul, range(1,2 + 1))
    return over // under


S = input()[::-1]
keta = 1
A_num = 0
x = 0
mod = np.array([0]*2019)
mod[0] += 1
for i in range(len(S)):
    A_num += int(S[i:i+1])*keta
    if A_num >= 2019:
        A_num = A_num%2019
    mod[A_num] +=1
    #keta*=10
    keta = keta * 10 % 2019
#print(mod)
#x += ConZ(mod[0])
#del mod[0]

#for j in range(len(mod)):
    #x+=cmb(mod[j])
#print(x)
print(int(np.sum(mod* (mod - 1) /2)))

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
import numpy as np
#def ConZ(i):
    #z_num = i+int(i*(i-1)/2)
    #return z_num
#def ConN(i):
    #n_num = int(i*(i-1)/2)
    #return n_num

def cmb(n):
    over = reduce(mul, range(n, n - 2, -1))
    under = reduce(mul, range(1,2 + 1))
    return over // under


S = input()[::-1]
keta = 1
A_num = 0
x = 0
mod = np.array([0]*2019)
mod[0] += 1
for i in range(len(S)):
    A_num += (int(S[i:i+1])*keta)%2019
    if A_num >= 2019:
        A_num = A_num%2019
    mod[A_num] +=1
    #keta*=10
    keta = keta * 10 % 2019
#print(mod)
#x += ConZ(mod[0])
#del mod[0]

#for j in range(len(mod)):
    #x+=cmb(mod[j])
#print(x)
print(int(np.sum(mod* (mod - 1) /2)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
s = str(input())

mod = 2019

div_memo = [0 for _ in range(mod)]

num = 0
d = 1
for n in reversed(s):
    num += int(n)*d
    num %= 2019
    div_memo[num] += 1
    d *= 10
    d %= 2019

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

ans += div_memo[0]
print(int(ans))

Submission status: Accepted

Solution code:
s = str(input())
n = len(s)
x = [0]*2019
x[0] = 1
m = 0
j = 1
for i in range(n):
  m = (m + int(s[-i-1])*j)%2019
  x[m] += 1
  j = (j*10)%2019
ans = 0
for i in range(2019):
  ans += (x[i]*(x[i]-1))//2
print(ans)

Submission status: Accepted

Solution code:
input = raw_input

M = 2019
s = input()
#n = len(s)
#s = int(s)

div = 10

counts = [0] * M
#m = 1

counts[0] += 1
cur = 0

m = 1
for c in reversed(s):
    cur = (int(c) * m + cur) % M
    counts[cur] += 1
    m = (m * 10) % M
    #m *= 10

out = 0
for c in counts:
    out += (c * (c-1) // 2)

print(out)

Submission status: Accepted

Solution code:
import numpy as np

s = input().strip()
t = 0
counts = np.array([0] * 2019)
counts[0] += 1
m = 1

for a  in reversed(s):
    t = (t + m * int(a)) % 2019
    counts[t] += 1
    m = m * 10 % 2019
    
print(int(np.sum(counts * (counts - 1) /2)))

Submission status: Accepted

Solution code:
M,a,t=2019,0,0
l=[0]*M
for i,c in enumerate(input()[::-1]):
  l[t]+=1
  t+=int(c)*pow(10,i,M)
  t%=M
  a+=l[t]
print(a)

Submission status: Accepted

Solution code:
A = input()

S = 0
lis = [0] * 2019
lis[0] += 1
l = len(A)+1
d = 1

for n in reversed(A):
    S += int(n)*d
    S %= 2019
    lis[S] += 1
    d *= 10
    d %= 2019

result = 0

for n in lis:
    result += (n*(n-1)//2)


print(result)

Submission status: Accepted

Solution code:
M,a,t,p=2019,0,0,1;l=[0]*M
for i in input()[::-1]:l[t%M]+=1;t+=int(i)*p;a+=l[t%M];p=p*10%M
print(a)

Submission status: Accepted

Solution code:
S = input()
 
res = [0] * 2019
res[0] = 1
 
d = 1
a = 0
 
for c in reversed(S):
    a += int(c) * d
    a %= 2019
    res[a] += 1
    d *= 10
    d %= 2019
 
ans = 0
for r in res:
    ans += r*(r-1) // 2
print(ans)

Submission status: Accepted

Solution code:
M,a,t,p=2019,0,0,1
l=[0]*M
for i in input()[::-1]:l[t]+=1;t=(t+int(i)*p)%M;a+=l[t];p=p*10%M
print(a)

Submission status: Accepted

Solution code:
M=2019
s=input()[::-1]
a=t=0
p=1
l=[0]*M
for i in s:
  l[t]+=1
  t+=int(i)*p
  t%=M
  a+=l[t]
  p=p*10%M
print(a)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

P = 2019

def main():
    S = input().rstrip()

    n = len(S)
    counts = [0] * P
    counts[0] += 1
    T = 0
    d = 1
    for s in reversed(S):
        T = (T + (d * int(s)) % P) % P
        d = (d * 10) % P
        counts[T] += 1

    ans = 0
    for c in counts:
        ans += c*(c-1)//2  # cC2
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

modCount = [1]+[0]*2018
mod = 0
dig = 1
result = 0

for i in range(len(S)):
  mod = (int(S[i:i+1])*dig+mod)%2019
  dig = (dig*10)%2019
  result += modCount[mod]
  modCount[mod] += 1

print(result)

Submission status: Accepted

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

modCount = [0]*2019
modCount[0] = 1
mod = 0
dig = 1
result = 0

for i in range(len(S)):
  mod = (int(S[i:i+1])*dig+mod)%2019
  dig = (dig*10)%2019
  result += modCount[mod]
  modCount[mod] += 1

print(result)

Submission status: Accepted

Solution code:
s=raw_input()
str="".join(reversed(s))

dict={}

dict[0]=1

ans=0

sumee=0
ans22=1


for i in str:
	x=sumee+ans22*(ord(i)-ord('0'))
	x=x%2019
	if x in dict:
		ans+=dict[x]
	if x not in dict:
		dict[x]=0
	dict[x]+=1
	sumee=x
	ans22=(ans22*10)%2019

print(ans)

Submission status: Accepted

Solution code:
str=input()
N=len(str)
a=[0]*N
a[0]=int(str[N-1])
base=10
for i in range(N-1):
    a[i+1]=(int(str[N-i-2])*base+a[i])%2019
    base*=10
    base%=2019
b=[0]*2019
b[0]=1
for i in range(N):
    b[int(a[i])]+=1
ans=0
for i in range(2019):
    if b[i]>1:
        ans+=(b[i]*(b[i]-1))/2
print(int(ans))

Submission status: Accepted

Solution code:
S = input()

res = [0] * 2019
res[0] = 1

d = 1
a = 0

for c in reversed(S):
    a += int(c) * d
    a %= 2019
    res[a] += 1
    d *= 10
    d %= 2019

ans = 0
for r in res:
    ans += r*(r-1) // 2
print(ans)