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:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

s = S()
D = defaultdict(int)
D[0] = 1
ret = 0
ans = 0
j = 1
for i in range(len(s) - 1, -1, -1):
    ret = int(s[i]) * j + ret
    ans += D[ret % 2019]
    D[ret % 2019] += 1
    j = j * 10 % 2019

print(ans)

Submission status: Accepted

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

MOD = 2019

mods = [0 for _ in range(2019)]
mods[0] = 1

num = 0
digit = 1
for s in S[::-1]:
  num = s * digit + num
  num %= MOD
  mods[num] += 1
  digit = (digit * 10) % MOD
  
ans = 0
for m in mods:
  ans += m * (m - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
s = list(map(int, list(input())))

acc = [0]*(len(s)+1)
digit = 1

for i in reversed(range(0, len(s))):
    si = s[i] * digit % 2019
    acc[i] = (acc[i+1] + si) % 2019
    digit *= 10
    digit %= 2019

cnt = [0]*2019
ans = 0
for i in range(0, len(s)+1):
    ans += cnt[acc[i]]
    cnt[acc[i]] += 1

print(ans)

Submission status: Accepted

Solution code:
s=input()
n=len(s)
t=[0]*2019
t[0]=1
d=1
tkk=0
for k in reversed(range(n)):
  tk=tkk+int(s[k])*d
  tk=tk%2019
  t[tk]=t[tk]+1
  tkk=tk
  d=d*10
  d=d%2019
ans=0
for i in t:
  ans=ans+i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
s = input()
mod = 2019
l = [0]*mod
l[0] = 1 #余りが0の場合が1足りないので補う
ans = 0
r = 0
t = 1

for i in s[::-1]:
    r += int(i)*t
    r %= mod # 余りをrに代入してしまっても、後の計算に支障が無い。
    l[r] += 1
    t *= 10
    t %= mod # t *= 10を使用しても、ここの余りを使用しても、r%modの答えは変わらない。

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

print(ans)

Submission status: Accepted

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

sm = 0

cnts = [0] * 2019
cnts[0] = 1

d = 1

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
S=input()

N=len(S)
d={}
for i in range(2019):
    d[i]=0

d[0] = 1

mod=0
dig=1

for i in range(N):
    #s=S[N-1-i:]
    #d[int(s)%2019]+=1
    mod += dig * int(S[N-1-i])
    mod %= 2019
    d[mod] += 1
    dig *= 10
    dig %= 2019


ans = 0
for k in d.keys():
    v = d[k]
    if v > 1:
        ans += v*(v-1)//2
print(ans)

Submission status: Accepted

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

# 0が2019個からなるリスト。modを保管する
cnts = [0] * 2019
cnts[0] = 1
mod_num = 0
d = 1

for c in s:
  t = d * int(c)
  mod_num += t
  mod_num %= 2019
  cnts[mod_num] += 1
  d *= 10
  d %= 2019

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

print(result)

Submission status: Accepted

Solution code:
S = input()[::-1]
L = len(S)
ans = 0
now = 0
A = [0] * 2019
A[0] = 1
d = 0
for i in range(L):
    now = now + int(S[i]) * pow(10, d, 2019)
    now %= 2019
    d += 1
    A[now] += 1

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

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin


def get_result(data):
    S = data[0]
    mod_all_bit = [0] * 2019
    mod_all_bit[0] = 1
    # 10**i の mod を漸化式的に事前計算
    # こうすることで計算が効率化できる
    ten_i_mod = [0] * len(S)
    ten_i_mod[0] = 1
    for i in range(len(S)-1):
        ten_i_mod[i+1] = (ten_i_mod[i] * 10) % 2019
    mod = 0
    for i in range(len(S)):
        mod = (mod + ten_i_mod[i] * int(S[-(i+1)])) % 2019
        mod_all_bit[mod] += 1
    ans = 0
    for val in mod_all_bit:
        if val >= 2:
            ans += val * (val-1) * 0.5
    return int(ans)


if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)

Submission status: Accepted

Solution code:
s = input()

ch = 0
x = 1

rem = [0] * 2019
ans = 0
rem[0] = 1

for c in reversed(s):
    ch = (ch + int(c) * x) % 2019
    x = (x * 10) % 2019
    rem[ch] = rem[ch] + 1

