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)

power = [0]*(n+1)
power[-1] = 1
x = 1

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

cnt = [0]*2020

x=0
for i in range(n, 0,-1):
	x = (x+int(s[i-1])*power[i])%2019
	mod19[i] = x
	cnt[x]+=1
	
# ~ print(power)
# ~ print(mod19)
	
ans = 0

for i in range(2020):
	x = cnt[i]
	ans+= x*(x-1)//2
	# ~ if x>0: print(i, x)

	
print(ans+cnt[0])

Submission status: Accepted

Solution code:
from itertools import permutations, accumulate
mod = 2019

a = list(map(int,input()))
n = len(a) #入力の桁数

for i in range(n):
    a[i] *= pow(10,n-i-1,mod) #pow(a,b)==a^b べき乗
    
s = [0]+list(accumulate(a)) #accumulate([1,2,3,4,5]) --> 1 3 6 10 15
d = [0]*mod
ans = 0
for i in s:
    j = i%mod
    ans += d[j]
    d[j] += 1
print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
n = input()
l = len(n)
s = [0] * 2020
m = [0] * (l+1)
m[0] = 1
s[0] = 1
for i in range(1, l+1):
    m[i] = (m[i-1]*10) % 2019
tmp = 0
n = list(n)[::-1]
for i in range(len(n)):
    #print(i, n[-1-i], m[i])
    tmp = (tmp + int(n[i])*m[i]) % 2019
    # print(tmp)
    s[tmp] += 1
su = 0
for i in s:
    if i > 1:
        # print("#", i)
        su += i * (i - 1)//2
print(su)

Submission status: Accepted

Solution code:
INT_MAX=10**11+7
MOD=10**9+7
def INPUT():return list(int(i) for i in input().split())
def LIST_1D_ARRAY(n):return [0 for _ in range(n)]
def LIST_2D_ARRAY(m,n):return [[0 for _ in range(n)]for _ in range(m)]
#=======================================================================
s=input()
digits=list(int(i) for i in s)
n=len(s)
powermod=[0]*2019
powermod[0]=1
pow10=1
num=0
ans=0
for digit in reversed(digits):
    num+=digit*pow10
    rem=num%2019
    ans+=powermod[rem]
    pow10*=10
    powermod[rem]+=1
    num=rem
    pow10%=2019
print(ans)

Submission status: Accepted

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

target = 2019

# s = reversed(original)

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

num, d = 0, 1
digit = 1
mod = 0
for c in original:
    # val = int(c) * digit
    # currentMod = val % target
    # # mod = (currentMod + mod) % target
    # digit *= 10
    #
    # counts[mod] += 1
    num += int(c) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1

# print(sum(results.values()))

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

print(ans)  # 答えの出力

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:
S = input()
n = len(S)
dp = [0 for _ in range(n+1)]
count = [0 for _ in range(2019)]
count[0] = 1
p=1
for i in range(1,n+1):
    dp[i] = (dp[i-1]+int(S[n-i])*p) % 2019
    p = p*10%2019
    count[dp[i]] += 1

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

print(int(sum(count)))

Submission status: Accepted

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

r = 0
C = [0 for _ in range(MOD)]
C[0] = 1

for i,s in enumerate(S):
    r += int(s)*pow(10,i,MOD)
    r %= MOD
    C[r] += 1

a = 0
for c in C:
    a += c*(c-1)/2

print(int(a))

Submission status: Accepted

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

dp = [0]*2019
dp[0]=1
total = 0
a = 1

for i in list(s):
  total += int(i)*a
  total %= 2019
  dp[total] += 1
  a *= 10
  a %= 2019
count=0
  
for i in range(2019):
    count += dp[i]*(dp[i]-1)//2
 
print(count)

Submission status: Accepted

Solution code:
def main():
    S=input()
    P=2019
    ans=0
    
    count=[0]*P
    count[0]=1
    u=0
    
    for i,s in enumerate(reversed(S)):
        u=(int(s)*pow(10,i,P)+u)%P
        ans+=count[u]
        count[u]+=1
    print(ans)
    

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
N = 2019


