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 = list(input())
p = [0 for i in range(2019)]
n = len(s)
ans = 0
kar = 0
dig = 1
for i in range(n):
    kar = (kar + int(s[n-1-i])*dig)%2019
    dig = (dig*10)%2019
    p[kar] += 1

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

Submission status: Accepted

Solution code:
import math
s = input()
n = len(s)
count = 0
a = [0 for i in range(2019)]
a[0] = 1
k = 0
b = [0 for i in range(n)]
b[0] = 1
for i in range(1, n):
    b[i] = b[i-1]*10 % 2019

#print(b)
for i in reversed(range(0, n)):
 #   print((b[n-i-1])*int(s[i]) % 2019)
    k += (b[n-i-1])*int(s[i]) % 2019
  #  print(k, k % 2019)
    a[k % 2019] += 1

for i in range(len(a)):
    if a[i] >= 2:
        count += (a[i])*(a[i]-1)//2
print(count)

Submission status: Accepted

Solution code:
S = input()
P = 2019
N = len(S)
num = [0] * P
num[0] = 1
c = 0
ans = 0
dgt = 1
for i in range(N-1, -1, -1):
    c = (c + int(S[i]) * dgt) % P
    dgt *= 10
    dgt %= P
    ans += num[c]
    num[c] += 1

print(ans)

Submission status: Accepted

Solution code:
S=input()
N=len(S)
R=[0]*(N+1)
mul=1
for i in range(1,N+1):
    R[-(i+1)]=(((int(S[-i])*mul))%(2019)+R[-i])%2019
    mul*=10
    mul%=2019
#print(R)
L=[0]*2019
for r in R:
    L[r]+=1
ans=0
for l in L:
    if l>=2:
        ans+=l*(l-1)//2
print(ans)

Submission status: Accepted

Solution code:
S=str(input())
l=len(S)
ans=0
dig=1
mod=[0]*2019
mod[0]=1
t=0
for i in range(l):
    t=(t+int(S[-i-1])*dig)%2019
    mod[t]+=1
    dig=(dig*10)%2019
    
for j in mod:
    ans=ans+(j*(j-1))//2
print(ans)

Submission status: Accepted

Solution code:
n = input()

MOD = 2019
ans = 0
dp = [0]*MOD
dp[0] = 1
temp = 0

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

for item in dp:
    if item > 1:
        ans += item*(item-1)//2

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

mod = 2019

s = input().rstrip()
n = len(s)

t = [int(s[n - 1])]

mul = 10
for i in range(n - 2, -1, -1):
    t.append((t[-1] + int(s[i])*mul) % mod)
    mul *= 10
    mul %= mod
t.append(0)

from collections import Counter

c = Counter(t)
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import collections

def main():
    S = str(input())
    n = len(S)

    T = [-1 for i in range(n+1)]
    T[-1] = 0
    # for i in range(n):
    #     #print(S[i:])
    #     T[i] = int(S[i:]) % 2019
    # print(T)
    b = [1 for i in range(n)]
    for i in reversed(range(n-1)):
        b[i] = b[i+1]*10 % 2019
    #print(b)

    # for i in reversed(range(n)):
    #     T[i] = (int(S[i])*10**(n-1 -i) + T[i+1]) % 2019
    # print(T)

    for i in reversed(range(n)):
        T[i] = (b[i]*int(S[i]) + T[i+1]) % 2019
    #print(T)


    C = collections.Counter(T)
    #print(C) # dict 型のサブクラス，Counter
    ans = 0
    for value, count in C.items():
        ans += int(count*(count-1)/2)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

    reminder = [0]*mod
    pre_rem = 0

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

    ans = reminder[0]
    for rem_num in reminder:
        if rem_num >= 2:
            ans += (rem_num * (rem_num -1))//2
    print(ans)
    
solve()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
S = list(input())
L = [0]*2019
L[0]=1
digit = 1
x = 0

