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

counter=[0]*2019
counter[0]=1
num=0
t=1
prefer=0
for i in reversed(s):
    num+=int(i)*t
    num%=2019
    t*=10
    t%=2019
    counter[num]+=1

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

Submission status: Accepted

Solution code:
from collections import Counter
l = len(S := input())
counts = Counter((n := (n + (d := d * 10 % 2019) * int(S[-i])) % 2019 if i else (n := 0 * (d := 202)) for i in range(l + 1)))
print(sum(n * (n - 1) // 2 for n in counts.values()))

Submission status: Accepted

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

counts = [0]*2019 # 剰余の余りの回数を保存
counts[0] = 1 # 0%2019を累積和として含めることを想定

num, d = 0,1 # numは余りの累積和、dはcharの桁数
'''
charに一桁ずつ取り出す。そのmod2019を考え、累積和をとる。
しかし、それぞれの数字には10の累乗がかかっているので、それについては別途dを用意してmod2019をとる
つまり、numは1桁目のmod2019、2桁目のmod2019に1桁目のmod2019を加える
'''
for char in s:
  num += int(char) * d
  num %= 2019
  d *= 10
  d %= 2019
  counts[num] += 1

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

Submission status: Accepted

Solution code:
import collections 
s = input()

n = len(s)
m = [0]
mod = 0
ten = 1
for i in s[::-1]:
  mod += (int(i)*ten)%2019
  mod %= 2019
  m.append(mod)
  ten *= 10
  ten %= 2019

count = collections.Counter(m)
print(sum([c*(c-1)//2 for c in count.values()]))

Submission status: Accepted

Solution code:
s=input()
tmpsum=0
ruiseki=[0]
dic={}
so=2019

for i in range(1,len(s)+1):
    tmpsum+=(int(s[-i])*pow(10,i-1,so)) % so
    tmpsum%=so
    ruiseki.append(tmpsum)

for rui in ruiseki:
    if rui in dic:
        dic[rui]=dic[rui]+1
    else:
        dic[rui]=1


output=0
for val in dic.values():
    output+=val*(val-1)/2

print(int(output))

Submission status: Accepted

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

t=0

x=1
cnt=[0]*2019
cnt[0]=1


for i in s:
    t += int(i)*x
    t %= 2019
    x *= 10
    x %= 2019
    cnt[t]+=1

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

print(ans)

Submission status: Accepted

Solution code:
# D - Multiple of 2019

from collections import Counter

s = input()

count = 0
counter = Counter([0])

suffix = 0
pow = 1
for i in range(len(s) - 1, -1, -1):
    suffix = (int(s[i]) * pow + suffix) % 2019
    pow = pow * 10 % 2019
    count += counter[suffix]
    counter[suffix] += 1

print(count)

Submission status: Accepted

Solution code:
# D - Multiple of 2019

from collections import Counter

s = input()

count = 0
counter = Counter([0])

suffix = [0] * (len(s) + 1)
pow = 1
for i in range(len(s) - 1, -1, -1):
    suffix[i] = (int(s[i]) * pow + suffix[i + 1]) % 2019
    pow = pow * 10 % 2019
    count += counter[suffix[i]]
    counter[suffix[i]] += 1

print(count)

Submission status: Accepted

Solution code:
s = input()

n = len(s)
mod_list = [0]*2019
mod_list[0] = 1
t = 0
keisu = 1
for i in range(n):
  t = (int(s[n-1-i])*keisu+t) %2019
  keisu = keisu*10 %2019
  mod_list[t]+= 1
count = 0
for k in range(2019):
  count += mod_list[k] * (mod_list[k]-1)//2
print(count)

Submission status: Accepted

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

ans = 0
mods = [0]
s = [int(a) for a in s[::-1]]
x = 0
for i in range(len(s)):
    x += s[i] * pow(10, i, 2019)
    mods.append(x%2019)

mods = Counter(mods)

for k in mods.keys():
    counts = mods[k]
    ans += counts * (counts-1) // 2
print(ans)

Submission status: Accepted

Solution code:
import collections as col
cnt = col.Counter()
cnt[0] += 1


s = input()
n = len(s)

num = 0
for i,s in enumerate(s[::-1]):
    num += int(s) * pow(10, i, 2019)
    cnt[num%2019] += 1

ans = 0
for key,val in cnt.items():
    ans += val*(val-1)//2

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s = input()
mod = 2019
ls = [1]+[0]*2018
ans = 0
temp=0
m=1
for i in range(len(s)):
    temp= (temp + m*int(s[-i-1]))%mod
    m=(m*10)%mod

    ls[temp] += 1

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

Submission status: Accepted

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

Submission status: Accepted

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


def solve(S: str):
    # S[i, j) % 2019 == 0となる(i, j)の数
    # S[i..n) - S[j, n) === 0 (mod 2019)
    # 累積mod c[i] = S[i:]
    n = len(S)
    c = [0] * (n + 1)  # c[i] = int(S[i:]) % 2019
    for i in reversed(range(n)):
        c[i] = (c[i + 1] + int(S[i]) * pow(10, n - 1 - i, 2019)) % 2019
    print(sum(v * (v - 1) // 2 for v in Counter(c).values()))


# 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 = next(tokens)  # type: str
    solve(S)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(int)
S=input()
S=S[::-1]
i=0
x=0
MOD=2019
for s in S:
  x+=(int(s)*pow(10,i,MOD))%MOD
  x%=MOD
  d[x]+=1
  i+=1
ans=0
for k in d.values():
  ans=ans+k*(k-1)//2
print(ans+d[0])

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(int)
S=input()
S=S[::-1]
i=1
x=0
MOD=2019
for s in S:
  x+=(int(s)*i)%MOD
  x%=MOD
  d[x]+=1
  i*=10
  i%=MOD
ans=0
for k in d.values():
  ans=ans+k*(k-1)//2
print(ans+d[0])

Submission status: Accepted

Solution code:
S = input()

from collections import defaultdict
mod = 2019
N = len(S)
D = defaultdict(int)
S = S[::-1]
ans = 0
T = 0
D[0]+=1
for i in range(N):
    s = int(S[i])*pow(10,i,mod)
    T = (T+s)%mod
    ans += D[T]
    D[T]+=1
print(ans)

Submission status: Accepted

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

ans = 0
tot = 0
from collections import defaultdict
dic = defaultdict(int)
for i in range(N):
    dic[tot] += 1
    tot += int(rS[i]) * pow(10,i,2019)
    tot %= 2019
    ans += dic[tot]

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
def main():
    S=input()
    remainders=[0]
    sub=0
    pow10=1
    for i in range(len(S)-1,-1,-1):
        remainders.append((remainders[-1]+pow10*int(S[i]))%2019)
        pow10=((pow10%2019)*(10%2019))%2019
    d=Counter(remainders)
    ans=0
    for key in d:
        ans+=(d[key]*(d[key]-1))//2
    print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

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

cum = [0] * (N+1)
for i in range(N):
    cum[i+1] = (cum[i] + (int(rS[i]) * pow(10,i,2019)) % 2019) % 2019

ans = 0
from collections import Counter
from math import factorial
c = Counter(cum)
for v in c.values():
    if v >= 2:
        ans += factorial(v) // (factorial(v-2)*2)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    S = list(map(int, list(input())))
    S = S[::-1]
    n = len(S)
    mod = 2019

    A = [0] * n
    times = 1
    for i in range(n):
        A[i] = S[i] * times % mod
        times = times * 10 % mod

    # 累積和
    R = [0] * (n + 1)
    for i in range(n):
        R[i+1] = (R[i] + A[i]) % mod
    # print(R)
    cnt = {}
    ans = 0
    for i in range(n+1):
        r = R[i] % mod
        # print(r)
        ans = ans + cnt.get(r, 0)
        # cnt.setdefault(r, 0)
        # ans = ans + cnt[r]
        cnt[r] = cnt.get(r, 0) + 1
    # print(cnt)
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    S = list(map(int, list(input())))
    S = S[::-1]
    n = len(S)
    mod = 2019

    A = [0] * n
    times = 1
    for i in range(n):
        A[i] = S[i] * times
        times = times * 10 % mod

    # 累積和
    R = [0] * (n + 1)
    for i in range(n):
        R[i+1] = (R[i] + A[i]) % mod
    # print(R)
    cnt = {}
    ans = 0
    for i in range(n+1):
        r = R[i] % mod
        # print(r)
        ans = ans + cnt.get(r, 0)
        # cnt.setdefault(r, 0)
        # ans = ans + cnt[r]
        cnt[r] = cnt.get(r, 0) + 1
    # print(cnt)
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())
 
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
 
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
 
INF = float('inf')
 
def solve():
    S = list(map(int, list(input())))
 
    S = S[::-1]
    # print(S)
    n = len(S)
    mod = 2019
 
    #
    A = [0] * (n)
    a = 1
    for i in range(n):
        A[i] = S[i] * a
        a = a * 10 % mod
    # print(A)
 
    # 累積和
    R = [0] * (n+1)
    for j in range(n):
        R[j+1] = (R[j] + A[j]) % mod
    # print(R)
 
    # 個数を数える
    cnt = {}
    ans = 0
    for l in range(0, n+1):
        r = R[l]
        ans = ans + cnt.get(r, 0)
        cnt[r] = cnt.setdefault(r, 0) + 1
    print(ans)
 
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time

def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

# https://algo-logic.info/abc158e/
def main():
    s = list(map(int, S()[::-1]))
    N = len(s)
    P = 2019
    cnts = [0] * P
    cnts[0] = 1
    sum_of_digits = 0

    for i in range(N):
        sum_of_digits += s[i] * pow(10, i, P)
        sum_of_digits %= 2019
        cnts[sum_of_digits] += 1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()
s_len = len(S)
mod_hash = {0: 1}
mod_temp = 1
mod = 0

for i in range(1, s_len + 1):
	mod = (mod + mod_temp * int(S[-i])) % 2019
	if mod in mod_hash:
		mod_hash[mod] += 1
	else:
		mod_hash[mod] = 1
	mod_temp = (mod_temp * 10) % 2019

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

def comb_count(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)

S = input()[::-1]
ans = 0

mods = [0] * 2019 #余りが0~2018
mods[0] = 1
current = 0
tmp = 1

for i in range(len(S)):
    current = int(S[i]) * tmp + current
    mod = current % 2019
    mods[mod] += 1
    tmp = tmp * 10 % 2019

for mod in mods:
    if mod > 1:
        ans += comb_count(mod, 2)

print(ans)

Submission status: Accepted

Solution code:
import math

def comb_count(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)

S = input()[::-1]
ans = 0

mods = [0] * 2019 #余りが0~2018
mods[0] = 1
current = 0
tmp = 1

for i in range(len(S)):
    current = (int(S[i]) * tmp + current)
    mod = current % 2019
    # ans += mods[mod]
    mods[mod] += 1
    tmp = tmp * 10 % 2019

for mod in mods:
    if mod > 1:
        # print(mod)
        ans += comb_count(mod, 2)

print(ans)

Submission status: Accepted

Solution code:
import math

def comb_count(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)

S = input()[::-1]
ans = 0

mods = [0] * 2019 #余りが0~2018
mods[0] = 1
current = 0
tmp = 1

for i in range(len(S)):
    current = (int(S[i]) * tmp + current) % 2019
    mod = current % 2019
    # ans += mods[mod]
    mods[mod] += 1
    tmp = tmp * 10 % 2019

for mod in mods:
    if mod > 1:
        # print(mod)
        ans += comb_count(mod, 2)

print(ans)

Submission status: Accepted

Solution code:
import math

# def comb_count(n, r):
#     return math.factorial(n) // math.factorial(r) // math.factorial(n - r)

S = input()[::-1]
ans = 0

mods = [0] * 2019 #余りが0~2018
mods[0] = 1
current = 0
tmp = 1

for i in range(len(S)):
    current = (int(S[i]) * tmp + current) % 2019
    mod = current % 2019
    ans += mods[mod]
    mods[mod] += 1
    tmp = tmp * 10 % 2019

# for mod in mods:
#     if mod > 1:
#         ans += comb_count(mod, 2)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)


S = readChar()

res = [0]*len(S)
res[-1]=int(S[-1])

d = defaultdict(int)

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


for i in res:
	d[i]+=1

ans = d[0]
for key in d:
	if d[key]>1:
		ans+=comb(d[key],2)

print(ans)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)


S = readChar()

re = [0]*len(S)
res = [0]*len(S)
res[-1]=int(S[-1])

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

d = defaultdict(int)
for i in res:
	d[i]+=1

ans = d[0]
for key in d:
	if d[key]>1:
		ans+=comb(d[key],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:
s = input()
n = len(s)
r = list(reversed(s))
x = 1
t = 0
c = [0] * 2019
ans = 0
for i in range(n):
    c[t] += 1
    t += (int(r[i]))*x
    t %= 2019
    ans += c[t]
    x = x*10%2019
   
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
import copy
#input = sys.stdin.readline
sys.setrecursionlimit(20000000)
s = input()
s = s[::-1]
n = len(s)
dp = [0]*(n+1)
k = 1
a = defaultdict(int)
a[0]+=1
for i in range(n):
  dp[i] = (dp[i-1]+int(s[i])*k)%2019
  k*=10
  k%=2019
  a[dp[i]] += 1
ans = 0
for i in a.keys():
  ans += a[i]*(a[i]-1)/2
print(int(ans))

Submission status: Accepted

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

"""
    例： S = '31415926535'
        S[3:8] = '15926535' が 2019 で割り切れるかどうか？
     <=> S[3:-1] - S[8:-1] が 2019 で割り切れるかどうか
     <=> S[3:-1] % 2019 == S[8:-1] % 2019 か
    よって、2019で割ったときの異なるあまりをそれぞれカウントすればよい
"""

mod_cnts = [0] * 2019
mod_cnts[0] = 1 # 累積和のはじめ
current_cusum, ans = 0, 0
# O(N)
d = 1
# for i in range(N):
for s in S:
    current_cusum += int(s) * d
    current_cusum %= 2019
    d = d * 10 % 2019
    mod_cnts[current_cusum] += 1

    # d *= 10 % 2019

# O(2019)
for cnt in mod_cnts:
    ans += cnt * (cnt - 1) // 2 # n_C_2 2つ選ぶ組み合わせ
 
print(ans)

Submission status: Accepted

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

counts = [0] * 2019
counts[0] = 1
#余りの数字がそれぞれ何回出たかカウント
#count[0]は「累積和的」に0%2019を考えるために1にしている

num, d = 0, 1
#numは余りの累積和、dはcharの桁数
for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1
'''
charに一桁ずつ取り出す。そのMOD2019を考え、累積和をとる
しかし、それぞれの数字には10の累乗がかかっているのでそれについては別途dを用意してMOD2019をとる
つまり、numは1桁目のMOD2019、2桁目のMOD2019に1桁目のMOD2019に加える
'''

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

print(ans) # 答えの出力

Submission status: Accepted

Solution code:
S = input()

n = len(S)

medalist = [0] * 2019
medalist[0] = 1
num = 0
mods = 1

for i in range(n):
    fig = int(S[n - i - 1])
    num = (num + fig * mods) % 2019
    medalist[num] = medalist[num] + 1
    mods = (mods * 10) % 2019

result = 0

for i in range(2019):
    m = medalist[i]
    if m != 0:
        result += m * (m - 1) / 2

print(int(result))

Submission status: Accepted

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

X=[0]
md=2019

for i,s in enumerate(S):
    X.append((X[-1]+int(s)*pow(10,i,md))%md)

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

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

# print('input >>')

S = input()
S = S[::-1] + '0'

mod = 0
mods = [0] * 2019
mods[0] += 1

i_mod = 1

for i in range(len(S)-1):
    # mods[i+1] = (int(S[i+1]) * 10 ** (i+1) + mods[i]) % 2019
    i_mod %= 2019
    mod = (int(S[i]) * i_mod + mod) % 2019
    # print(mod)
    mods[mod]+=1
    i_mod *= 10

# print(mods)

ans = 0

# counter = Counter(mods)

# for n in counter.values():
#     if n > 1:
#         ans += (n * (n-1)) // 2

# print('-----output-----')

for m in mods:
    if m > 1:
        ans += (m * (m-1)) // 2

print(ans)

Submission status: Accepted

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

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

num, d = 0, 1

for c in s:
    num += int(c)*d
    num %= mod
    d *= 10
    d %= mod
    dp[num] += 1

ans = 0
for cnt in dp:
    if cnt == 0:
        continue
    ans += cnt*(cnt-1)//2

print(ans)

Submission status: Accepted

Solution code:
#D
S = list(str(input()))
N = len(S)

U = []
for i in range(N):
    U.append(int(S[N-i-1]))


DP = [-1]*(N+1)
DP[0] = 0
now = 0
pnow = 1
for i,u in enumerate(U):
    pnow*=10
    pnow%=2019
    now+=int(u)*pnow
    now%=2019
    DP[i+1] = now
    
#print(DP)
tyo = [0]*2019
for dp in DP:
    tyo[dp]+=1

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

Submission status: Accepted

Solution code:
from collections import defaultdict


def resolve():
    s = input()

    cnt = defaultdict(int)
    cnt[0] += 1
    tmp = 0
    for i, c in enumerate(s[::-1]):
        c = int(c)
        tmp = (tmp + c * pow(10, i, 2019)) % 2019
        cnt[tmp] += 1

    ans = sum(c * (c - 1) // 2 for c in cnt.values())
    print(ans)


resolve()

Submission status: Accepted

Solution code:
from collections import *
s = input()
p = 2019
c = Counter()
c[0] += 1
v = r = 0
k = 1
for i in s[::-1]:
    v += int(i)*k
    v %= p
    r += c[v]
    c[v] += 1
    k *= 10
    k %= p
print(r)

Submission status: Accepted

Solution code:
from collections import Counter
s = input()[::-1]
T = [0]*(len(s)+1)
digit = 1

for i in range(1,len(s)+1):
    T[i] = (T[i-1]+digit*int(s[i-1]))
    T[i] = T[i] % 2019
    digit = digit * 10
    digit = digit % 2019

S = Counter(T)
ans = 0
for i in S.values():
    ans+=(i*(i-1))//2

print(ans)

Submission status: Accepted

Solution code:
s = input()[::-1]
length = len(s)
a = [0] * length
d = [0] * length
ans = [0] * 2019
x = 10

a[0] = int(s[0])
d[0] = a[0]
ans[d[0]] += 1

for i in range(1, length):
    a[i] = int(s[i]) * x % 2019
    d[i] = (d[i-1] + a[i]) % 2019
    ans[d[i]] += 1
    x = x * 10 % 2019

ans_c = [i for i in ans if i != 0]

print(int(sum([ans_c[i] * (ans_c[i]-1) for i in range(len(ans_c))]) / 2) + ans[0])

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

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

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

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

print(ans)

Submission status: Accepted

Solution code:
s=list(input())[::-1] # 10進数で位を上げていくために反転させる
n=len(s)
amari_lis=[0]*2019 # 
amari_lis[0]=1 # 2019で割り切れる場合、組合せ総数は (n+1)C2 となるため（その他はnC2でOK）

num=0
kurai=1
for keta in s:
    num+=int(keta)*kurai
    num%=2019
    amari_lis[num]+=1
    kurai*=10
    kurai%=2019 # amari_lisが 0~2019 のため、位の数も 2019 で割った余りで考える

ans=0
for i in amari_lis:
    ans+=i*(i-1)/2 # nC2の計算, 余りが同じものを引けば 0⇒2019で割れると言える（組合せ数を逐次追加することで総数算出）

print(int(ans))

Submission status: Accepted

Solution code:
y=2019
a=[0]*y
k=1
r=p=0
for c in input()[::-1]:
    a[p]+=1
    p-=int(c)*k
    p%=y
    r+=a[p]
    k*=10
    k%=y
print(r)

Submission status: Accepted

Solution code:
import numpy as np
s = input()
y = 2019
dp = np.zeros(y, dtype="int64")
tmp = np.zeros(y, dtype="int64")
k = 1
r = 0
for c in s[::-1]:
    i = int(c)*k%y
    tmp[i:] = dp[:y-i]
    tmp[:i] = dp[y-i:]
    tmp[i] += 1
    dp, tmp = tmp, dp
    r += dp[0]
    k *= 10
    k %= y
print(r)

Submission status: Accepted

Solution code:
a=input()
num=len(a)
mod_map={0:1}
moji_int=0
Sn=[0]*(num+1)
tens=[1]*(num+1)
for i in range(-1,-num-1,-1):
    tens[-i]=tens[-i-1]*10%2019
    tmp=int(a[i])*(tens[-i-1])%2019
    Sn[-i]=(Sn[-i-1]+tmp%2019)%2019
    mod=Sn[-i]
    if mod not in mod_map:
        mod_map[mod]=1
    else:
        mod_map[mod]+=1

res=0
for i in mod_map.values():
    res+=int(i*(i-1)/2)
print(res)

Submission status: Accepted

Solution code:
a=input()
num=len(a)
mod_map={0:1}
moji_int=0
Sn=[0]*(num+1)
tens=[1]*(num+1)
for i in range(-1,-num-1,-1):
    tens[-i]=tens[-i-1]*10%2019
    tmp=int(a[i])*(tens[-i-1])
    Sn[-i]=(Sn[-i-1]+tmp%2019)%2019
    mod=Sn[-i]
    if mod not in mod_map:
        mod_map[mod]=1
    else:
        mod_map[mod]+=1

res=0
for i in mod_map.values():
    res+=int(i*(i-1)/2)
print(res)

Submission status: Accepted

Solution code:
a=input()
num=len(a)
mod_map={0:1}
moji_int=0
Sn=[0]*(num+1)
tens=[1]*(num+1)
for i in range(-1,-num-1,-1):
    tens[-i]=tens[-i-1]*10%2019
    tmp=int(a[i])*(tens[-i-1])
    Sn[-i]=(Sn[-i-1]+tmp)%2019
    mod=Sn[-i]
    if mod not in mod_map:
        mod_map[mod]=1
    else:
        mod_map[mod]+=1

res=0
for i in mod_map.values():
    res+=int(i*(i-1)/2)
print(res)

Submission status: Accepted

Solution code:

a=list(reversed(input()))
num=len(a)
mod_map={0:1}
moji_int=0
Sn=0
tens=1
for i in a:
    tmp=int(i)*(tens)
    Sn=(Sn+tmp)%2019
    mod=Sn
    tens=tens*10%2019
    if mod not in mod_map:
        mod_map[mod]=1
    else:
        mod_map[mod]+=1


res=0
for i in mod_map.values():
    res+=int(i*(i-1)/2)
print(res)

Submission status: Accepted

Solution code:
a=reversed(input())
#num=len(a)
mod_list=[1]+[0]*2019
moji_int=0
Sn=0
tens=1
for i in a:
    tmp=int(i)*(tens)
    Sn=(Sn+tmp)%2019
    mod=Sn
    tens=tens*10%2019
    mod_list[mod]+=1
res=0
for i in mod_list:
    res+=int(i*(i-1)/2)
print(res)

Submission status: Accepted

Solution code:
def main():
    S = input()
    # S = "1" * 200000
    S = S[::-1]

    x = 1
    tot = 0
    cnt = [0] * 2019
    ans = 0

    for i in range(len(S)):
        # print("-----")
        # print(f"i: {i}")
        # print(f"tot: {tot}")
        # print(f"S[i]: {S[i]}")
        # print(f"x: {x}")
        # print(f"cnt: {cnt}")
        # print(f"cnt[tot]: {cnt[tot]}")
        # print(f"ans: {ans}")

        cnt[tot] += 1
        tot = (tot + (int(S[i]) * x)) % 2019
        ans += cnt[tot]
        x = (x * 10) % 2019
    
    # print("-----")
    # print(f"i: {i}")
    # print(f"tot: {tot}")
    # print(f"S[i]: {S[i]}")
    # print(f"x: {x}")
    # print(f"cnt: {cnt}")
    # print(f"cnt[tot]: {cnt[tot]}")
    # print(f"ans: {ans}")
    
    print(ans)


if __name__ == '__main__':
    main()

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:
from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------

a = input().strip()
n = len(a)
dp = [0]*(n+1)
mp  = defaultdict(int)
dp[n-1] = int(a[n-1])
dp[n] = 0
mp[dp[n]]+=1
mp[dp[n-1]]+=1
for i in range(n-2,-1,-1):
    dp[i] = (dp[i+1]+(int(a[i])*pow(10,(n-i-1),2019))%2019)%2019
    mp[dp[i]]+=1
res =0
#print(dp)
#dp.sort()
#print(dp)
#print(mp)
for i,v in mp.items():
    res+=v*(v-1)//2
print(res)

Submission status: Accepted

Solution code:
from collections import Counter
s = input()[::-1]
mod = 2019

x = [0]

for i, j in enumerate(s):
    x.append((x[-1] + int(j) * pow(10,i, mod))%mod)

C = Counter(x)
ans = 0

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

Submission status: Accepted

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

a = [0]*2019
a[0] = 1
count = 0
val = 1
current = 0
for c in s:
    current = (current + val * int(c)) % 2019
    count += a[current%2019]
    a[current%2019] += 1
    val = val * 10 % 2019

print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# Problem D - Multiple of 2019

from collections import Counter

# input
S = input()
s_len = len(S)

# initialization
ans = 0

# mod count
nums_2019 = [0]*2019
nums_2019[0] = 1
tmp_num = 0
for i in range(s_len-1, -1, -1):
    tmp_num += int(S[i]) * pow(10, s_len-i-1, 2019)
    nums_2019[tmp_num%2019] += 1

# output
for m_c in nums_2019:
    if m_c>=2:
        ans += m_c * (m_c-1) // 2
print(ans)

Submission status: Accepted

Solution code:
s = input()[::-1]
#sは文字列 逆向きにしている
sum_of_digits = 0
 
cnts = [0] * 2019
 
cnts[0] = 1
 
d = 1
 
for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10         #dを１０倍
    d %= 2019       #dを2019で割る（2019は10と素なので意味はないかも）
    cnts[sum_of_digits] += 1
    #cntは2019個ある　modの値が同じごとに個数を計算して足したもの
 
ans = 0
    
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2  
                    #cnt conbination 2
                    #mod ごとに m(m − 1)/2
        
#(i, j)が条件をみたすのはTi−1 == Tj (mod2019)のとき
#Ti−1 - Tj == 0 (mod2019) と等価 Ti−1 == Tj (mod2019)
 
print(ans)