def main():
    S = input()
    mod = [0] * N
    ans = 0
    for c in S:
        nxt = [0] * N
        x = int(c)
        for i in range(N):
            nxt[(i*10+x) % N] += mod[i]
        nxt[x] += 1
        ans += nxt[0]
        mod = nxt
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def solve(S: str):
    T = [0 for _ in range(len(S) + 1)]
    for i in range(len(S) - 1, -1, -1):
        T[i] = (T[i+1] + int(S[i]) * pow(10, len(S) - 1 - i, 2019)) % 2019
    # T = [int(S[i:]) % 2019 if i < len(S) else 0 for i in range(len(S) + 1)]
    M = [0 for _ in range(2019)]
    # M = [T.count(i) for i in range(2019)]
    for t in T:
        M[t] += 1
    ct = 0
    for m in M:
        ct += m * (m - 1) / 2

    print(int(ct))
    return


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
# s=input()
#https://atcoder.jp/contests/abc158/tasks/abc158_e p=2019 copype
P=2019

# N,P=map(int,input().split());
S,a,i,j,c=input(),0,0,1,[1]+[0]*P
if 10%P:
	for v in S[::-1]:i,j=(i+int(v)*j)%P,j*10%P;a+=c[i];c[i]+=1
else:
	for v in S:
		i+=1
		if int(v)%P<1:a+=i
print(a)

#honto???

Submission status: Accepted

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

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

m = 2019
cnt = [0] * m
cnt[0] = 1
total = 0
x = 1
ans = 0

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# import sys 
# import os
# path = os.path.join(os.getcwd(),'input.txt')
# input = open(path).readline

import numpy as np
S = input()
cand = np.zeros(2019,dtype=int)
rem = 0
order = 1
mod = 2019
for s in S[::-1]:
    rem += (int(s)*order)%mod
    rem %= mod
    cand[rem] +=1
    order *= 10
    order %=mod
ans = cand[0]
cand = cand[cand>1]
for c in cand:
    ans += c*(c-1)/2
print(int(ans))

Submission status: Accepted

Solution code:
from collections import Counter

s=input()[::-1]
ans=0
lst=[0]
num=0
p=1
for i in s:
    lst.append((int(i)*p+lst[-1])%2019)
    p=p*10%2019