for i in S[::-1]:
    x += digit*int(i)
    digit *= 10
    x %= 2019
    digit %= 2019 
    L[x] += 1

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
S = input()
l = len(S)
a = [0]
b = [0]*2019
c = [1]
d = 0
e = 0
for n in range(l-1):
    c.append(c[n]*10%2019)
for n in range(l):
    d += int(S[-n-1])*c[n]
    a.append(d%2019)
for n in range(l+1):
    b[a[n]] += 1
for n in range(2019):
    e += int(b[n]*(b[n]-1)/2)
print(e)

Submission status: Accepted

Solution code:
S = input()

mod = [0] * 2019
mod[0] = 1
digit = 1
temp = 0
 
for i in S[::-1]:
    temp = (temp + digit * int(i)) % 2019
    mod[temp] += 1
    digit = (digit * 10) % 2019

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

print(ans)

Submission status: Accepted

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

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

ans = 0
for count in counts:
    if count > 1:
        # print(i)
        ans += count * (count-1) //2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections
S = input()
cnt = 0

mod = [0]
reverse_S = S[::-1]
for i in range(len(reverse_S)):
  now = int(reverse_S[i]) * pow(10,i,2019)
  mod.append((now + mod[i]) % 2019)


c = collections.Counter(mod)
hindo = sorted(c.values(),reverse=True)
for i in hindo:
  if i != 1:
    cnt += i*(i-1)//2


print(cnt)

Submission status: Accepted

Solution code:
S = input().strip()
p = 2019
t = 1
y = 0
c = [0] * p
c[y] += 1
for x in map(int, S[::-1]):
    y = (y + t*x) % p
    c[y] += 1
    t = (t*10) % p