print(sum(v * (v - 1)//2 for v in rem))

Submission status: Accepted

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

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

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

c = Counter(dp)

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

print(ans)

Submission status: Accepted

Solution code:
import collections
S = list(map(int, input()))[::-1]
mod_list = [0 for _ in range(len(S)+1)]
x = 0
d = 0
for i, s in enumerate(S):
    x += s * pow(10, d, 2019)
    d += 1
    mod_list[i] = x%2019
c = collections.Counter(mod_list)
ans = 0
for i in range(2020):
    ans += c[i] * (c[i]-1)//2
print(ans)

Submission status: Accepted

Solution code:
S=input()
N=len(S)
Slis=[]
for i in range(N):
  Slis+=[int(S[i])]
T=[0 for i in range(N+1)]#T[i]はi桁より右側の数字


ten=1

for i in range(N):
  T[N-i-1]=(T[N-i]+ten*Slis[N-i-1])%2019
  ten=(ten*10)%2019

MOD=[0 for i in range(2019)]
for i in range(N+1):
  tmp=T[i]%2019
  MOD[tmp]+=1


  
ans=0

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

Submission status: Accepted

Solution code:
S = input()
mod = 2019
rem = [0] * mod
rem[0] = 1
now = 0
for k,v in enumerate(S[::-1]):
  now += int(v) * pow(10,k,mod)
  rem[now % mod] += 1
ans = 0
for i in rem:
  ans += i * (i-1) // 2
print(ans)

Submission status: Accepted

Solution code:
from queue import deque


S = deque(input())
mod = 2019
T = [0] * mod
T[0] = 1
a, b = 0, 1

for _ in range(len(S)):
    s = int(S.pop())
    a = a + s * b
    a = a % mod
    T[a] += 1
    b = b * 10
    b = b % mod
    
print(sum((i * (i - 1) // 2 for i in T)))

Submission status: Accepted

Solution code:
m=2019
l=[0]*m
l[0]=1
s,k=0,1
for c in reversed(input()):k=k*10%m;s=(s+int(c)*k)%m;l[s]+=1
print(sum(v*(v-1)//2for v in l))

Submission status: Accepted

Solution code:
from queue import deque
 
    
S = deque(input())
y = 2019
U = [0] * y
t = 0
U[0] = 1
k = 1

for s in reversed(S):
    t = t + int(s) * k
    t %= y
    U[t] += 1
    k *= 10
    k %= y

cnt = 0
for u in U:
    cnt = cnt + u * (u - 1) // 2

print(cnt)

Submission status: Accepted

Solution code:
S = input()[::-1]
remain_table = [0] * 2019
remain_table[0] = 1
d = 1
chk = 0
for s in S:
    chk += int(s) * d
    chk = chk % 2019
    remain_table[chk] += 1
    d *= 10
    d %= 2019

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

Submission status: Accepted

Solution code:
s = input()
MOD = 2019
a =[0]*MOD
a[0] = 1
c_ = 0
ans = 0
t = 1
for i in reversed(s):
  c = (c_+int(i)*t)%MOD
  a[c] += 1
  t *= 10
  t %= MOD
  c_ = c
for i in a:
  ans += i*(i-1)//2
print(ans)

Submission status: Accepted

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

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

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

c = Counter(dp)

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

print(ans)

Submission status: Accepted

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

sum_of_digits = 0

cnts = [0] * 2019
cnts[0] = 1
d = 1

for c in S:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    cnts[sum_of_digits] += 1

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
def main():
    s = input()
    MOD = 2019
    r = [0]*MOD
    r[0] = 1
    z = 0
    t = 1
    for i in reversed(s):
        z = int(i) * t + z
        z %= MOD
        t *= 10
        t %= MOD
        r[z] += 1
    print(sum(i*(i-1)//2 for i in r))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
S = input()
MOD = 2019

cnt = [0] * MOD
cnt[0] = 1

now = 0
ans = 0
for d, n in enumerate(map(int, S[::-1])):
    now = (n * pow(10, d, MOD) + now) % MOD
    ans += cnt[now]
    cnt[now] += 1

print(ans)

Submission status: Accepted

Solution code:
S = str(input())[::-1]
N = len(S)
mod_list = [0]*2020
mod_list[0] = 1

mod = 2019
tmp = 0

for i in range(N):
    tmp = (tmp + int(S[i])*pow(10,i,mod))%mod
    mod_list[tmp] += 1
    
ans = 0
for i in mod_list:
    ans += i*(i-1)//2
        
print(ans)

Submission status: Accepted

Solution code:
def main():
    s = input()
    MOD = 2019
    r = [0]*MOD
    r[0] = 1
    z = 0
    t = 0
    for i in reversed(s):
        z = int(i) * pow(10,t,MOD) + z
        z %= MOD
        r[z] += 1
        t += 1
    print(sum(i*(i-1)//2 for i in r))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# D - Multiple of 2019

from collections import defaultdict
d = defaultdict(int)

mod = 2019
s = str(input())[::-1]

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

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

print(ans)

Submission status: Accepted

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

for i in s:
    tmp = int(i) * pow(10, d, mod) % mod
    tmp = cnt[-1] + tmp
    cnt.append(tmp % mod)
    d += 1

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

Submission status: Accepted

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


def solve(S: int):
    S =str(S)[::-1]
    MOD = 2019
    mod_l = [int(0)]*2019
    mod_l[0] = 1
    prev = 0
    for x in range(len(S)):
        k = int(S[x]) * pow(10, x, MOD) % MOD + prev
        mod_l[k%2019] += 1
        prev = k%2019

    s = sum([x*(x-1)//2 for x in mod_l])
    print(s)
    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 Counter

S = input()
mods = [0]
num, ten = 0, 1
for n in S[::-1]:
    num += int(n) * ten
    num %= 2019
    mods.append(num)
    ten *= 10
    ten %= 2019

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

Submission status: Accepted

Solution code:
def main():
    S = list(input())
    N = len(S)
    t = 0
    A = [0] * 2019
    A[0] += 1
    d = 1
    for s in reversed(S):
        d *= 10
        d %= 2019
        t += (int(s) * d)
        t %= 2019
        A[t] += 1
    result = sum([a*(a-1)//2 for a in A])
    print(result)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from math import gcd

S = list(map(int, list(read()[:-1])))
n = len(S)
F = [0] * (n + 1)  # [i,n)までを整数として見たときの余り
for i in ra(n, 0, -1):
    F[i - 1] = (F[i] + S[i - 1] * pow(10, n - (i - 1), 2019)) % 2019
cnt = Counter(F)
ans = 0
for v in cnt.values():
    ans += v * (v - 1) // 2
# print(F)
print(ans)

Submission status: Accepted

Solution code:
#create date: 2020-04-26 21:06

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    s = ns()
    n = len(s)
    now = 0
    m = [0] * 2019
    for i in range(n):
        now = (now + int(s[n-i-1]) * pow(10, i, 2019)) % 2019
        #print(now)
        m[now] += 1
    m[0] += 1
    ans = 0
    for mi in m:
        ans += (mi-1) * mi //2
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter

S = input()
mods = [0]
num, ten = 0, 1
for n in S[::-1]:
    num += int(n) * ten
    num %= 2019
    mods.append(num)
    ten *= 10
    ten %= 2019

counter = Counter(mods)
ret = 0
for v in counter.values():
    ret += v * (v - 1) // 2
print(ret)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
#from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
#from math import floor, ceil
#from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
#inf = 10**17
#mod = 10**9 + 7

s=input().rstrip()
u=list(map(int,list(s)))
u=list(reversed(u))
#print(u)
n=len(u)
beki=[0 for i in range(n)]
beki[0]=1
for i in range(n-1):
    beki[i+1]=(beki[i]*10)%2019
#print(beki)
dp=[0 for i in range(n)]
dp[0]=beki[0]*u[0]
for i in range(n-1):
    dp[i+1]=(dp[i]+beki[i+1]*u[i+1])%2019
dp.append(0)
#print(dp)
c=Counter(dp)
ans=0
for l in c.values():
    ans+=(l*(l-1))//2
print(ans)

Submission status: Accepted

Solution code:
s=input()
l=len(s)
ans=0
p=0
a={}
b=-1
c=-1
d=-1
e=-1
q=1
for j in range(l)[::-1]:
    p=(p+int(s[j])*q)%2019
    q*=10
    q%=2019
    if p==0:
        ans+=1
    if a.get(p)!=None:
        ans+=a[p]
    if a.get(p)!=None:
        a[p]+=1
    else:
        a[p]=1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
s = input()
n = len(s)
p = 2019
dd = defaultdict(int)
dd[0] = 1
prev = 0
for i in reversed(range(n)):
    prev = (prev+int(s[i])*pow(10, n-i, p)) % p
    dd[prev] += 1
print(sum(v*(v-1)//2 for v in dd.values()))

Submission status: Accepted

Solution code:
from collections import defaultdict
p = 2019
s = input()
n = len(s)
dd = defaultdict(int)
digits = 0
remainder = 0
for i in reversed(range(n)):
    x = (remainder+int(s[i])*pow(10, digits, p)) % p
    dd[x] += 1
    remainder = x
    digits += 1
ans = 0
for k, v in dd.items():
    if k == 0:
        ans += v
    ans += v*(v-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

dic = defaultdict(int)
dic[0] = 1

ans = 0

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

print (ans)

# print (dic)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
def cnt_multiple(s, p):
    # ABC158E, ABC164D
    n = len(s)
    if p != 2 and p != 5:
        a = []
        t = 1
        for i in range(n-1, -1, -1):
            a.append((ord(s[i])-ord("0")) * t % p)
            t = t * 10 % p
        cum = [0]
        for v in a:
            cum.append((cum[-1] + v) % p)

        dic = defaultdict(int)
        ans = 0
        for v in cum:
            ans += dic[v]
            dic[v] += 1
        return ans
    elif p == 2:
        ans = 0
        for i in range(n):
            if (ord(s[i]) - ord("0")) % 2 == 0:
                ans += i+1
        return ans
    else:
        ans = 0
        for i in range(n):
            if (ord(s[i]) - ord("0")) % 5 == 0:
                ans += i+1
        return ans
s = str(input())
n = len(s)
p = 2019

print(cnt_multiple(s, p))

Submission status: Accepted

Solution code:
S = input()
MOD = 2019
cnt = [0]*MOD
cur = 0 # 現在考えている部分文字列
cnt[cur] = 1 # 部分文字列'0'も作れると考える
d = 1 # 位を表す
for s in S[::-1]:
    cur += int(s)*d # 新たな桁を追加
    cur %= MOD
    cnt[cur] += 1
    # 後処理
    d *= 10 # 位を上げる
    d %= MOD # ただし数が巨大になるため、計算量を減らすために剰余をとる
ans = 0
for c in cnt:
    ans += c*(c-1)//2
print (ans)

Submission status: Accepted

Solution code:
from collections import Counter

s = input()
mod = 2019

li = [0]
num = 0
power = 1
for e in s[::-1]:
    num += int(e) * power
    num %= mod
    li.append(num)

    power *= 10
    power %= mod

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

Submission status: Accepted

Solution code:
s = input()

n = len(s)
amari = [0] * 2019
amari[0] += 1
tmp = 0
digit = 1
for i in range(n):
    tmp += int(s[n-i-1]) * digit
    tmp %= 2019
    amari[tmp] += 1
    digit = (digit * 10) % 2019

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

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = list(map(int, input()))
MOD = 2019
cnt = 0
M = len(N)
ans = 0
mod_list = [0]
ten = 1

for n in N[::-1]:
    ans += ten*n
    mod_list.append(ans%MOD)
    ten *= 10
    ten %= MOD

SUM = 0
for k,v in Counter(mod_list).items():
    SUM += v * (v-1) /2

print(int(SUM))

Submission status: Accepted

Solution code:
MOD = 2019
class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self
    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

S=input()
m=[0]*MOD
m[0]=1
now=Mint()
ans=0
for i in range(1,len(S)+1):
    now += Mint(int(S[-i])) * pow(10,i-1,MOD)
    ans += m[now.value]
    m[now.value] += 1
print(ans)

Submission status: Accepted

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

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

num = 0
d = 1

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

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
def resolve():
    s = [int(num) for num in input()]

    ten = 1
    num = 0
    mod_table = np.zeros(shape=2019, dtype=int)

    for i in range(len(s)):
        num += s[len(s) - i - 1] * ten
        num %= 2019
        mod_table[num] += 1
        ten = (ten * 10) % 2019

    ans = sum((mod_table * (mod_table - 1)) // 2)
    ans += mod_table[0]
    print(ans)
    
resolve()

Submission status: Accepted

Solution code:
from collections import Counter


def f(mod):
    ret = [0]
    power = 1
    num = 0
    for i, e in enumerate(s, 1):
        num *= 10
        num += int(e)
        num %= mod

        power *= 10
        power %= mod
        inv = pow(power, mod - 2, mod)

        ret.append(num * inv % mod)

    return ret


s = input()

mod3 = f(3)
mod673 = f(673)

li = [10 * e673 + e3 for e3, e673 in zip(mod3, mod673)]

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

Submission status: Accepted

Solution code:
def main():
    s = list(map(int, list(input())))
    m = [0]*2019
    num = 0
    ans = 0
    n = len(s)
    ten = 1
    for i in range(n):
        num += s[n-i-1]*ten
        num %= 2019
        m[num] += 1 
        ten = (ten*10)%2019
    for mi in m:
        if mi:
            ans += (mi*(mi-1))//2
    ans += m[0]
    print(ans)
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import collections
input = sys.stdin.readline

s = input().strip()
n = len(s)
cnt = collections.defaultdict(int)
cnt[0] = 1
res = sm = 0
p10 = 1
for d in reversed(s):
	sm = (sm + int(d) * p10) % 2019
	res += cnt[sm]
	cnt[sm] += 1
	p10 = p10 * 10 % 2019
print(res)

Submission status: Accepted

Solution code:
def main():
    s = input()
    n = len(s)
    s = s[::-1]
    t = [0]*n
    a = [0]*2020
    x = 1
    ans = 0
    for i in range(n):
        if 0 < i:
            t[i] += t[i-1]
        v = int(s[i])
        v *= x
        t[i] += v
        t[i] %= 2019
        ans += a[t[i]]
        if t[i] == 0:
            ans += 1
        a[t[i]] += 1
        x *= 10
        x %= 2019
    print(ans)
#    print(t)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
S = [int(a) for a in input()[::-1]]
m = 2019
N = len(S)
s = 0
p = 1
X = [0] * 2019
X[0] = 1
ans = 0
for a in S:
    s = (s + a * p) % m
    ans += X[s]
    X[s] += 1
    p = p * 10 % m
 
print(ans)

Submission status: Accepted

Solution code:


from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline




def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

#S=list(map(int,list(input())[:-1]))[::-1]
S=list(map(int,list(input())[:-1]))
#print(S)

N=len(S)
smod=[0]*N
bef=0
b=1

for i in range(len(S)):
    l=N-i-1
    bef+=(S[l]*(b))%2019
    smod[l]=bef%2019
    #smod.append(bef%2019)
    b=(b*10)%2019
    
cnt=[0]*2020
for sm in smod:
    cnt[sm]+=1

cnt[0]+=1

res=0
for sc in cnt:
    res+=sc*(sc-1)/2
    
    
print(int(res))

#print(smod)

#print(cnt[:10])

Submission status: Accepted

Solution code:
import collections
s = list(input())
n = len(s)
mod = [0]*(n+1)
pow10 = 1
for i in range(n):
    mod[i+1] = (mod[i] + int(s[-1-i])*pow10)%2019
    pow10 = pow10*10%2019
d = collections.Counter(mod)
ans = 0
for i in d.values():
    ans += i*(i-1)//2
print(ans)

Submission status: Accepted

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

def main():
  s = input().strip()
  x = remain = 0
  remains = [0] * 2019
  k = 1
  for d in map(int, list(s[::-1])):
    x = d * k + remain
    remain = x % 2019
    k = (10 * k) % 2019
    remains[remain] += 1

  print(sum([(remain * (remain - 1)) // 2 for remain in remains]) + remains[0])
  
if __name__=='__main__':
  main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
s = input()
n = len(s)
# 累積和の準備
sum_list = [0]*(n+1)  # s[0]は０であってほしいから配列数ひとつおおい
_10 = 1
for i in range(1, n + 1):
    sum_list[i] += (sum_list[i-1] + int(s[n-i])*_10 % 2019) % 2019  # ここでmodしておく
    _10 = _10*10 %2019
"""
(s[j]-s[i]/10**i)が区間の整数
区間の整数が2019で割り切れればよい
つまり、(s[j]-s[i]/10**i)≡0 (mod=2019)
ここで10**iと2019(素数)は互いに素なので、
10**iをかけて上の式はs[j]-s[i]≡0 (mod=2019)と同値
s[j]≡s[i] (mod=2019)となる。
"""
c = Counter(sum_list)
ans = 0

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

Submission status: Accepted

Solution code:
S=input()
k=[0]*2019
t=0
k[0]=1
for i,s in enumerate(S[::-1]):
  t+=int(s)*pow(10,i,2019)
  t%=2019
  k[t]+=1
  
ans=0
for l in k:
  ans+=l*(l-1)//2
print(ans)

Submission status: Accepted

Solution code:
S = input()

## 後ろの桁から処理したいので配列を逆転する
S = S[::-1]

## 累積和の配列
cs = [0] * (len(S) + 1)

## 桁
d = 1

for i in range(len(S)):
  ## i+1桁目の2019で割った余り
  m = (int(S[i]) * d) % 2019

  ## 累積和を求める
  ## 同じあまりの数が知りたいので、こちらも2019で割った余りを保存する
  cs[i+1] = (cs[i] + m) % 2019

  ## 次の位へ
  d *= 10

  ## 位が大きくなるのでこれも余りをとっておく
  d %= 2019


res = 0
c = [0] * 2019

## 同じあまりの値がいくつあるか数える
for n in cs:
  c[n] += 1

## 同じ値あまりの数を重複なく２つ選ぶ場合の数の合計が答え
for n in c:
  # nC2
  res += n * (n - 1) // 2


print(res)

Submission status: Accepted

Solution code:
import collections
 
S = input()
l = [0]
a = 0
b = 1

for i in range(1,len(S)+1):
  a = (a+int(S[-i])*b)%2019
  l.append(a)
  b = (b*10)%2019
  

c = collections.Counter(l)
 
rlt = 0
for k in c:
  rlt += c[k]*(c[k]-1)//2

print(rlt)

Submission status: Accepted

Solution code:
S=input()
n=len(S)
t=[0]*(n+2)
b=[0]*2019
m=0
mod2019_10=[0]*(n+1)
#print(S[n-1])
t[n+1]=0
t[n]=int(S[n-1])%2019
mod2019_10[0]=1
for i in range(1,n+1):
    mod2019_10[i]=(mod2019_10[i-1]*10)%2019
for i in range(1,n):
    t[n-i]=(t[n-i+1]+(int(S[n-i-1])*mod2019_10[i])%2019)%2019
#print(t[n-1],t[n-4])
for i in range(1,n+2):
    b[t[i]]+=1
#print(b[0])
for i in range(2019):
    if b[i]>=2:
        m=m+(int(b[i]*(b[i]-1)/2))
print(m)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    count = [0] * 2019
    count[0] = 1
    val = 0
    res = 0
    for i, d in enumerate(reversed(input())):
        d = int(d)
        val += d * pow(10, i, 2019)
        val %= 2019
        res += count[val]
        count[val] += 1
    print(res)
resolve()

Submission status: Accepted

Solution code:
import collections
s = input()

l = [int(s[-1])]
d = 10
for i in range(len(s)-2, -1, -1):
  l.append((l[-1] + int(s[i])*d) % 2019)
  d *= 10
  d %= 2019
c = collections.Counter(l)
ans = 0  
for i in c.values():
  ans += i*(i-1)//2

ans += c[0]

print(ans)

Submission status: Accepted

Solution code:
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
# import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""
from collections import deque, defaultdict, Counter
import math
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))
# WideIntPoint


def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  # SingleInt


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  # HeightString


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  # MatrixInt


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  # NumberGrid


def grid(n): return [s_list() for _ in range(n)]


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# a/b の切り上げ


def round_up(a, b):
    """ a/b の切り上げ """
    c = (a + b - 1) / b
    return c


def lcm(a, b):
    """a,bの最小公倍数"""
    return a * b // gcd(a, b)


def main():
    s = input()[::-1]

    cnt = [0] * 2019
    # print(cnt)
    cnt[0] = 1
    ans = 0
    b = 0
    t = 1
    for i in s:
        b = b + int(i) * t
        b %= 2019
        cnt[b] += 1
        t *= 10
        t %= 2019

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

S = input()
N = len(S)

dp = [0] * N
dp[N-1] = int(S[N-1])
times = 10
for i in reversed(range(1, N)):
    dp[i-1] = (dp[i] + times * int(S[i-1])) % 2019
    times *= 10
    times %= 2019

T = Counter(dp)
ans = T[0]
for t in T.values():
    ans += t*(t-1)//2

print(ans)

Submission status: Accepted

Solution code:
M=2019;t=1;p=r=0;c=[0]*M
for x in'0'+input()[::-1]:p+=int(x)*t;p%=M;t=t*10%M;r+=c[p];c[p]+=1
print(r)