ans=sum(x*(x-1)//2 for x in Counter(lst).values())
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

##### dict の for文 #####
# for k, v in d.items():
#     print(k, v)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	S = inputStr()
	S = S[::-1]

	dol = {0:1}
	tmptmp = 0
	kinou = 0
	for i,val in enumerate(S):

		if tmptmp == 0:
			tmptmp = 1
		else:
			tmptmp = tmptmp * 10 % 2019
		tmp = (int(val) * tmptmp) % 2019
		tmp = (tmp + kinou) % 2019
		kinou = tmp

		if tmp in dol:
			dol[tmp] += 1
		else:
			dol[tmp] = 1

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

	#print(dol)
	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Accepted

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

tmp_amari = [0]*2019

#amari = 0
num = 0
order = 1
for i in s:
    num += int(i)*order
    num %= 2019
    #print(num)
    tmp_amari[num] += 1
    order *= 10
    order %= 2019
    #print(order)

tmp_print = [i for i in tmp_amari if i > 0]
#print(tmp_print)

ans = 0
ans += tmp_amari[0]

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	s = input()[:-1][::-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) # 答えの出力

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:

"""
：余りの等しい物をカウントし、その累積和
：Aの余りとBの余り(mod 2019)が等しい場合
　A-Bは2019の倍数である
：計算量を抑えるため各項と１０の指数乗は分けて計算する
：
"""

import sys
input=sys.stdin.readline
s = input()[:-1][::-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:
def main():
    s=list(input())[::-1]
    ans,tot,x,m=0,0,1,2019
    cnt=[0]*m
    n=len(s)
    for i in range(n):
        cnt[tot] += 1
        tot += int(s[i])*x
        tot %= m
        ans += cnt[tot]
        x = x*10%m
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

arr = [0]*2019
arr[0] += 1
count = 0
dig = 1
r = 0

for i in range(0,n):
  r = (r + int(st[i]) * dig) % 2019
  arr[r] += 1
  dig = dig * 10 % 2019

for i in arr:
  count += i*(i-1)//2;

print(count)

Submission status: Accepted

Solution code:
def main():
    A = input()[::-1]
    A = "0" + A
    # lis_num = [int(s) for s in A]

    # print(lis_num)

    # S = [0] * len(lis_num)
    S = [0] * len(A)
    cnt = [0] * 2019
    cnt[0] = 1

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

    # print(S)

    # for i in S:
    #     cnt[i % 2019] += 1

    ans = 0

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
S = input()[::-1]
N = len(S)
sum_of_mod = [0] * 2019
sum_of_mod[0] += 1
digit = 1
now = 0
for i in range(N):
    now = int(S[i])*digit + now
    now %= 2019
    digit *= 10
    digit %= 2019
    sum_of_mod[now] += 1

ans = 0
for i in range(2019):
    ans += sum_of_mod[i] * (sum_of_mod[i]-1) // 2
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
import numpy as np

def solve(S):
	M = 2019
	t = 1
	ans = 0
	c = np.zeros(M, dtype=np.int64)
	c[0] = 1
	r = 0
	for d in S:
		r = (d * t + r) % M
		ans += c[r]
		c[r] += 1
		t = t * 10 % M
	return ans



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

if __name__ == '__main__':
	import sys
	if sys.argv[-1] == 'ONLINE_JUDGE':
		cc_export()
		exit(0)
	from my_module import solve
	S = sys.stdin.buffer.readline().decode('utf-8').rstrip()
	S = np.array([int(d) for d in S[::-1]], dtype=np.int32)
	print(solve(S))

Submission status: Accepted

Solution code:
import sys
import numba
import numpy as np
S = sys.stdin.buffer.readline().decode('utf-8').rstrip()
S = np.array([int(d) for d in S[::-1]], dtype=np.int32)

@numba.njit(numba.i8(numba.typeof(S)), cache=True)
def solve(S):
	M = 2019
	t = 1
	ans = 0
	c = np.zeros(M, dtype=np.int64)
	c[0] = 1
	r = 0
	for d in S:
		r = (d * t + r) % M
		ans += c[r]
		c[r] += 1
		t = t * 10 % M
	return ans

print(solve(S))

Submission status: Accepted

Solution code:
s=input()
r=set()
last=0
power=1
d={0:0}
total=0
rem=0
for i in range(len(s)-1,-1,-1):#handling of 0's as n and rem
    n=int(s[i])*power+rem
    power*=10
    power=power%2019
    rem=n%2019
    if rem in d.keys():
        d[rem]+=1
    else:
        d[rem]=1
    total+=d[rem]-1
print(total+d[0])

Submission status: Accepted

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

n = 0
d = 1

for s in S:
    n = n%2019 + (int(s)*d)%2019
    tmp = n%2019
    rem[tmp] += 1
    d *= 10
    d %= 2019
    
ans = 0
for i in rem:
    ans += ((i*(i-1))//2)

print(ans+rem[0])

Submission status: Accepted

Solution code:
#!python3

# input
S = input()


def main():
    n = len(S)
    p = [None] * n
    p[0] = 1
    for i in range(1, n):
        p[i] = (p[i - 1] * 10) % 2019
    
    d = {i: 0 for i in range(2019)}
    d[0] = 1
    ans = 0
    x = 0
    for i in range(n):
        x = (x + int(S[n - i - 1]) * p[i]) % 2019
        ans += d[x]
        d[x] += 1
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
s=input()
b=[0]*2019
b[0]=1
now=0
m=2019
c=1
ans=0
for i in range(len(s)-1,-1,-1):
    now+=int(s[i])*c
    now=now%m
    c=c*10
    ans=ans+b[now]
    b[now]=b[now]+1
    c=c%m

print(ans)

Submission status: Accepted

Solution code:
s = input()[::-1]
v = 0
mods = [ 0 for i in range(2019) ]
mods[0] = 1
d = 1

for c in s:
    v += int(c) * d
    v %= 2019
    d *= 10
    d %= 2019
    mods[v] += 1

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

print(ans)

Submission status: Accepted

Solution code:
S = input()[::-1]
N = len(S)
amari = [0 for i in range(2019)]
before = int(S[0])
amari[before] += 1
S = S[1::]
keta = 1
for i in S:
    i = int(i)
    keta = (keta * 10) % 2019
    x = (keta * i + before) % 2019
    amari[x] += 1
    before = x
ans = amari[0]
for i in amari:
    ans += i * (i - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
s = input()[::-1] # 右からn桁の数についてループを回していきたいので、文字列を反転させる

sum_of_digits = 0 # 余りの値
cnts = [0] * 2019 # 余りの値ごとに余りが同じ値の数を格納する変数。2019で割る場合、余りは0~2018までの2019通りあるので、リストの長さは2019
cnts[0] = 1 # ※1
d = 1 # sum_of_digitsの計算に使う10の累乗値

# まず余りの値ごとに余りが同じ値の数を数える
for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019 # ※2
    cnts[sum_of_digits] += 1

# 次に余りの値ごとにその組み合わせを計算し、足し合わせる
ans = 0
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
s, count, m, pow10, ans = input(), [0 if i else 1 for i in range(2019)], 0, 1, 0
for c in reversed(s):
    m = (m + (ord(c) - ord('0')) * pow10) % 2019
    pow10 = pow10 * 10 % 2019
    ans += count[m]
    count[m] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

import collections
s = [int(c) for c in input()]
tmp = 1
mod = 0
count = collections.defaultdict(int)
for i,num in enumerate(s[::-1]):
    mod = (tmp * num + mod) % 2019
    count[mod] += 1
    tmp *= 10
    tmp %= 2019
count[0] += 1
print(sum((item*(item-1)//2 for item in count.values())))

Submission status: Accepted

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

m = 0
d = 1
cnt = [0] * 2019

for c in s:
	m += int(c) * d
	m %= 2019
	d *= 10
	d %= 2019
	cnt[m] += 1

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

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


def read():
    S = list(input())
    return S,


class ModInt(int):
    
    MOD = 10**9+7

    def __new__(cls, x, *args, **kwargs):
        return super().__new__(cls, x % ModInt.MOD)

    def __add__(self, other):
        return ModInt(super().__add__(other) % ModInt.MOD)

    def __radd__(self, other):
        return ModInt(super().__radd__(other) % ModInt.MOD)

    def __mul__(self, other):
        return ModInt(super().__mul__(other) % ModInt.MOD)

    def __rmul__(self, other):
        return ModInt(super().__rmul__(other) % ModInt.MOD)

    def __pow__(self, other, *args):
        return ModInt(super().__pow__(other, ModInt.MOD))

    def __rpow__(self, other, *args):
        raise NotImplementedError()

    def __truediv__(self, other):
        raise NotImplementedError()

    def __floordiv__(self, other):
        raise NotImplementedError()

    def __rtruediv__(self, other):
        raise NotImplementedError()

    def __rfloordiv__(self, other):
        raise NotImplementedError()


def solve(S, MOD=2019):
    N = len(S)
    S = list(reversed(S))
    T = [ModInt(0) for i in range(N+1)]
    ModInt.MOD = 2019
    
    mul = ModInt(1)
    for i in range(N):
        T[i+1] = T[i] + int(S[i]) * mul
        mul *= 10
    
    # T[i] == T[j] (mod 2019) となる(i, j)の組を列挙
    # <=> 0<=T[i]<2019 より、T[i]の出現数を計数すれば求められる
    # nC2 = (n * n-1) // 2
    ans = 0
    for k, v in Counter(T).most_common():
        iv = int(v)
        if iv >= 2:
            ans += v * (v-1) // 2
    return ans

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

S = list(map(int, list(input())))
num = 0
dict = [0 for i in range(2019)]
dict[0] = 1
ans = 0

for i , n in enumerate(S[::-1]):
    num += n * pow(10,i,2019)
    dict[num % 2019] += 1

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

S = list(map(int, list(input())))
num = 0
dict = {}
dict[0] = 1
ans = 0

for i , n in enumerate(S[::-1]):
    num += n * pow(10,i,2019)
    cand = num % 2019
    if cand in dict.keys():
        dict[cand] += 1
    else:
        dict[cand] = 1

for key in dict.keys():
    ans += dict[key] * (dict[key] - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
nums = [int(c) for c in str(n)]
nums.reverse()
a = [0]*2019
a[0] = 1
now = 0
pow10 = [1]*len(nums)
for i, num in enumerate(nums):
    if i < len(nums)-1:
        pow10[i+1] = pow10[i]*10 % 2019
for i, num in enumerate(nums):
    now = (now+num*pow10[i]) % 2019
    a[now] += 1
sum = 0
for i in range(2019):
    sum += a[i]*(a[i]-1)//2
print(sum)

Submission status: Accepted

Solution code:
#import sys
from collections import deque
#def input():
#    return sys.stdin.readline()[:-1]

S = deque(map(int, list(input())))
num = 0
dict = {}
dict[0] = 1
ans = 0

for i in range(len(S)):
    num += S.pop() * pow(10,i,2019)
    cand = num % 2019
    if cand in dict.keys():
        dict[cand] += 1
    else:
        dict[cand] = 1

for key in dict.keys():
    ans += dict[key] * (dict[key] - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input():
    return sys.stdin.readline()[:-1]

S = deque(map(int, list(input())))
num = 0
dict = {}
dict[0] = 1
ans = 0

for i in range(len(S)):
    num += S.pop() * pow(10,i,2019)
    cand = num % 2019
    if cand in dict.keys():
        dict[cand] += 1
    else:
        dict[cand] = 1

for key in dict.keys():
    ans += dict[key] * (dict[key] - 1) // 2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections

mod = 2019

def main():
    S = list(input())
    lenS = len(S)
    Smod2019 = [0] * lenS
    tmp = 0
    for i in range(lenS):
        tmp += (pow(10, i, mod)*int(S[-(i+1)]))%mod
        Smod2019[i] = tmp%mod
    
    cnt = collections.Counter(Smod2019)
    cntitems = cnt.items()
    ans = 0
    #print(cntitems)
    for c in cntitems:
        if c[0] == 0:
            ans += c[1]
        ans += (c[1]*(c[1]-1))//2
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
'''
[point 1]
1817181712114 の部分 "18171"について考える...

    181710000 / 10000 ≡ 0 (MOD 2019) ならば、2019の倍数
    181710000 ≡ 0 (MOD 2019) でよい

[point 2]
    181710000
    =
    181712114
    -
         2114

    なので、特定区間の値 は 累積和の差 から瞬時に求められる。
    さらに、181710000 ≡ 0 (MOD 2019) を考えると、

    0 ≡ 181712114 - 2114
    → 181712114 ≡ 2114

    となる。
    結局の所、MOD2019において合同な累積和のペアの数の数え上げ。
'''

from collections import defaultdict

def gen_10exp_mod(n, mod):
    a = 1
    yield a
    for _ in range(1, n):
        a = (a*10) % mod
        yield a

def main():
    MOD = 2019
    S = input()[::-1]
    # 桁ごとの実際の値を計算 (MOD)
    A = [int(s)*n % MOD for s, n in zip(S, gen_10exp_mod(len(S), MOD))]
    # 累積和を計算
    ACC = [0]
    for a in A:
        ACC.append((ACC[-1] + a) % MOD)
    # ペア数え上げ
    d = defaultdict(int)
    for acc in ACC:
        d[acc] += 1
    ans = sum(v*(v-1)//2 for v in d.values())
    print(ans)


main()

Submission status: Accepted

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

dp = [0]*2019
now_sum = 0
ten_times = 1

for ch in s_reverse:
    now_sum = (now_sum + int(ch)*ten_times) % 2019
    ten_times = (ten_times * 10) % 2019
    dp[now_sum] += 1

ans = dp[0]
for i_dp in dp:
    ans += i_dp*(i_dp-1)//2

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
M = 2019

S = list(input())
s_size = len(S)

S.reverse()
x = 1
tot = 0
ans = 0

cnt_list = [0 for i in range(M)]

for i in range(s_size):
	cnt_list[tot] += 1
	tot += (ord(S[i])-ord('0'))*x
	tot %= M
	ans += cnt_list[tot]
	x = x*10%M

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    S = input()[::-1]
    L = len(S)
    dp = [0] * 2019
    wk = 0
    r = 1
    for i in range(L):
        wk += int(S[i])*r
        wk %= 2019
        r *= 10
        r %= 2019
        dp[wk] += 1
    ret = dp[0]
    for i in range(2019):
        ret += dp[i]*(dp[i]-1)//2
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S = list(reversed(input()))

length = len(S)

a = [0]*length
for i in range(length):
    pickup = int(S[i])
    a[i] = pickup*pow(10, i, 2019)

b = [0]*(length+1)
for i in range(1, length+1):
    b[i] = (b[i-1] + a[i-1]) % 2019
cnt, ans = [0] * 2019, 0
for x in b:
    ans += cnt[x]
    cnt[x] += 1

print(ans)

Submission status: Accepted

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