print(sum(i*(i-1)//2 for i in c))

Submission status: Accepted

Solution code:
S=input()
N=len(S)
M=2019

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

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

Submission status: Accepted

Solution code:
import collections
S = input()
cnt = 0

mod = [0]
reverse_S = S[::-1]
for i in range(len(reverse_S)):
  now = int(reverse_S[i]) * pow(10,i,2019)
  mod.append((now + mod[i]) % 2019)


c = collections.Counter(mod)
hindo = c.values()
for i in hindo:
  if i != 1:
    cnt += i*(i-1)//2


print(cnt)

Submission status: Accepted

Solution code:
def solve(s):
    dp = [0] * 2019
    dp[0] = 1
    r = 0
    for i in range(1, len(s) + 1):
        r += int(s[-i]) * pow(10, i - 1, 2019)
        r %= 2019
        dp[r] += 1
    res = 0
    for r in range(2019):
        res += dp[r] * (dp[r] - 1) // 2
    return res


def main():
    s = input()
    res = solve(s)
    print(res)


def test():
    assert solve("1817181712114") == 3
    assert solve("14282668646") == 2
    assert solve("2119") == 0


if __name__ == "__main__":
    test()
    main()

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:
import math
s=input()
n=len(s)
count=0
a=[0 for i in range(2019)]
a[0]=1
k=0
b=[0 for i in range(n)]
b[0]=1
for i in range(1,n):
    b[i]=b[i-1]*10%2019
for i in reversed(range(0,n)):
    k+=(b[n-i-1])*int(s[i])%2019
    a[k%2019]+=1        
for i in range(len(a)):
    if a[i]>=2:
        count+=(a[i])*(a[i]-1)//2
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#n,p = map(int,input().split())
s=input()
p = 2019
ans = 0
l = [0 for i in range(p)]
l[0] = 1
z = 0
ten = 1
tmp = 0
for i in s[::-1]:
    i = int(i)
    tmp=(tmp+i*ten)%p
    ten = (ten*10)%2019
    l[tmp]+=1
for i in l:
    ans+= i*(i-1)//2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S = input()[::-1]
P = [0]*(len(S)+1)
for i,j in enumerate((S)):
    P[i+1] = (P[i] + int(j)*pow(10,i,2019))%2019
 
dp = [0]*2019
for i in P:
    dp[i%2019] += 1
print(sum([i*(i-1)//2 for i in dp]))

Submission status: Accepted

Solution code:
S = input()[::-1]
P = [0]*(len(S)+1)
a = 0
for i,j in enumerate((S)):
    a = (a+int(j)*pow(10,i,2019))%2019
    P[i] = a

dp = [0]*2019
for i in P:
    dp[i%2019] += 1
print(sum([i*(i-1)//2 for i in dp]))

Submission status: Accepted

Solution code:
import numpy
import math


def main():
    S = input()
    Mod = [0 for i in range(2019)]
    Mod[0] = 1
    d = 1
    tmp = 0
    ans = 0
    for c in reversed(S):
        tmp = (d * int(c) + tmp) % 2019
        ans += Mod[tmp]
        #print(tmp, ans)
        Mod[tmp] += 1
        d = (d * 10) % 2019

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
S = input()
N = len(S)
table = [1] + [0] * 2020
exp = [1]
for i in range(N):
    exp += [exp[-1]*10 %2019]

curr = 0
for i in range(N):
    curr += int(S[N-1-i])*exp[i]
    curr %= 2019
    table[curr] += 1

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

Submission status: Accepted

Solution code:
s = input() #sys.stdin.readlineは最後が改行
n =len(s)

from collections import defaultdict
amari = defaultdict(lambda:0)
amari[0]=1
num=0
tmp=0

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

from math import factorial

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

print(ans)

Submission status: Accepted

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

mod = 2019

d = {}
d[0] = 1
t, p = 0, 1
for i in range(n-1, -1, -1):
	t = (t + p * int(s[i])) % mod
	d[t] = d.get(t, 0) + 1
	p = p * 10 % mod

print(sum(x * (x - 1) // 2 for x in d.values()))

Submission status: Accepted

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce


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


def INT(): return int(input())


def MAP(): return map(int, input().split())


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


def ZIP(n): return zip(*(MAP() for _ in range(n)))


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    S = input()
    N = len(S)

    lis = [0]*2019
    lis[0] = 1

    ct = 0
    for i, x in enumerate(reversed(S)):
        ct += int(x) * pow(10, i, 2019)
        ct %= 2019
        lis[ct] += 1

    ans = 0

    for x in lis:
        if x != 0:
            ans += x*(x-1)//2

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input() #sys.stdin.readlineは最後が改行
n =len(s)

from collections import defaultdict
amari = defaultdict(lambda:0)
amari[0]=1
num=0
tmp=0
ans =0

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

    if amari[tmp]>1:
        val = amari[tmp]
        ans -= (val-1)*(val-2)//2
        ans += (val)*(val-1)//2

print(ans)

Submission status: Accepted

Solution code:
S = input()
T = [0]*2019
T[0]=1
t = 0
ans = 0
dig = 1
for i in range(len(S)):
    t = (t + (int(S[-i-1]))*dig)%2019
    dig = (dig*10)%2019
    T[t] += 1
for j in T:
    ans +=int(j*(j-1)/2)
print(ans)

Submission status: Accepted

Solution code:
N = input()
a = [0] * 2050
n = 0
p = 1
for i in range(len(N)):
    n += int(N[len(N)-1-i]) * p
    p *= 10
    p %= 2019
    a[int(n) % 2019] += 1
ans = 0
for i in range(2019):
    if i == 0:
        ans += a[i] * (a[i]+1) // 2
    else:
        ans += (a[i]-1) * a[i] // 2
print(ans)

Submission status: Accepted

Solution code:
def D():
    s = input()
    mods = [0]*2019
    mods[0] = 1
    mod = 0
    for i, element in enumerate(s[::-1]):
        mod += int(element)*pow(10,i,2019)
        mods[mod%2019] += 1
    print(sum(map(lambda x:int(x*(x-1)/2), mods)))
D()

Submission status: Accepted

Solution code:
def main(): #なんか早くなるおまじない
    import sys
    from collections import defaultdict
    dic = defaultdict(int)

    input = sys.stdin.readline #早くなるおまじない

    s = str(input().rstrip())
    m = 0

    for i in range(1, len(s) + 1):
        m_1 = pow(10, i-1,2019)
        m_add = (int(s[-i]) * m_1) % 2019
        m = (m_add + m) % 2019
        dic[m] += 1

    ans1 = 0

    for x in dic.values():
        if x > 1:
            ans1 += x * (x - 1) // 2
    ans2 = dic[0]

    print(ans1 + ans2)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 解説を参考に作成
# さらに 提出 #12403542 を参考


def solve():
    S = input()
    lenS = len(S)
    mod_list = [0] * 2019
    x = 0
    for i in range(lenS):
        x = (int(S[lenS - 1 - i]) * pow(10, i, 2019) + x) % 2019
        mod_list[x] += 1

    result = 0
    for i, ml in enumerate(mod_list):
        if i == 0:
            result += ml
        result += int(ml * (ml - 1) / 2)
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
s = list(map(int, list(input())))
s.reverse()
ss = [s[0]]
n = len(s)
mod_digit = 10
for i in range(1, n):
    ss.append((s[i]*mod_digit+ss[i-1])%2019)
    mod_digit = mod_digit*10%2019
keys = [i for i in range(2019)]
counter = {key:0 for key in keys}
for i in range(n):
    counter[ss[i]] += 1
def mC2(m):
    return m*(m-1)//2
ans = 0
for key, item in counter.items():
    ans += mC2(item)
ans += counter[0]
print(ans)

Submission status: Accepted

Solution code:
S=input()

out=0
l=[0]*2019
x=0
now=1
for i in S[::-1]:
    x+=now*int(i)
    x%=2019
    l[x]+=1

    now*=10
    now%=2019

for i in l:
    out+=(i-1)*i//2
print(out+l[0])

# # 全探索は間に合わない
# D=len(S)-4
# for ii in range(D+1):
#     for i in range(ii+3,len(S)):
#         T=S[ii:i+1]
#         if int(T)%2019==0:
#             out+=1
# print(out)

Submission status: Accepted

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


def main():
    S = input()
    N = len(S)

    mod_count = [0] * 2019
    mod_count[0] = 1
    ssum = 0
    for i, c in enumerate(S[::-1]):
        ssum = (ssum + int(c) * pow(10, i, 2019)) % 2019
        mod_count[ssum] += 1

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# if the remainders (mod 2019) are equal, the difference will be divisible
# x = Q*2019+5 y = R*2019+5 then x-y=(Q-R)*2019
# unless Q-R<=0
# where the substring itself is (Q-R)*2019/10**(something)
from collections import Counter
s = input()[::-1]
partial = 0
remainders = list()
num = (int(character) for character in s)
for i, int_char in enumerate(num):
  partial = (partial+(int_char*pow(10,i,2019))%2019)%2019
  remainders.append(partial)
histo = Counter(remainders)
non_single_count = int(sum(count*(count-1)/2 for value, count in histo.items() if value!=0))
single_count = int(sum(count+count*(count-1)/2 for value, count in histo.items() if value==0))
print(non_single_count+single_count)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = sr()
mod_cnt = [0] * 2019
mod_cnt[0] = 1
power = 1
remain = 0
answer = 0
for i in range(len(S)-1, -1, -1):
    remain += int(S[i]) * power
    remain %= 2019
    power *= 10; power %= 2019
    answer += mod_cnt[remain]
    mod_cnt[remain] += 1

print(answer)

Submission status: Accepted

Solution code:
S = input()
mod_bucket = [0] * 2019
mod_bucket[0] = 1
 
_S = S[::-1]
mod = 0
p = 1
for i in range(len(S)):
    mod = (p * int(_S[i]) + mod) % 2019
    mod_bucket[mod] += 1
    p = p*10%2019

ans = sum([mod*(mod-1)/2 for mod in mod_bucket])
print(int(ans))

Submission status: Accepted

Solution code:
# 2019は10と互いに素なので、
# N%2019と(N*(10**正整数))%2019は一致する
# pppppxxxxxxxを2019で割った余りとxxxxxxxを2019で割った余りが一致すれば、
# pppppは2019で割り切れることが言える

S = input()
from collections import defaultdict
amari = defaultdict(int)
cur = 0 # 今の数値
keta = 1 # 今の桁数
for i in range(len(S)-1,-1,-1):
  cur += int(S[i]) * keta
  cur %= 2019
  keta *= 10
  keta %= 2019
  amari[cur] += 1

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:
import sys
sys.setrecursionlimit(300000)
from collections import Counter

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


S = input()

m = [0]
pow = 1
for i in range(len(S)):
    m.append((m[-1] + int(S[- i - 1]) * pow) % 2019)
    pow = (pow * 10) % 2019


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

Submission status: Accepted

Solution code:
S = input()

ans = 0
lists = [0 for i in range(2019)]
lists[0] += 1

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

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

print(ans)

Submission status: Accepted

Solution code:
s = input()
ans = 0
# 2019までの余りの分布
U = [0 for i in range(2019)]
mod = 2019
sum_i_to_n = 0
for i in range(len(s)-1, -1, -1):
    # 後ろから見てく
    sum_i_to_n += int(s[i]) * pow(10, len(s)-i-1, mod)
    sum_i_to_n %= mod
    if sum_i_to_n % mod == 0:
        # 2019で割り切れたら
        ans += 1
    # 1817181712114と81712114はあまりが同じ。
    # 二つの差の1817100000000は2019の倍数よって18171も2019の倍数
    ans += U[sum_i_to_n]
    U[sum_i_to_n] += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

S = input()
B = defaultdict(int)
B[0]=1
ans=0
prev=0

for i in range(len(S)):
    m=(prev+int(S[-i-1])*pow(10,i,2019))%2019
    ans+=B[m]
    B[m]+=1
    prev=m

print(int(ans))

Submission status: Accepted

Solution code:
S = input()[::-1]
S_l = len(S)
MOD = 2019
l = [0]*(S_l+1)
ans_l = [0]*2020
l[0] = 0
l[1] = int(S[0]) 
ans_l[0]+=1
ans_l[int(S[0])]+=1

for i in range(2,S_l+1):
  l[i] = (int(S[i-1]) * pow(10,i-1,MOD) + l[i-1])%MOD
  ans_l[l[i]]+=1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
S = list(input())
N = len(S)

l = [0] * 2019
temp = 0
e = 1
for i in range(N-1, -1, -1):
    temp += int(S[i]) * e
    temp %= 2019
    l[temp] += 1
    e *= 10
    e %= 2019

ans = l[0]

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

print(ans)

Submission status: Accepted

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

temp = [0]*2019
t = 1
num = 0
for i in range(n):
    num += int(s.pop())*t 
    temp[num % 2019] += 1
    t = t*10 % 2019 

ans = temp[0]
for t in temp:
    if t > 1:
        ans += t*(t-1)/2

print(int(ans))

Submission status: Accepted

Solution code:
S = input()
mod_bucket = [0] * 2019
mod_bucket[0] += 1

_S = S[::-1]
mod = 0
p = 1
for i in range(len(S)):
    mod = (p * int(_S[i]) + mod) % 2019
    mod_bucket[mod] += 1
    p *= 10
    p %= 2019

ans = sum([mod*(mod-1)/2 for mod in mod_bucket])
print(int(ans))

Submission status: Accepted

Solution code:
S=input()
N=len(S)
M=2019

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

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

Submission status: Accepted

Solution code:
from sys import stdin
#import numpy as np


def merge_sort(lst, low, high):
    if low >= high:
        return
    mid = int((low+high)/2)
    merge_sort(lst, low, mid)
    merge_sort(lst, mid+1, high)
    for i in range(low, mid+1):
        tmp_array[i] = lst[i]
    j = high
    for i in range(mid+1, high+1):
        tmp_array[i] = lst[j]
        j -= 1
    i = low
    j = high
    for k in range(low, high+1):
        if tmp_array[i] <= tmp_array[j]:
            lst[k] = tmp_array[i]
            i += 1
        else:
            lst[k] = tmp_array[j]
            j -= 1


S = stdin.readline().rstrip()
N = len(S)
Sp = S

res_map = [0 for _ in range(N)]

aa_list2 = [1]
for i in range(1,N):
    aa_list2.append((aa_list2[i-1]*10)%2019)

tmp_array = [None for _ in range(N)]
res_map[N-1] = int(S[N-1])
index=1
for i in range(N-2,-1,-1):
    res_map[i] = (int(S[i])*aa_list2[index] + res_map[i+1])%2019
    index+=1

res_map.sort()
temp_num=int(res_map[0])
index=1
tot = 0

aa_table = [0 for i in range(2019)]
aa_table2 = [0 for i in range(2019)]
for i in range(len(res_map)):
    aa_table2[res_map[i]]+=1

aa_table2[0]+=1

#sort check
for i in range(1,N):
    if res_map[i]<res_map[i-1]:
        aa = 2/0

for i in range(1,len(res_map)):
    if temp_num==int(res_map[i]):
        index+=1
        if i==len(res_map)-1:
            aa_table[temp_num]=index
        continue
    else:
        aa_table[temp_num] = index
        index=1
        temp_num=int(res_map[i])
        if i==len(res_map)-1:
            aa_table[temp_num]=1

aa_table[0] += 1 


tot = 0
for i in range(2019):
    tot+=int((aa_table[i]-1)*aa_table[i]/2)



#for i in range(2018):
#    num = np.sum(np.array(res_map)==i)
#    if i ==0:
#        num+=1
#    tot += int(num*(num-1)/2)
    

print(tot)

Submission status: Accepted

Solution code:
def main():
    s = input()
    d = [0]*2019
    d[0] += 1
    now = 0
    for j, i in enumerate(s[::-1]):
        now = (int(i)*pow(10, j, 2019)+now) % 2019
        d[now] += 1
    print(sum([i*(i-1)//2 for i in d]))


main()

Submission status: Accepted

Solution code:
s = input()
mod = 2019
array = [0]*(len(s)+1)

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

    
array.sort()

cnt = 0
w = 1

for i in range(0, len(array)-1):
    if array[i] == array[i+1]:
        w += 1
    else:
        if w >= 2:
            cnt += w*(w-1)/2
            w = 1
            
if w != 1:
    cnt += w*(w-1)/2
    
print(int(cnt))

Submission status: Accepted

Solution code:
S=input()
mem_mod = [0 for i in range(0,2019,1)]
N = len(S)
counter = 0
S_num_tmp = list(S)
S_num = list(map(int, S_num_tmp))
tmp=10

for i in range(1,N,1):
    S_num[N-i-1] = S_num[N-i] + S_num[N-i-1]*pow(10,i,2019)

for i in range(0,N,1):
    X = S_num[N-i-1] % 2019
    if X==0:
        counter+=1
    counter += mem_mod[X]
    mem_mod[X] += 1
print(counter)

Submission status: Accepted

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

S = input().strip()
l = len(S)
dic = {0:[-1]}
ans = 0
base = 1
mod = 0
for i in range(0, l):
    base = (10 * base) % 2019
    s = base * int(S[l-1-i]) + mod
    mod = s % 2019
    if mod in dic:
        dic[mod].append(i)
    else:
        dic[mod] = [i]

for key, val in dic.items():
    v_len = len(val)
    ans += (v_len * (v_len -1))// 2

print(ans)

Submission status: Accepted

Solution code:
S = input()
count = 0
exist = [0]*2019
flg = False
N = len(S)
sum = 0
for i, s in enumerate(reversed(S)):
    sum += (int(s) * pow(10, i, 2019)) % 2019
    exist[sum % 2019] += 1
for e in exist:
    if e > 1:
        count += e*(e-1)//2
count += exist[0]
print(count)

Submission status: Accepted

Solution code:
arr = [0 for i in range(2019)]
arr[0] = 1

s = input()
n = len(s)

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


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

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

S = input()

T = [0]
for i, a in enumerate(map(int, reversed(S))):
    T.append((a * pow(10, i, 2019) + T[-1]) % 2019)

print(sum(m * (m - 1) // 2 for m in Counter(T).values()))

Submission status: Accepted

Solution code:
from collections import Counter

S = list(input())
T = [int(S[len(S)-1])]
k = int(S[len(S)-1])
for i in range(len(S)-2,-1,-1):
    k = (int(S[i])*pow(10,len(S)-i-1,2019) + k ) % 2019
    T.append(k)

A = Counter(T)
ans = 0
ans += A.get(0,0)
for i in A.values():
    ans += i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
s=input()
n=len(s)
w2019=[1]
i=0
for i in range(i,n):
  w2019.append((w2019[-1]*10)%2019)
v=[int(s[-1])]
for i in range(1,n):
  v.append((v[-1]+int(s[-(i+1)])*w2019[i])%2019)
v.sort()
cnt=0
co=0
if v[0]==0: cnt+=1
for i in range(1,n):
  if v[i]==v[i-1]: co+=1
  elif co!=0:
    cnt+=co*(co+1)//2
    co=0
  if v[i]==0: cnt+=1
cnt+=co*(co+1)//2
print(cnt)

Submission status: Accepted

Solution code:
from numba import njit
from numpy import int32,zeros,arange
@njit('i4(i4[:])')
def solve(s):
    a=0
    d=zeros(2019,int32)
    for i in s:
        p=zeros(2019,int32)
        for j in range(2019):p[(j*10+i)%2019]+=d[j]
        d=p
        d[i]+=1
        a+=d[0]
    return a
print(solve(int32([*input()])))

Submission status: Accepted

Solution code:
from collections import defaultdict
s = list(input())[::-1]
n = len(s)
dic = defaultdict(int)
dic[0] = 1
t = 0
for i in range(n):
    t += int(s[i])*pow(10,i,2019) % 2019
    t %= 2019
    dic[t] += 1
ans = 0
for i in dic.keys():
    m = dic[i]
    ans += m*(m-1)//2
print(ans)

Submission status: Accepted

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

ans = 0
x = [0] * N
x[0] = int(S[0]) % mod
ruijo = 10

for i in range(1, N):
    x[i] = (ruijo * int(S[i]) + x[i - 1]) % mod
    if x[i] % mod == 0:
        ans += 1
    ruijo *= 10
    ruijo %= mod
    
d = collections.Counter(x)

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

Submission status: Accepted

Solution code:
s=[int(i) for i in input()]
s.reverse()

a=0
l=[0 for i in range(2019)]
l[0]=1
b=0.1
for i in range(len(s)):
  b=int(b*10)
  b%=2019
  a+=s[i]*b
  a%=2019
  l[a]+=1

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

Submission status: Accepted

Solution code:

S = input()

mod = 2019
ctr = [0] * mod
t = 0
for i, v in enumerate(reversed(S)):
    t = (t + int(v) * pow(10, i, mod)) % mod
    ctr[t] += 1

ans = ctr[0]
for v in ctr:
    ans += v * (v - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
S = input()

n_i_to_j_mod = [0] * (2019+1) # 2019で割った余りがiになるようなSの部分連続文字列の個数
i_to_end_mod = [0] * (len(S)+1) # S[-i:](Sの後方i文字)を2019で割ったときの余り

for i in range(1, len(S)+1):
    if i == 1:
        i_to_end_mod[1] = int(S[-1]) % 2019
    else:
        i_to_end_mod[i] = (i_to_end_mod[i-1] + int(S[-i]) * pow(10, i-1, 2019)) % 2019
    n_i_to_j_mod[i_to_end_mod[i]] += 1

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

Submission status: Accepted

Solution code:

S = list(map(int, list(input())))

mod = 2019
ctr = [0] * mod
t = 0
for i, v in enumerate(reversed(S)):
    t = (t + int(v) * pow(10, i, mod)) % mod
    ctr[t] += 1

ans = ctr[0]
for v in ctr:
    ans += v * (v - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
S=input()
unko=[0]*2019
tmp=0
num=1
for s in S[::-1]:
  s=int(s)
  tmp=(tmp+s*num)%2019
  num=(num*10)%2019
  unko[tmp]+=1
ans=0
ans+=(unko[0]+1)*unko[0]/2
for i in unko[1:]:
  ans+=i*(i-1)/2
print(int(ans))

Submission status: Accepted

Solution code:
from sys import stdin
#import numpy as np


def merge_sort(lst, low, high):
    if low >= high:
        return
    mid = int((low+high)/2)
    merge_sort(lst, low, mid)
    merge_sort(lst, mid+1, high)
    for i in range(low, mid+1):
        tmp_array[i] = lst[i]
    j = high
    for i in range(mid+1, high+1):
        tmp_array[i] = lst[j]
        j -= 1
    i = low
    j = high
    for k in range(low, high+1):
        if tmp_array[i] <= tmp_array[j]:
            lst[k] = tmp_array[i]
            i += 1
        else:
            lst[k] = tmp_array[j]
            j -= 1


S = stdin.readline().rstrip()
N = len(S)
Sp = S

res_map = [0 for _ in range(N)]

aa_list2 = [1]
for i in range(1,N):
    aa_list2.append((aa_list2[i-1]*10)%2019)

tmp_array = [None for _ in range(N)]
res_map[N-1] = int(S[N-1])
index=1
for i in range(N-2,-1,-1):
    res_map[i] = (int(S[i])*aa_list2[index] + res_map[i+1])%2019
    index+=1

res_map.sort()
temp_num=int(res_map[0])
index=1
tot = 0

for i in range(1,N):
    if temp_num==int(res_map[i]):
        index+=1
        continue
    else:
        if temp_num==0:
            tot += int(index*(index+1)/2)
        elif index>1:
            tot += int(index*(index-1)/2)
        index=1
        temp_num=int(res_map[i])


aa_table = [0 for i in range(2019)]
for i in range(len(res_map)):
    aa_table[res_map[i]]+=1

aa_table[0]+=1

tot = 0
for i in range(2019):
    tot+=int((aa_table[i]-1)*aa_table[i]/2)



#for i in range(2018):
#    num = np.sum(np.array(res_map)==i)
#    if i ==0:
#        num+=1
#    tot += int(num*(num-1)/2)
    

print(tot)

Submission status: Accepted

Solution code:
S = input()
Smod = [0] * 2019
Smod[0] = 1
ans = 0
S_i = 0
prevmod = 0
k = 1
for i in range(len(S)-1, -1, -1):
  S_i = (int(S[i]) * k + prevmod) % 2019
  ans += Smod[S_i]
  Smod[S_i] += 1
  prevmod = S_i
  k = (k * 10) % 2019
print(ans)

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    S = sr()
    N = len(S)
    a = [0]*2019
    a[0] += 1
    t = 0
    r = 1
    for s in reversed(S):
        t += int(s)*r
        t %= 2019
        r *= 10
        r %= 2019
        a[t] += 1
    ans = 0
    for i in range(2019):
        ans += a[i]*(a[i]-1)//2
    print(ans)
resolve()