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

Submission status: Accepted

Solution code:
S = input()
a = len(S)
mod = 0
ten = 1
L = [0]*2019 #余りの列
L[0] = 1
for i in range(a-1,-1,-1):
    mod = (int(S[i])*(ten)+mod) %2019
    L[mod] += 1
    ten = (ten*10)%2019
ans = 0
for i in L:
  ans += i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
s = input()[::-1]
c = [0] * 2019
c[0] = 1
mod = 0
ten = 1
ans = 0

for i in s:
    mod = (mod + int(i) * ten) % 2019
    ten = ten * 10 % 2019
    c[mod] += 1

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

print(ans)

Submission status: Accepted

Solution code:
s = input()[::-1]
l = len(s)
c = [0] * 2019
c[0] = 1
ten = 1
mod = 0
ans = 0

for i in range(l):
    mod = (mod + int(s[i]) * ten) % 2019
    ten = ten * 10 % 2019
    c[mod] += 1

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

print(ans)

Submission status: Accepted

Solution code:
s = input()
l = len(s)
t = [0] * l
t[l - 1] = int(s[l - 1])
m = [0] * 2019
m[0] = 1
m[int(s[l - 1])] = 1
ten = 10
ans = 0

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s=input()
n=len(s)
a=[0]*2019
a[0]=1
k=0
ans=0
mod=1
for i in range(n-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:
S = input() [::-1]
ans = 0
mod = 0
ten = 1
count = [0]* 2019
count[0] = 1
for i in range(len(S)):
    mod = (mod + int(S[i]) * ten) % 2019
    ten = ten*10 % 2019
    count[mod] += 1
for c in count:
    ans += c*(c-1)//2
print(ans)

Submission status: Accepted

Solution code:
s = input()
p = 2019
mods = [0] * p
mods[0] = 1
current = 0
base = 1
cnt = 0

for c in map(int, s[::-1]):
    current = (current + base * int(c)) % p
    base = base * 10 % p
    mods[current] += 1

print(sum(el*(el-1)//2 for el in mods))

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

S = input()

L = int(S)
S = S[::-1]
cnt = defaultdict(int)

tmp = 0
answer = 0
for i, s in enumerate(S):
    tmp = (tmp + int(s) * pow(10, i, 2019)) % 2019
    #print(tmp)
    if tmp % 2019 == 0:
        answer += cnt[0] + 1
    else:
        answer += cnt[tmp % 2019]
    cnt[tmp % 2019] += 1
    #print(tmp, answer)

print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict
import random

S = input()
n = len(S)

mp = defaultdict(int)
mp[0] += 1
x = 0
y = 1
for i, s in enumerate(reversed(S)):
    x = (x + int(s) * y) % 2019
    y = (y * 10) % 2019
    mp[x] += 1

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

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit, i8


# @njit(i8[:](i8,i8,i8[:]))
@njit
def loof(a,N):
    M = np.zeros(2019,dtype=np.int16)
    M[0] += 1
    T = 0
    r = 1
    T += a[-1] * r
    T %= 2019
    M[T] += 1
    for i in range(N-2,-1,-1):
        r *= 10
        r %= 2019
        T += a[i] * r
        T %= 2019
        M[T] += 1
    return M


# @njit
# def pow_mod(a,n,mod):
#     memo = np.array([1])
#     if n >= 1:
#         for i in range(n-1):
#             memo = np.append(memo,memo[-1]*a%mod)
#         return memo
#     else:
#         return memo[0]


def main():
    S = input().rstrip()
    S = list(map(int,list(S)))
    a = np.array(S)

    N = len(a)

    # memo = pow_mod(10,N,2019)
    M = loof(a,N)

    res = 0

    for m in M:
        res += m * (m-1) // 2

    print(res)


main()

Submission status: Accepted

Solution code:
S = input()

S = reversed(S)

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

for (i, s) in enumerate(S):
    cnt[tot] += 1
    tot += int(s)*x
    tot %= 2019
    ans += cnt[tot]
    x = x * 10 % 2019

print(ans)

Submission status: Accepted

Solution code:
s = list(input())
mod = 2019
tot = [0]
ans = 0
dp = [0 for _ in range(2020)]
dp[0] = 1
for i in range(len(s)):
    nx = tot[i] + int(s[i])*(pow(10,(len(s)-i),mod))
    nx %= mod
    if dp[nx] != 0:
        ans += dp[nx]
    dp[nx] += 1
    tot.append(nx)
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    from collections import defaultdict
    s = input()
    n = len(s)
    d = defaultdict(int)
    d[0] += 1
    j = 0
    for i in range(1, n + 1):
        j += int(s[-i]) * pow(10, i - 1, 2019)
        j %= 2019
        d[j] += 1

    def calc(x): return x * (x - 1) // 2
    ans = 0
    for v in d.values():
        ans += calc(v)
    print(ans)


if __name__ == '__main__':
    resolve()

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

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

Submission status: Accepted

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

def solve(S: int):
    S = list(map(int, list(str(S))))
    count = collections.defaultdict(int)

    count[0] = 1
    tmp = ''
    prev_modulo = 0
    for idx, s in enumerate(S[::-1]):
        prev_modulo = (s * pow(10, idx, 2019) + prev_modulo) % 2019
        count[prev_modulo] += 1

    result = 0
    for k, v in count.items():
        result += v * (v-1) // 2
    print(result)
    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
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def get_modulos():
    modulos = []
    for i in range(224):
        modulos.append(10**i%2019)
    return modulos

def count_substring(s):
    found_remainder = defaultdict(int)
    current_mod = 0
    found_remainder[0] = 1

    output = 0

    modulos = get_modulos()
    for i in range(len(s)-1,-1,-1):
        digit = s[i]
        current_mod =  (int(digit)*modulos[(len(s)-1-i)%224] % 2019 + current_mod) % 2019
        # print(i, current_mod)
        output += found_remainder[current_mod]
        found_remainder[current_mod] += 1
    #print(dict(found_remainder))

    return output

s = input()
print(count_substring(s))

Submission status: Accepted

Solution code:
import numpy as np

s = input()[::-1]
length = len(s)
a = np.zeros(length, dtype=int)
d = np.zeros(length, dtype=int)
ans = np.zeros(2019, dtype=int)
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 = ans[np.nonzero(ans)]

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

Submission status: Accepted

Solution code:
# 解説AC
S = input()
N = len(S)

cnt = [0] * 2019

cnt[0] = 1

ans = 0
e = 1; cur = 0
for s in reversed(S):
    cur = (cur + int(s) * e) % 2019

    ans += cnt[cur]

    e = (e * 10) % 2019
    cnt[cur] += 1

print(ans)

Submission status: Accepted

Solution code:
s = input()
a = 0
mods = [0]*2019
mods[a] += 1
r = 1
for i in s[::-1]:
  a = (a+int(i)*r)%2019
  r = r*10%2019
  mods[a] += 1
ans = 0
for i in mods:
  ans += i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    S = list(map(int, input().rstrip("\r\n")))
    N = len(S)
    P = 2019
    S.reverse()
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if S[i] % P == 0:ans += N-i
    else:
        D = [0] * (N+1)
        tenpow = 1
        for i in range(N):
            S[i] = S[i] * tenpow % P
            tenpow *= 10
            tenpow %= P
            D[i+1] = (S[i] + D[i]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

mod = 2019
cnt = [0] * mod
cnt[0] = 1
digit = 1
now = 0

for i in range(1, n + 1):
    now += int(s[-i]) * digit
    digit *= 10
    digit %= mod
    now %= mod
    cnt[now] += 1

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

print(ans)

Submission status: Accepted

Solution code:
n = input()

remainder = [0]*2019
remainder[0] += 1
x = 1
rem = 0

for i in range(1, len(n)+1):
	rem = (rem + int(n[-i])*x)%2019
	remainder[rem] += 1
	x *= 10
	x %= 2019
    
res = 0
for e in remainder:
	res += e*(e-1)//2

print(res)

Submission status: Accepted

Solution code:
s = input()
s_r = s[::-1]
lmod = [0]
cmod = 0
for n,i in enumerate(s_r):
    cmod += int(i)*pow(10,n,2019) % 2019
    cmod = cmod % 2019
    lmod.append(cmod)

from collections import Counter
r = 0
for _,i in Counter(lmod).items():
    r += i*(i-1)/2

print(int(r))

Submission status: Accepted

Solution code:
s = input()
len_s = len(s)
pre = 0
mod = [0]*2019
mod[0]=1
x = 1
for i in range(len_s):
    pre = (x*int(s[len_s-i-1])+pre)%2019
    mod[pre] += 1
    x *= 10
    x %= 2019
print(sum([m*(m-1)//2 for m in mod]))

Submission status: Accepted

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

mod = [0]*2019
pre = 0
mod[pre] = 1
x = 1
for i in range(n):
    pre += int(s[i])*x
    pre %= 2019
    mod[pre] += 1
    x *= 10
    x %=2019
print(sum([m*(m-1)//2 for m in mod]))

Submission status: Accepted

Solution code:
S = input()

n = len(S)
m = 2019

S_ = S[::-1]

x = 1
total = 0
modlis = [0 for i in range(m)]

ans = 0
for i in range(n):
    modlis[total] += 1
    #print("S_[i]:", S_[i])
    #print("int(S_[i])*x:", int(S_[i])*x)
    #print("total:", total)
    total += int(S_[i])*x
    #print("total:", total)
    total %= m
    #print("total:", total)
    ans += modlis[total]
    #print("x:", x)
    x = x * 10 % m
    #print("x:", x)

print(ans)

Submission status: Accepted

Solution code:
s = input()

l = list(s)
n = len(s)

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

for i in range(n):
    x = ((int(l.pop()) * pow(10, i, 2019)) + x) % 2019
    dp[x] += 1
answer = 0

for i in range(2019):
    answer += dp[i] * (dp[i] - 1) / 2
print(int(answer))

Submission status: Accepted

Solution code:
reverse_S = input()[::-1]
n = len(reverse_S)
count = 0
mod = 0
mods = [0] * 2019
mods[0] = 1
x = 1
for s in reverse_S:
    mod = (mod + (int(s) * x)) % 2019
    mods[mod] = mods[mod] + 1
    x = x * 10
    x = x % 2019

for v in mods:
    count = count + v*(v-1)//2

print(count)

Submission status: Accepted

Solution code:
P = 2019


def main():
    S = [int(s) for s in input()[::-1]]
    N = len(S)
    A = [0]*N
    d = 1
    for i, s in enumerate(S):
        A[i] = (s * d) % P
        d *= 10
        d %= P
    ans = 0
    from collections import Counter
    acc = [0]*(N+1)
    for i in range(N):
        acc[i+1] = acc[i] + A[i]
        acc[i+1] %= P
    c = Counter(acc)
    for v in c.values():
        ans += v*(v-1)//2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()[::-1]
n = len(S)
dp = [0]*2019
dp[0] = 1
X = 0
Y = 1
for s in S:
    Z=(int(s)*Y)%2019
    X = (X+Z)%2019
    dp[X] += 1
    Y = (10*Y)%2019
answer = 0
for i in range(2019):
    answer += dp[i]*(dp[i]-1)/2
print(int(answer))

Submission status: Accepted

Solution code:
# 具体例は入力例1: 817181712114で作成
# 考え方：問題文を「右からi桁目までの数とj桁目までの数の余りが等しいなら条件を満たす」と読み替えて、格桁での余りを求めて余りの配列(L)に格納していく

S = input()
size = len(S)
L = [0] * 2019  # 余りに対応する配列

# 1桁目だけ事前に準備（817181712114の最後の4）
tmp = int(S[size - 1])  # 1桁目の数　ループで書き換えていくのでtmpと命名
tmp_r = 1  # 10のn乗を2019で割った余り(n初期値: 1)
L[0] += 1  # 余り0はiとjを同じ数値にセットしたときに必ず発生しているため予め1にセットしておく
# 余りtmp(4) なお、もし入力例が817181712114でなくて0だとすると、一行上とあわせてL[0]=2となり、ansは1となることからも一行上が必要とわかる
L[tmp] += 1

# (右から)2桁目からループを回す（累積和）
for i in reversed(range(size - 1)):  # 以下、例えばi=2で考える
    n = int(S[i])  # 対象桁の数字(例えば817181712114の右から2桁目は1)
    # 対象桁でのtmp_rは、1個前の桁のtmp_rに10かけて2019で割るだけ。2桁目の場合は10
    tmp_r = (tmp_r * 10) % 2019
    r = (n * tmp_r) % 2019  # 下記の準備
    # 対象桁までを2019で割った際の余り。817181712114の場合、右2桁(14)を2019で割った余りなので14。
    tmp = (tmp + r) % 2019
    L[tmp] += 1  # 余り14の桁があるので追加

ans = 0
for i in range(2019):
    tmp = L[i]
    if (tmp > 1):
        ans += tmp * (tmp - 1) // 2
        # comb(tmp,2)をハードコーディングしてるだけ

print(ans)

Submission status: Accepted

Solution code:
def resolve():
	s = input()
	s = s[::-1]
	t = [0]*2019
	t[0] = 1
	d = 1
	cur = 0
	m = 2019
	for i in range(len(s)):
		cur = (cur + (int(s[i]) * d % m)) % m
		t[cur] += 1
		d *= 10
		d %= m
	ans = 0
	for v in t:
		ans += v*(v-1)//2
	print(ans)
resolve()

Submission status: Accepted

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3

S = input()
size = len(S)
L = [0] * 2019

tmp = int(S[size - 1])  # 最後の文字
L[0] = 1
L[tmp] += 1
tmp_r = 1  # 10のn乗を2019で割った余り(n初期値: 1)

for i in reversed(range(size - 1)):  # 最後の文字の一つ手前からループを回す
    n = int(S[i])  # 対象の文字
    tmp_r = (tmp_r*10) % 2019
    r = (n * tmp_r) % 2019
    tmp = (tmp + r) % 2019
    # print(f"{i}桁目:{tmp}")
    L[tmp] += 1

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


def calc(i):
    if (i == 0):
        return


print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


s = input()

n = len(s)
DP = [0] * (n + 1)

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

COUNTS = Counter(DP)

print(sum(count * (count - 1) // 2 for count in COUNTS.values()))

Submission status: Accepted

Solution code:
def resolve():
    s = input()
    s = s[::-1]
    c = [0]*2019
    # why?
    c[0] = 1
    r = 0
    d = 1
    for i in s:
        num = int(i) * d % 2019 + r
        num %= 2019
        c[num] += 1
        r = num
        d *= 10
        d %= 2019
    ans = 0
    for i in c:
        ans += i*(i-1)//2
    print(ans)
resolve()

Submission status: Accepted

Solution code:
s = input()[::-1]
mod = 2019
cnt = [0] * mod
x = 1
cnt[0] = 1
total = 0
for s in s:
    total += int(s) * x
    total %= mod
    cnt[total] += 1
    x *= 10
    x %= mod


ans = sum(i*(i-1)//2 for i in cnt)
print(ans)

Submission status: Accepted

Solution code:
s = input()
line = s[::-1]
n = len(s)
mods = [1] + [0] * 2018
i = 1
now = 0
for d in line:
    now += int(d) * i
    now %= 2019
    mods[now] += 1
    i *= 10
    i %= 2019

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

print(int(ans))

Submission status: Accepted

Solution code:
s = input()[::-1]
m = 2019
ans = 0
x = 1
tot = 0
cnt = [0] * m
cnt[0] = 1
for s in s:
    tot += int(s) * x
    tot %= m
    #ans += cnt[tot]
    x *= 10
    x %= m
    cnt[tot] += 1

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

Submission status: Accepted

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

n=len(s)
D=[0]*(n+1)
c=[0]*(n+1)
ans = 0
f = 0
dp = [0]*(2020)
dp[0]+=1
tmp =0
x = 1
for e,i in enumerate(s):
    tmp = (tmp+x*i)%2019
    ans += dp[tmp]
    dp[tmp]+=1
    x = x*10 %2019
print(ans)

Submission status: Accepted

Solution code:
s=input()[::-1]
mod=[0]*2019
mod[0]=1
x=1
num=0
ans=0

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

for u in mod:
    ans += u*(u-1)//2

print(ans)

Submission status: Accepted

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

v = 0
d = 1
for n in s:
    v = (v + n * d) % 2019
    d = (d * 10) % 2019

    mods[v] = mods[v] + 1

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

Submission status: Accepted

Solution code:
number = str(input())[::-1]
remainderDictionary = {0: 1}
digitDictionary = {'1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}

sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum = (sum + digitDictionary[i] * x) % 2019 
  remainderDictionary[sum] = remainderDictionary.get(sum,0) + 1

ansDictionary = {} # dictionary with the number of occurences and the corresponding N combinations of 2
ans = 0
for i in remainderDictionary:
  remainderOccurences = remainderDictionary[i]
  value = ansDictionary.get(remainderOccurences,-1)
  if value == -1:
    value = remainderOccurences * (remainderOccurences - 1) // 2 # N combinations of 2
    ansDictionary[remainderOccurences] = value
  ans += value
print(ans)

Submission status: Accepted

Solution code:
number = str(input())[::-1]
remainderDictionary = {0: 1}
digitDictionary = {'1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}

sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum = (sum + digitDictionary[i] * x) % 2019 
  remainderDictionary[sum] = remainderDictionary.get(sum,0) + 1

ans = 0
for i in remainderDictionary:
  value = remainderDictionary[i]
  if value > 1:
    ans += value * (value - 1) // 2 # N C 2
print(ans)

Submission status: Accepted

Solution code:
# n = int(sys.stdin.readline())
import sys,bisect,math
sys.setrecursionlimit(15000)

s = sys.stdin.readline().rstrip()
cum = [0]*(len(s)+1)#cumulative sum
import collections
d = collections.defaultdict(int)
d[0] = 1
ret = 0
dig = 1
for i in range(len(s))[::-1]:
    cum[i]=(int(s[i])*dig+cum[i+1])%2019
    dig = (dig*10)%2019
    #cum[i+1]=int(s[i:])%2019
    if cum[i] in d:
        ret += d[cum[i]]
    d[cum[i]] += 1
#print(d,cum,ret)
print(ret)

Submission status: Accepted

Solution code:
number = str(input())[::-1]
remainderDictionary = {0: 1}
digitDictionary = {'1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}

sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum = (sum + digitDictionary[i] * x) % 2019 
  remainderValue = remainderDictionary.get(sum,0) + 1
  remainderDictionary[sum] = remainderValue
     
ans = 0
for i in remainderDictionary:
  value = remainderDictionary[i]
  if value > 1:
    ans += value * (value - 1) // 2 # N C 2
print(ans)

Submission status: Accepted

Solution code:
number = str(input())[::-1]
remainderDictionary = {0: 1}
digitDictionary = {'1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}

sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum = (sum + digitDictionary[i] * x) % 2019 
  remainderValue = remainderDictionary.get(sum,0) + 1
  remainderDictionary[sum] = remainderValue
     
ans = 0
for i in remainderDictionary:
  value = remainderDictionary[i]
  ans += value * (value - 1) // 2 # N C 2
print(ans)

Submission status: Accepted

Solution code:
number = str(input())[::-1]
remainderDictionary = {0: 1}

digitDictionary = {'0':0, '1':1, '2':2, '3':3, '4':4, '5':5, '6':6, '7':7, '8':8, '9':9}

sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum = (sum + digitDictionary[i] * x) % 2019 
  remainderValue = remainderDictionary.get(sum,0) + 1
  remainderDictionary[sum] = remainderValue
     
ans = 0
for i in remainderDictionary:
  value = remainderDictionary[i]
  ans += value * (value - 1) // 2 # N C 2
print(ans)

Submission status: Accepted

Solution code:
number = str(input())[::-1]
remainderDictionary = {0: 1}
    
sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum = (sum + int(i) * x) % 2019 
  remainderValue = remainderDictionary.get(sum,0) + 1
  remainderDictionary[sum] = remainderValue
     
ans = 0
for i in remainderDictionary:
  value = remainderDictionary[i]
  ans += value * (value - 1) // 2 # N C 2
print(ans)

Submission status: Accepted

Solution code:
number = str(input())[::-1]
remainderDictionary = {0: 1}
    
sum = 0
x = 1
for i in number:
  x = (x * 10) % 2019
  sum += int(i) * x
  sum %= 2019
  remainderValue = remainderDictionary.get(sum,0) + 1
  remainderDictionary[sum] = remainderValue
     
ans = 0
for i in remainderDictionary:
  value = remainderDictionary[i]
  ans += value * (value - 1) // 2 # N C 2
print(ans)

Submission status: Accepted

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

S=[0,]
cnt=[0]*2019
cnt[0]=1
d=1
num=0
for i in range(len(s)):
    num += int(s[i])*d
    num %= 2019
    d *= 10
    d%= 2019
    # S.append((int(S[i]) + int(s[i]) * 10**i) % 2019)
    cnt[num]+=1

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

print(ans)

Submission status: Accepted

Solution code:
# 後で１の位から処理するためにひっくり返しておく
S = list(map(int, reversed(input())))
#print("S = ", S)
"""
「2019の倍数か」は「mod 2019 が 0 になるか」と同意。
しかし、普通に切り出して、１つずつチェックすると計算工数がかかるので、累積和を使う。
各桁の値を （桁の数値a_k）× 10^k と表現し、mod 2019 の値を予め計算し、累積和を作っておく。
ここで、10^k の部分は、2019と互いに疎（公約数がない）なので、
含めて計算しても mod 2019 の周期を乱さない。（勿論オフセットは変わる）
「(i, j) が2019で割り切るか」は、「i～j の累積和が同じ値になる（2019周期）か」と同意。
累積和が同じ値になる個数を数えて、組み合わせを計算すればよい。
"""
# a　：　各桁の mod 2019 値（桁の数値 a_k × 10^k mod 2019）
a = [0] * len(S)
# sums ：　累積和
sums = [0] * (len(S) + 1)
# d : 10^k
d = 1
# cnt : 累積和 mod 2019 の出現度数表
cnt = [0] * 2019
cnt[0] = 1  # sums[0] = 0 の分
for i in range(len(S)):
    a[i] = (S[i] * d) % 2019
    sums[i + 1] = (sums[i] + a[i]) % 2019
    d = (d * 10) % 2019 
    cnt[sums[i + 1]] += 1
#print("sums = ", sums)
#print("cnt = ", cnt)
ans = 0
for i in cnt:
    ans += i * (i - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
s = input()[::-1]
v = 0
mods = {}
mods[0] = 1
d = 1

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

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

print(ans)

Submission status: Accepted

Solution code:
S = input()

X = [0]*2019
X[0] = 1
d = 1
a = 0

for s in reversed(S):
    a = ((ord(s) - ord('0'))*d + a)%2019
    d = d*10%2019
    X[a] += 1

ans = sum(x*(x-1)//2 for x in X)
print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

X = [0]
for i, s in enumerate(S):
  X.append((X[-1] + int(s)*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]
# (Xl,0 − Xr−1,0) % 2019 = 0 → Xl,0 % 2019 = Xr−1,0 % 2019
cnts = [1] + [0] * (2019 - 1)
tmp = 0
d = 1

for i in s:
    tmp += int(i) * d
    cnts[tmp % 2019] += 1
    d = d * 10 % 2019 # 桁数が大きくなりすぎる → 10と2019が素だから可能な技

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

print(ans)

Submission status: Accepted

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

cnts = [1] + [0] * (2019 - 1)
tmp = 0
d = 1

for i in s:
    tmp += int(i) * d
    cnts[tmp % 2019] += 1
    d = d * 10 % 2019 # 桁数が大きくなりすぎる → 10と2019が素だから可能

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

print(ans)

Submission status: Accepted

Solution code:
import collections
import math

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

def naive(s):
	cnt = 0
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			k = int(s[i:j])
			if k % 2019 == 0 and k != 0:
				#print(i, j)
				cnt += 1
	return cnt

def main(s):
	nums = [0]
	cur = 0
	p = 0.1
	for i in range(len(s)):
		p = int(p * 10) % 2019
		cur = (cur + int(s[len(s) - 1 - i]) * p) % 2019
		nums.append(cur)
	d = dict(collections.Counter(nums))
	a = [val for key, val in d.items() if val >= 2]
	return sum([comb(x, 2) for x in a])	

s = input()
print(main(s))

Submission status: Accepted

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

sum = 0
x = 1
for i in S:
    sum += int(i) * x
    Surpus[sum % 2019] += 1
    x *= 10
    x %= 2019

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

print(ans)

Submission status: Accepted

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


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)/2
print(int(cnt))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S = list(input())
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = [0] * 2019
k = 10
for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        sub += int(S[N - i]) * k
        k *= 10
        k %= 2019
    rest = sub % 2019
    counter[rest] += 1

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

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
cnt[0] = 1
x=0
mod19[n] = 0
for i in range(n-1, -1,-1):
	x = (x+int(s[i])*power[i])%2019
	mod19[i] = x
	cnt[x]+=1
ans = 0
for i in range(2020):x = cnt[i];ans+= x*(x-1)//2
print(ans)

Submission status: Accepted

Solution code:
s = list(input())
n = len(s)
mod = 2019

d=[0]*(n+1)
k=1
for i in range(n):
    d[i+1]=d[i]+k*int(s[n-i-1])
    d[i+1]%=mod
    k*=10
    k%=mod

count = [0]*mod
for i in range(n+1):
    count[d[i]] += 1

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

    count = 0

    mods = [0] * 2019
    mods[0] = 1
    current = 0
    x = 1
    for s in S:
        current = (current + x * int(s)) % 2019
        count += mods[current % 2019]
        mods[current % 2019] += 1
        x = x * 10 % 2019

    print(count)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# D - Multiple of 2019

s = input()

# pow[k] = 10 ** k % 2019
pow = [1]
while len(pow) <= 1 or pow[-1] > 1:
    pow.append(pow[-1] * 10 % 2019)
n = len(pow) - 1  # 10 ** n == 1 mod 2019

# memo[i % n][m] = (int(s[:i+1]) % 2019 == mであるiの個数)
memo = [[0] * 2019 for i in range(n)]
memo[n - 1][0] = 1  # memo[-1][0] = 1

count = 0  # int(s[i:j+1]) == 0 mod 2019 である(i,j)の個数
mod = 0
for j, c in enumerate(s):
    mod = (mod * 10 + int(c)) % 2019  # mod = int(s[:j+1]) % 2019
    for i in range(1, n + 1):
        m = mod * pow[n - i] % 2019  # m == mod * 10 ** (-i) mod 2019
        count += memo[(j - i + n) % n][m]
    memo[j % n][mod] += 1

print(count)

Submission status: Accepted

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

d = [0] * (n+1)

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

count = [0] * mod
for i in range(n+1):
    count[d[i]] += 1

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

print(ans)

Submission status: Accepted

Solution code:
S = input()
mod = 2019
len_S = len(S)
# 10の乗数のmodを格納
# オーバーフローを防ぐ
power = [0] * len_S
power[len_S - 1] = 1

for i in range(1,len_S):
    power[len_S-i-1] = (power[len_S-i] * 10) % mod

a = []
S_a = [0] * len_S
for i in range(len_S):
    a.append((power[i] * int(S[i])) % mod)
    if i > 0:
        S_a[i] = S_a[i-1] + int(a[i])
    else:
        S_a[i] = int(a[i])

# S_a の 2019の余りをカウント
cnt = [0] * 2020
ans = 0
for i in range(len_S):
    cnt[S_a[i]%mod] += 1

# 累積和のあまりがすでに0のやつはそれを選べば割り切れるので足す
ans += cnt[0]
for i in range(2020):
    ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

MOD = 2019

def solve(S):
    dp = np.zeros(MOD, np.int64)
    temp = np.empty_like(dp)
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % MOD
        temp[x:] = dp[:-x]
        temp[:x] = dp[-x:]
        dp, temp = temp, dp
        answer += dp[0]
        pow10 *= 10
        pow10 %= MOD
    return answer


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

if sys.argv[-1] == 'ONLINE_JUDGE':
    cc_export()
    exit()
else:
    from my_module import solve

S = np.array(list(read().rstrip()), dtype=np.int32) - ord('0')
print(solve(S))

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
ans = 0
for i in range(2020):x = cnt[i];	ans+= x*(x-1)//2
print(ans+cnt[0])