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()
dp = [int(s) for s in S[::-1]]
dp.insert(0, 0)
for i in range(len(S)):
    dp[i+1] = (dp[i+1]*pow(10, i, 2019) + dp[i])%2019

from collections import Counter

c = Counter(dp)
# print(c)
print(sum([x*(x-1)//2 for x in c.values()]))

Submission status: Accepted

Solution code:
n = input()
mod = [0]*2019
mod[0] += 1
T = 0
d = 1 # 桁数
for i, s in enumerate(n[::-1]):
  T += int(s) * d
  T %= 2019
  d = (d * 10) % 2019
  mod[T] += 1
  
res = 0  
for m in mod:
  res += m*(m-1)/2
print(int(res))

Submission status: Accepted

Solution code:
# originally submitted at https://atcoder.jp/contests/abc164/submissions/12433818
# authored by catamanyan
S = list(map(int,input()))

counter = 0
amari = [0]*2019

s = 0
for i in range(len(S)):
    if S[len(S)-i-1] == 0:
        continue
    else:
        s += S[len(S)-i-1] * pow(10, i, 2019)
        s = s % 2019
        amari[s] += 1

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

counter += amari[0]

print(int(counter))

Submission status: Accepted

Solution code:
s=input()
b=0
m=len(s)
c=[0 for i in range(2019)]
c[0]=c[0]+1
a=""
e=0
f=1
s= ''.join(list(reversed(s)))
for i in s:
    e+=int(i)*f
    g=e%2019
    c[g]+=1
    f*=10
    f%=2019
e = sum(i * (i - 1) // 2 for i in c)
print(e)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
s = input().strip()
if len(s) <= 3:
  print(0)
  exit()
c = 0
chk = [0]*2019
for i,si in enumerate(s[::-1]):
  c += int(si)*pow(10,i,2019)
  chk[c%2019] += 1
ans = chk[0]
for i in chk:
  ans += i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
def POW(x, n, mod):
    ans = 1
    # n が 0 になるまで計算を続ける
    while n > 0:
        if n % 2 == 1:
            ans *= x%mod
        x = (x*x)%mod						#x = x**2
        n >>= 1						#ビットシフト
    return ans

if __name__ == '__main__':
	S = input()
	L = len(S)
	lst = [0] * 2019
	lst[0] = 1
	amari = 0
	ans = 0
	for i in range(1,L+1):
		amari = ( int(S[L-i]) * POW(10,i-1,2019) + amari ) % 2019
		lst[amari] += 1

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

	print(int(ans))

Submission status: Accepted

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

for j in range(2019):
    #if m[j]>= 2:
    number += (m[j]*(m[j] - 1))//2

print(number)

Submission status: Accepted

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

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

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

acc = [0] * (N+1)
mul = 1
for i in range(N-1, -1, -1):
    x = int(S[i]) * mul
    acc[i] = (acc[i+1] + x) % mod
    mul *= 10
    mul %= mod

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

Submission status: Accepted

Solution code:

s = input()[::-1]
from collections import defaultdict
amari = defaultdict(int)
keta_ = defaultdict(int)

cur = 0
keta = 1

for i in range(len(s)):
    cur += int(s[i]) * keta
    cur %= 2019

    keta *= 10
    keta %= 2019
    
    amari[cur] += 1
    keta_[keta] += 1

#print('%')
#print(2114%2019)
#print(181712114%2019)

#print(81712114%2019)
#print(1817181712114%2019)

#print('%')

#print(amari)
#print(keta_)
ans = 0
if 0 in amari:
    ans += amari[0]

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

Submission status: Accepted

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


def solve(S: int):
    from itertools import takewhile, count
    SS = tuple(map(int, str(S)))
    ans = 0
    t = [0] * 2020
    t[0] = 1
    u, cnt = 0, 0
    for i, n in enumerate(reversed(SS)):
        u = (n * pow(10, i, 2019) + u) % 2019
        cnt += t[u]
        t[u] += 1
    return cnt



# 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
    print(solve(S))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,os
from collections import defaultdict, deque
from math import ceil, floor
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 2019

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

    if N < 4:
        print(0)
        return

    R = [0] * 2019
    R[0] = 1 # '' の分
    t = 0
    b = 1
    for c in S:
        t += int(c) * b
        t %= 2019
        R[t] += 1
        b *= 10
        b %= 2019
    ans = 0
    for r in R:
        ans += r*(r-1)//2
    print(ans)
    




    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = str(input())[::-1]
sum_of_digits = 0
cnt = [0] * 2019

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

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

Submission status: Accepted

Solution code:
def main():
    S = input()
    work, temp = [0] * 2019, 0
    work[0] = 1
    a = 1
    for s in S[::-1]:
        temp += int(s) * a
        work[temp%2019] += 1
        a *= 10
        a %= 2019
    print(sum([w*(w-1)//2 for w in work]))
main()

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()
Sr = S[::-1] # 一の位から考える

T = 0 # 部分文字列
mod = [0] * 2019 # mod数え上げ配列
mod[0] += 1 # 「部分文字列T = S」の場合の、 「0 % 2019 = 0」を予めカウント
d = 1 # 桁数
for i, s in enumerate(Sr):
  T += int(s) * d
  T %= 2019
  d = (d * 10) % 2019
  
  mod[T] += 1
  
# ペアを合計
# n個から2通り選ぶ（nC2）
mod = [n * (n-1) // 2 for n in mod]
print(sum(mod))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S=input()[::-1]
l=[0]*2019
a=1
d=0

for s in S:
  d=d+int(s)*a
  l[d%2019]+=1
  a*=10
  a%=2019
  
ans=l[0]
for i in l:
  if i>=2:
    ans+=i*(i-1)//2
    
print(ans)

Submission status: Accepted

Solution code:
s=input()
s_len=len(s)
n=2019
sp=[0]*n
sp[0]=1
p=1
d=0
for i in reversed(s):
    d+=int(i)*p
    m=d%n
    sp[m]+=1
    p*=10
    p%=2019
result=sum(i*(i-1)//2 for i in sp)
print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s = input()
s_len = len(s)
n = 2019
mod_list = [0] * n
mod_list[0] = 1

p = 1
d = 0
for t in reversed(s):
    d += int(t) * p
    m = d % n
    mod_list[m] += 1
    p *= 10
    p %= 2019

result = sum(i * (i - 1) // 2 for i in mod_list)
print(result)

Submission status: Accepted

Solution code:
num = [0 for i in range(2019)]
num[0] = 1
count = 0
s = input()
now = 0
p = 1
for i in range(len(s) - 1, -1, -1):
    now = (now + int(s[i]) * p) % 2019
    count += num[now]
    num[now] += 1
    p = p * 10 % 2019
print(count)

Submission status: Accepted

Solution code:
S = input()
n = len(S)
k = 2019

# Let S = s[0]s[1]....s[n - 1] and
# let A[i] = s[i]s[i+1]...s[n-1] = s[i]*10^(n-i-1) + ... + s[n-1]*10^0
A = [0] * (n + 1) # A[n] = 0
d = {0:1}

w = 1
for i in range(n - 1, -1, -1):
    A[i] = (A[i + 1] + w * int(S[i])) % k
    w = w * 10 % k
    if A[i] in d:
        d[A[i]] += 1
    else:
        d[A[i]] = 1

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
S = input()[::-1]

mod = [0]*2019
mod[0] = 1
ten = 1
index = 0
for s in S:
    index += ten*int(s)
    index %= 2019
    mod[index] += 1
    ten *= 10
    ten %= 2019

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

print(ans)

Submission status: Accepted

Solution code:
S=input()[::-1]
List=[0]*2019
ans=0
a=1
d=0

for s in S:
  d=d+int(s)*a
  List[d%2019]+=1
  a=a*10
  a=a%2019
  #print(s[i:],int(s[i:])%2019)
  
#print(List)
ans=List[0]
for i in List:
  if (i>=2):
    ans+=(i*(i-1))//2
  
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import Counter
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    S = [int(x) for x in input().strip()]
    N = len(S)
    ans = 0
    l = [0] * (N + 1)
    p = 1
    cumsum = [0] * (N + 1)
    for i in range(N-1, -1, -1):
        l[i] = (S[i] * p) % 2019
        p *= 10
        p %= 2019
    for i in range(N-1, -1, -1):
        cumsum[i] = (l[i] + cumsum[i+1]) % 2019
    cumsum = Counter(cumsum)
    for i in range(0, 2019):
        ans += (cumsum[i] * (cumsum[i] - 1)) // 2

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

a = 1
d = 0

for s in S:
    d = d + int(s)*a
    num = d%2019
    counts[num] += 1
    a *= 10
    a %= 2019

ans = 0

for i in counts:
    if i >=2:
        x = (i*(i-1))//2
        ans += x

print(ans)

Submission status: Accepted

Solution code:
#ACの人のやつ丸パクリです。自分のソースコードがTLEになるので試しに使わせてもらいます。

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 = list(map(int, list(input())))
n = len(s)

countdic = {}
mod = 2019

num = 0
d = 1
for i in range(1,n+1):
    num += s[n-i]*d
    num %= mod
    if num in countdic:
        countdic[num] += 1
    if num not in countdic:
        countdic[num] = 1
    d = (10*d)%mod

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

if 0 in countdic:
    ans += countdic[0]

print(ans)

Submission status: Accepted

Solution code:
S = input()
r = 1
arr = [0]
for c in S[::-1]:
    arr.append((arr[-1] + int(c) * r) % 2019)
    r *= 10
    r %= 2019
from collections import Counter
ctr = Counter(arr)
ans = 0
for v in ctr.values():
    ans += v*(v-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,deque
from scipy import special
S = input()
l = [int(n) for n in S]
a = [0]
t = 0
m = 1
d = deque(l)
mod = 2019
while d:
    temp = d.pop()
    t = (t + (temp * m)) % mod
    m = (m * 10) % mod
    a.append(t%mod)
b = [special.comb(kv,2,exact=True) for kv in Counter(a).values() if kv > 1]
print(sum(b))

Submission status: Accepted

Solution code:
s = input()

n = len(s)
c = [0]*2019
c[0]+=1
t = 0
digit = 1
for ss in s[::-1]:
    t = (t+int(ss)*digit) % 2019
    digit = (digit * 10) % 2019
    c[t]+=1
ans = 0
ans = sum(cc*(cc-1)//2 for cc in c)
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    S = str(input())
    N=len(S)
    P=2019

    def main():
        if P == 2:
            res = 0
            for i in range(N):
                if int(S[N - 1 - i]) % 2 == 0:
                    res += N - i
        elif P == 5:
            res = 0
            for i in range(N):
                if int(S[N - 1 - i]) == 0 or int(S[N - 1 - i]) == 5:
                    res += N - i

        else:
            mods = [0] * P
            # mods[i]はPで割ったあまりがiである連続部分列の個数
            tenfactor = 1
            mod = 0
            mods[mod] += 1

            for i in range(N):
                mod = (mod + int(S[N - i - 1]) * tenfactor) % P
                tenfactor = (tenfactor * 10) % P
                mods[mod] += 1

            res = 0
            for p in range(P):
                res += mods[p] * (mods[p] - 1) // 2

        return res

    print(main())


resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S=input()
mc=[0]*2019

tg=0
digit=1
for s in S[::-1]:
    tg+=int(s)*digit
    mc[tg%2019]+=1
    digit=digit*10%2019

ans=sum(m*(m-1)//2 for m in mc)
print(ans+mc[0])

Submission status: Accepted

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

surplus = [0]*2019
surplus[0] += 1

d = 1
n = 0
for i in reversed(input()):
    n = (n + int(i)*d) %2019
    d = d*10 % 2019
    surplus[n] += 1

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

Submission status: Accepted

Solution code:
# Problem D - Multiple of 2019

# input
S = list(input())
N = len(S)

# initialization
ans = 0

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

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

# output
print(ans)

Submission status: Accepted

Solution code:
S = input()
mod = [0] * 2019
mod[0] = 1 
d = 1
n = 0
for i in reversed(S):
  n += int(i) * d
  n %= 2019
  d *= 10
  d %= 2019
  mod[n % 2019] += 1
ans = 0
for j in range(2019):
  ans += mod[j] * (mod[j] - 1) // 2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

S = list(input())
N = len(S)
d = defaultdict(int)

beki = [0]*N
now = 1
for i in range(N):
    beki[i] = now
    now *= 10
    now %= 2019

now = 0
d[0] = 1
ans = 0
for i in range(N):
    now += int(S[N-1-i])*beki[i]
    now %= 2019
    ans += d[now]
    d[now] += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    s = input()
    rem = [0] * 2019  # the count of the each remainder: 0 ~ 2018
    rem[0] = 1  # why? can't understand.

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

    return sum(c * (c - 1) // 2 for c in rem)


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

Submission status: Accepted

Solution code:
def main():
    s = list(input())[::-1]
    ary_mod = [0] * 2019
    ary_mod[0] = 1
    now = 0

    for i, ss in enumerate(s):
        now += int(ss) *pow( 10 , i, 2019)
        remind = now % 2019
        ary_mod[remind] += 1
    ans = 0
    for i, n in enumerate(ary_mod):
        ans += (n*(n-1)) // 2
    print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    s = input()
    rem = [0] * 2019  # the count of the each remainder: 0 ~ 2018
    rem[0] = 1  # why? can't understand.

    temp = 0
    digit = 1
    for c in s[::-1]:
        # No time to pow.
        temp += int(c) * digit
        rem[temp % 2019] += 1
        digit = digit * 10 % 2019

    return sum(c * (c - 1) // 2 for c in rem)


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

Submission status: Accepted

Solution code:
def main():
    s = input()
    rem = [0] * 2019  # the count of the each remainder: 0 ~ 2018
    rem[0] = 1  # why? can't understand.

    temp = 0
    digit = 1
    for c in s[::-1]:
        # No time to pow.
        temp += int(c) * digit
        rem[temp % 2019] += 1
        digit *= 10
        digit %= 2019

    return sum(c * (c - 1) // 2 for c in rem)


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

Submission status: Accepted

Solution code:
def main():
    s = input()
    rem = [0] * 2019  # the count of the each remainder: 0 ~ 2018
    rem[0] = 1  # why? can't understand.

    temp = 0
    digit = 1
    for i, c in enumerate(s[::-1]):
        # No time to pow.
        temp += int(c) * digit
        rem[temp % 2019] += 1
        digit *= 10
        digit %= 2019

    return sum(c * (c - 1) // 2 for c in rem)


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

Submission status: Accepted

Solution code:

def main():
    s = list(input())[::-1]
    ary_mod = [0] * 2019
    ary_mod[0] = 1
    now = 0
    digit = 1
    for i, ss in enumerate(s):
        now += int(ss) * digit % 2019
        digit *= 10
        digit %= 2019
        remind = now % 2019
        ary_mod[remind] += 1
    ans = 0
    for i, n in enumerate(ary_mod):
        ans += (n*(n-1)) // 2
    print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# https://www.hamayanhamayan.com/entry/2020/04/26/232032
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:
def main():
  n, d, mods = 0, 1, [1]+[0]*2019
  for i in reversed(input()):
    n = (n+int(i)*d)%2019
    d = d*10%2019
    mods[n] += 1
  print(sum([i*(i-1)//2 for i in mods]))
main()

Submission status: Accepted

Solution code:
import time

p0 = time.time()
S = input()
n = len(S)
Y = {0:1}
# print(Y)
Y[0] = 1
A = [0]
pk = 0
for i in range(1,n+1):
    # print(S[-i])
    k = (int(S[-i])*pow(10,i-1,2019)+pk)%2019
    A.append(k)
    if k not in Y:
        Y[k] = 1
    else:
        Y[k] += 1
    pk = k

# print(A)
# print(Y)
# print(time.time()-p0)
c = 0
for y in Y:
    d = Y[y]
    c += d*(d-1)//2
print(c)

Submission status: Accepted

Solution code:
S = input()

num = 0

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

    r_lst[num] += 1


print(cnt)

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
    counts[num] += 1
    d *= 10
    d %= 2019

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces

def comb(a,b):
    ans = 1
    for i in range(b):
        ans *= a - i
    for j in range(b):
        ans //= (j + 1)
    return ans

def main():
    s = ns()
    mod = 2019
    tmp1  = 1
    tmp2 = 0
    mod2019 = [1] + [0 for i in range(2018)]
    for i in range(len(s)-1, -1, -1):
        tmp2 = (tmp2 + tmp1*int(s[i]))%mod
        tmp1 = (tmp1*10)%mod
        mod2019[tmp2] += 1
    ans = 0
    for i in range(2019):
        ans += comb(mod2019[i],2)
    print(ans) 
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input()[::-1]
n = len(s)
amari = [0]*2019
amari[0] = 1

temp = 0
d = 1
for char in s:
    temp += int(char)*d
    temp %= 2019
    d *= 10
    d %= 2019  
    amari[temp] += 1

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

print(int(ans))

Submission status: Accepted

Solution code:
if __name__ == '__main__':

    s = list(input())
    s.reverse()
    n = len(s)
    now = 0
    mods = [0] * 2019
    mods[0] += 1
    for i in range(n):
        now += pow(10, i, 2019) * int(s[i])
        now %= 2019
        mods[now] += 1
    ans = 0
    for i in mods:
        ans += (i * (i - 1)) // 2
    print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':

    s = list(input())
    s.reverse()
    n = len(s)
    now = 0
    mods = [0] * 2019
    mods[0] += 1
    ten = 1
    for i in range(n):
        now += ten * int(s[i])
        now %= 2019
        ten *= 10
        ten %= 2019
        mods[now] += 1
    ans = 0
    for i in mods:
        ans += (i * (i - 1)) // 2
    print(ans)

Submission status: Accepted

Solution code:

s=input()
s=s[::-1]
md=[0]
ex10=1
tmp=0
mod=2019
for i in range(len(s)):
    tmp+=ex10*int(s[i])
    tmp%=mod
    md.append(tmp)
    ex10*=10
    ex10%=mod
from collections import Counter

sc= Counter(md)
ans=0
for k in sc:
    sck=sc[k]
    ans+= sck*(sck-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
s = input()
n = len(s)

d = defaultdict(int)
d[0] = 1
x = 0
b = 1
for i in range(n-1,-1,-1):
    x += b*int(s[i])
    x %= 2019
    d[x] += 1

    b *= 10
    b %= 2019

res = 0
for k in d:
    c = d[k]
    res += c*(c-1)//2
print(res)

Submission status: Accepted

Solution code:
s=list(input())
s=s[::-1]
l=len(s)
mod=2019
count=[0]*2019
count[0]=1
num=0
seki=1
for i in range(l):
    num+=int(s[i])*seki
    num=num%mod
    count[num]+=1
    seki=(seki*10)%mod
ans=0
for i in range(2019):
    N=count[i]
    ans+=N*(N-1)//2
print(ans)

Submission status: Accepted

Solution code:
s=input()
n=len(s)
from collections import Counter
#print(s,n)
cc=Counter()
cc[0]+=1
num=0
tenpow=1
ans=0
for i in range(n-1,-1,-1):
    num=tenpow*(int(s[i]))+num
    num%=2019
    tenpow=10*tenpow
    tenpow%=2019
    ans+=cc[num]
    cc[num]+=1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=2019
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    A=list(map(int,list(input())[::-1]))
    N=len(A)
    S=[0]*(N+1)
    for i in range(N):
        S[i+1]=(S[i]+A[i]*pow(10,i,MOD))%MOD
    l=[0]*2019
    ans=0
    for i in range(N+1):
        ans+=l[S[i]]
        l[S[i]]+=1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()
digits = list(map(int,S))
# S = S[::-1]→これが時間かかる

# i~nまでの値をmod2019したときの数
# ls = [0for i in range(2019)]
ls = [0] * 2019

# 0文字の時
ls[0] += 1

x = 0
pow10 = 1
count = 0
for i in reversed(digits):
    x += i*pow10
    x %= 2019
    count += ls[x]
    ls[x] += 1
    pow10 *= 10
    pow10 %= 2019

# for x in ls:
#     count += x*(x-1)/2

print(int(count))

Submission status: Accepted

Solution code:
# @oj: atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-04-27 14:27
# @url:https://atcoder.jp/contests/abc164/tasks/abc164_d
import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
# region fastio

BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------------------
# (a*b)%p=(a%p*b%p)%p
# (a+b)%p=(a%p+b%p)%p
def main():
    k=2019
    s=str(input())[::-1]
    mod10=[1]
    for i in range(1,len(s)):
        mod10.append((mod10[i-1]%k*10%k)%k)
    inverse=[]
    for i in range(0,len(s)):
        n=int(s[i])
        if n!=0:
            if len(inverse)>0:
                mod=((n%k*mod10[i])%k+inverse[-1])%k
            else:
                mod=((n%k*mod10[i])%k)%k
            inverse.append(mod)
    res=[x for x in list(collections.Counter(inverse).items()) if x[0]==0 or x[1]>1]
    # print (inverse)
    # print (res)
    ans=0
    for r in res:
        if r[0]==0:
            ans+=(r[1]+1)*r[1]//2
        else:
            ans+=(r[1]-1)*r[1]//2
    print (ans)    
    # 181718171
    # print ((1111111117*10+1)%2019,((1111111117%2019*10%2019)%2019%2019+1%2019)%2019)
    # print (8171%2019,((10**3%2019*10%2019)%2019%2019+8171%2019)%2019)
    # print ((11111111171-965)%2019)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
s = input()

mod = [0] * 2019
mod[0] = 1
d = 1
n = 0
ans = 0

for i in reversed(s):
    n += int(i) * d
    n %= 2019
    d *= 10
    d %= 2019
    mod[n % 2019] += 1

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

print(ans)

Submission status: Accepted

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

S = input()[::-1]

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

num, d = 0, 1

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

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

print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict

S = input()
N = len(S)
d = defaultdict(int)

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

print(ans)

Submission status: Accepted

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

ans = 0
ten = 1
d = 0
cntlist = [0]*2019
cntlist[0] = 1
for i in range(n-1,-1,-1): #ステップ指定必要
    a = int(s[i])*ten%2019
    d = (d + a)%2019
    ten *= 10
    ten %= 2019
    cntlist[d] += 1

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

print(ans)

Submission status: Accepted

Solution code:
import sys
## io
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))
## dp
INIT_VAL = 0
MD2 = lambda d1,d2: [[INIT_VAL]*d2 for _ in range(d1)]
MD3 = lambda d1,d2,d3: [MD2(d2,d3) for _ in range(d1)]
## math
DIVC = lambda x,y: -(-x//y)
DIVF = lambda x,y: x//y

def main():
    s = list(map(int, IS()))
    n = len(s)
    p = 2019
    cnt = 0
    d = [0]*p
    d[0] = 1 # 0(mod p)はそれ単体で割り切れるため+1しておく
    ss = 0
    x = 1
    for si in s[::-1]:
        ss += x*si
        ss %= p
        d[ss] += 1
        x = (10*x)%p # %p無しだとTLE
    cnt = 0
    for di in d:
        cnt += di*(di-1)//2 # calc combination(n_C_2)
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()
digits = list(map(int, S))
divisor = 2019

rem_count = [0] * divisor
rem_count[0] = 1
num = 0
pow10 = 1
total = 0

for digit in reversed(digits):
    num += digit * pow10
    rem = num % divisor
    total += rem_count[rem]
    pow10 *= 10
    rem_count[rem] += 1

    # optimization to not deal with big integers
    num = rem
    pow10 %= divisor

print(total)

Submission status: Accepted

Solution code:
def main():
    S = input()
    u = 0
    H = [0] * 2019
    H[0] = 1
    m = 1
    r = 0
    for s in reversed(S):
        u = (u + m * int(s)) % 2019
        r += H[u]
        H[u] += 1
        m = (m * 10) % 2019
    return r


print(main())

Submission status: Accepted

Solution code:
"""
s=1817181712114 なら
4
10
100
2000
10000
700000
1000000
80000000
100000000
7000000000
10000000000
800000000000
1000000000000
の数列とみて, 各々%2019を取ってzero sum range
"""
from collections import Counter
def make_modlist(Len,mod):
    modlist=[0]*Len
    modlist[0]=1
    for i in range(1,Len):
        modlist[i]=10*modlist[i-1]%mod
    return modlist
a=list(map(int,input()))
a.reverse()
n=len(a)
d=make_modlist(n,2019)
b=[0]*(n+1)
for i in range(n):
    b[i+1]=a[i]*d[i]%2019
for i in range(1,n+1):
    b[i]+=b[i-1]
    b[i]%=2019
ans=0
for i in Counter(b).values():
    ans+=i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
s = list(map(int,list(input())))[::-1]
n = len(s)
chk = [0]*2019
chk[0] = 1
t,m,ans = 1,0,0
for i in s:
    m = (m+t*i)%2019
    ans += chk[m]
    chk[m] += 1
    t = t*10%2019
print(ans)

Submission status: Accepted

Solution code:
s,l = (input(),2019)
m,a,r = ([1]+[0]*l,0,0)
for i,e in enumerate(s[::-1]):
    a += int(e)*pow(10,i,l)
    r += m[a%l]
    m[a%l] += 1
print(r)

Submission status: Accepted

Solution code:
S = input()
digits = list(map(int, S))
divisor = 2019

rem_count = [0] * divisor
rem_count[0] = 1
num = 0
pow10 = 1
total = 0

for digit in reversed(digits):
    num = digit * pow10 + num
    num %= divisor
    total += rem_count[num % divisor]
    pow10 *= 10
    pow10 %= divisor
    rem_count[num % divisor] += 1

print(total)