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:
import sys
input = sys.stdin.readline


L = 2019
S = input().rstrip()


A = {0 : 1}
ans = 0
tmp = 0
c = 1
for s in S[::-1]:
    n = int(s)
    tmp = (tmp + c*n) % L
    c = c * 10 % L
    if tmp in A:
        A[tmp] += 1
    else:
        A[tmp] = 1

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

Submission status: Accepted

Solution code:
S = input()
N = len(str(S))
P = 2019
list_a = [0] * P
list_a[0] += 1
counter = 0
temp = 0
power = 1
for i in range(N):
    temp += pow(10, i, P) * int(S[N - i - 1])
    temp %= P
    counter += list_a[temp]
    list_a[temp] += 1
print(counter)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


s = str(input())
n = len(s)
p = 2019

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    s = input()

    power = 1
    dic = [0] * 2019
    dic[0] = 1
    x = 0
    dic1 = {i:j for i,j in zip('0123456789',range(10))}
    for i in range(len(s)-1,-1,-1):
        x += power * dic1[s[i]]
        x %= 2019
        dic[x] += 1
        power *= 10
        power %= 2019
    
    ans = 0
    for v in dic:
        ans += v*(v - 1)//2
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
S = input()
S = list(map(int,S))
N = len(S)

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

res = [0]
for i in range(N):
    s = S[-i-1]
    res.append((res[-1] + s * rs[i]) % MOD)

cand = Counter(res)
ans = 0
for i in cand.values():
    ans += i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
S=input()
N=len(S)
A=[0]
for i in range(N):
    s=int(S[-1-i])
    A.append((A[-1]+(s*pow(10,i,2019)))%2019)
d={}
for i in range(len(A)):
    if not A[i] in d:
        d[A[i]]=1
    else:
        d[A[i]]+=1
ans=0
for k in d.keys():
    ans+=d[k]*(d[k]-1)//2
print(ans)

Submission status: Accepted

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


S = list(input())
N = len(S)
MOD = 2019
#%%
A = [0]*(N+1)
R = [0]*(2030)

R[0] += 1
base = 1
for i in range(N):
    A[i+1] = A[i] + base*int(S[N-1-i])
    base *= 10
    base %= MOD
    A[i+1] %= MOD
    R[A[i+1]] += 1

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

Submission status: Accepted

Solution code:
S = input()
MOD = 2019
# L = [0 for _ in range(2019)]
L = []
N = len(S)
t = 0
k = 1
for i in range(N - 1, -1, -1):
    t = (t + int(S[i]) * k) % MOD
    L.append(t)
    k *= 10
    k %= MOD
R = [0 for _ in range(2019)]
R[0] = 1
for l in L:
    R[l] += 1
res = 0
for r in R:
    res += (r * (r - 1)) // 2
print(res)

Submission status: Accepted

Solution code:

S = input()
N = len(S)

num = [0] * 2019
num[0] = 1
now, ans = 0, 0
_10 = 1

for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % 2019
    _10 *= 10
    _10 %= 2019
    ans += num[now]
    num[now] += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate,chain
from collections import Counter

MOD = 2019

S = input()

memo = [None]*len(S)
x = 1
for i,c in enumerate(reversed(S)):
    memo[i] = x*int(c)%MOD
    x = (10*x)%MOD

acc = tuple(chain((0,), accumulate(memo, lambda x,y: (x+y)%MOD)))

print(sum(c*(c-1)//2 for c in Counter(acc).values()))

Submission status: Accepted

Solution code:
s = input()
seen = dict()
seen[0] = 1
curr = 0
mult = 1
out = 0
for c in s[::-1]:
    curr += int(c) * mult
    curr %= 2019
    mult *= 10
    mult %= 2019
    if curr not in seen:
        seen[curr] = 0
    out += seen[curr]
    seen[curr] += 1
print(out)

Submission status: Accepted

Solution code:
S = input()
n = len(S)
*S, = map(int, S[::-1])
R = [0]*2019

p = 0
for i, s in enumerate(S):
    q = 10**(i % 224) % 2019
    p += s*q
    p %= 2019
    R[p] += 1

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s=list(input())
s=s[::-1]
for i in range(len(s)):
    s[i]=int(s[i])
data=[0]
x=0
for i in range(len(s)):
    x=pow(10,i,2019)*s[i]+x
    x=x%2019
    data.append(x)
from collections import Counter
data=dict(Counter(data))
ans=0
for key in data.values():
    ans+=(key)*(key-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:
n = input()
l = len(n)
a = [0 for _ in range(2019)]
a[0] = 1
now = 0
ten = [1]
for i in range(l-1):
  ten.append(ten[-1]*10%2019)
ten.reverse()
for i in range(l)[::-1]:
  now += ten[i]*int(n[i])
  now %= 2019
  a[now] += 1
  #print(now)
ans = 0
for d in range(2019):
  ans += a[d] * (a[d]-1) // 2
print(ans)

Submission status: Accepted

Solution code:
s = input()
mod = 2019

temp = [1]
for i in range(len(s) - 1):
    temp.append(temp[-1] * 10 % mod)
temp.reverse()
temp2 = []
for i in range(len(s)):
    temp2.append(int(s[i]) * temp[i])
temp3 = [0]
for i in range(len(s)):
    temp3.append((temp3[-1] + temp2[i]) % mod)
temp4 = {}
for i in temp3:
    temp4.setdefault(i, 0)
    temp4[i] += 1
ans = 0
for i in temp4.values():
    ans += (i * (i - 1) // 2)
print(ans)

Submission status: Accepted

Solution code:

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	S = list(input())
	N = len(S)
	D = defaultdict(int)
	D[0] = 1
	var = 0
	for i in range(N):
		var = var + pow(10, i, 2019) * int(S[N - 1 - i])
		var %= 2019
		D[var] += 1

	ans = 0
	for i in D:
		v = D[i]
		ans += int(v * (v - 1) // 2)

	print(ans)
	


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
s = input()

mods0 = [1]
for i in range(len(s)):
    tmp = mods0[-1] * 10
    mods0.append(tmp % 2019)

mods = [0]
for i in reversed(range(len(s))):
    tmp = mods[-1] + int(s[i]) * mods0[len(s) - i - 1]
    mods.append(tmp % 2019)

from collections import Counter
c = Counter(mods)
ans = 0
for key in c.keys():
    v = c[key]
    ans += v * (v - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
s = input()[::-1]
n = len(s)
ans = 0
data = [0 for _ in range(2019)]
now = 0
data[0] = 1
q = [1]
x = 1
for i in range(n):
    x *= 10
    x %= 2019
    q.append(x)

for i,x in enumerate(s):
    now += int(x)*q[i]
    now %= 2019
    data[now] += 1
    #print(now)

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

print(ans)

Submission status: Accepted

Solution code:
import collections
s=list(input())
n=len(s)
s.reverse()
l=[0]
a=1
x=0
for i in range(n):
  x+=a*int(s[i])
  x%=2019
  a*=10
  a%=2019
  l.append(x)
L=collections.Counter(l)
L2=list(L.values())
ans=0
for i in range(len(L2)):
  ans+=L2[i]*(L2[i]-1)//2
print(ans)

Submission status: Accepted

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

ct = Counter()
ct[0] = 1
ans = 0
tmp = 0
digit = 1
for c in S[::-1]:
    c = int(c)
    tmp = c * digit + tmp
    tmp %= MOD
    ans += ct[tmp]
    ct[tmp] += 1
    digit *= 10
    digit %= MOD
print(ans)

Submission status: Accepted

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

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

T = [-1]*L
mod = 2019
now = 0
for i in range(L):
    s = S[i]
    now += int(s)*pow(10,i,mod)
    T[i] = now%mod
    
Nlist = [0]*2019
Nlist[0] = 1

for i in T:
    Nlist[i] += 1
    
ans = 0
for i in Nlist:
    ans += i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
S = [int(x) for x in input()]
N = len(S)
l = 1
ans = 0
dic = defaultdict(int)
dic[0] = 1
m = 0
for x in S[::-1]:
    m = (x * l + m) % 2019
    ans += dic[m]
    l = l * 10 % 2019
    dic[m] += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    S = input().strip()

    D = {0: 1}
    ss = 0
    r = 1
    for s in S[::-1]:
        ss += int(s) * r
        ss %= 2019
        D[ss] = D.setdefault(ss, 0) + 1
        r *= 10
        r %= 2019

    print(sum(v * (v - 1) // 2 for v in D.values()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter


def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    k = min(k, n - k)
    ans = 1
    for i in range(1, k + 1):
        ans *= n - i + 1
        ans //= i
    return ans


s = input()
n = len(s)
a = [0] * (n + 1)
a[n - 1] = int(s[n - 1])
base = 10
for i in reversed(range(n - 1)):
    a[i] = (a[i + 1] + int(s[i]) * base) % 2019
    base *= 10
    base %= 2019
# print(a)

cnt = Counter(a)
# print(cnt)

ans = 0
for v in cnt.values():
    ans += comb(v, 2)

print(ans)

Submission status: Accepted

Solution code:
def examA():
    S, W = LI()
    if S<=W:
        print("unsafe")
    else:
        print("safe")
    return

def examB():
    A, B, C, D = LI()
    while(True):
        C -= B
        if C<=0:
            print("Yes")
            break
        A -= D
        if A<=0:
            print("No")
            break
    return

def examC():
    N = I()
    S = [SI()for _ in range(N)]
    Set = set(S)
    ans = len(Set)
    print(ans)
    return

def examD():
    S = SI()
    N = len(S)
    D = [0]*(N+1)
    for i in range(N):
        D[i+1] = (D[i]+int(S[N-1-i])*pow(10,i,2019))%2019
    #print(D)
    ans = 0
    C = Counter(D)
    #print(C)
    for c in C.values():
        ans += (c-1)*c//2
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
def main():
    S = list( map( int, list( input())))
    N =len(S)
    A = [0]*2019
    P = 2019
    num = [0] * P
    num[0] = 1
    now, ans = 0, 0
    _10 = 1
    for i in range(N-1, -1, -1):
        now = (now + int(S[i]) * _10) % P
        _10 *= 10
        _10 %= P
        ans += num[now]
        num[now] += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def resolve():
    S = input()
    table=[0]*2019
    table[0]=1
    x = 0
    x_10 =1
    for i in S[::-1]:

        x = (x+ int(i)*x_10)%2019

        table[x]+=1

        x_10*=10
        x_10 %= 2019

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



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import Counter

S = input()
P = 2019

def solve(S, P):
    S = S[::-1]
    T = [0] * len(S)
    T[0] = int(S[0]) % P
    power = 1
    for i in range(1, len(S)):
        power *= 10
        power %= P
        T[i] = T[i - 1] + power * int(S[i])
        T[i] %= P
    counter = Counter(T)
    return sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]


print(solve(S, P))

Submission status: Accepted

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

S = input()[:-1]
cnt = defaultdict(int)
cnt[0] = 1
ans = 0
now = 0

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

print(ans)

Submission status: Accepted

Solution code:
S = input()
# 2019 = 3 * 673
# using mod ?
# 0 mod 2019 の個数を求めたいが…
p=2019
h=0
d=1
total = 0
counts = [0]*p
counts[0]=1
for s in reversed(S):
  m = (int(s)*d) % p
  h = (h+m) % p
  total += counts[h]
  counts[h] += 1
  d = (d*10) % p
print(total)

Submission status: Accepted

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

dp = [0] * (N+1)
base = 2019
for i, s in enumerate(S, 1):
    dp[i] = (dp[i-1]*10 + int(s)) % 2019

digit = 1
for i in range(N):
    j = N - i
    dp[j] *= digit
    dp[j] %= base
    digit *= 10
    digit %= base

ans = 0
d = {}
for r in dp:
    if r in d:
        ans += d[r]
        d[r] += 1
    else:
        d[r] = 1

print(ans)

Submission status: Accepted

Solution code:
S=input()
DP=[0]*len(S)

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

from collections import Counter
C=Counter(DP)

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

print(ANS)

Submission status: Accepted

Solution code:
s = input()
mod = 2019
remains = [0]*mod

ans = 0
now = 0
remains[0] = 1
for i,val in enumerate(s[::-1]):
    now += int(val) * pow(10,i,mod )
    now %= mod
    ans += remains[now]
    remains[now] += 1

print(ans)

Submission status: Accepted

Solution code:
s=list(input())
mod=2019
A=[0]*2019
a=0
b=1
for i in range(len(s)):
  a=(a+int(s[-1-i])*b)%mod
  A[a]+=1
  b=b*10%mod
ans=A[0]*(A[0]+1)//2
for i in range(1,2019):
  if A[i]!=0:
    ans=ans+(A[i]-1)*A[i]//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
S = [int(c) for c in input()]
N = len(S)
ls = [0]*N
m = 1
for i in range(N):
  ls[N-1-i] = S[N-1-i]*m%2019
  m *= 10
  m %= 2019
T = [0]*N
T[0] = ls[0]
for i in range(1,N):
  T[i] = (T[i-1]+ls[i])%2019
c = Counter(T)
ans = c[0]+sum(v*(v-1)//2 for v in c.values())
print(ans)

Submission status: Accepted

Solution code:
import sys
range = xrange
input = raw_input

mod = 2019

S = input()
X = [0]
power = 1
for c in reversed(S):
    X.append((int(c) * power + X[-1]) % mod)
    power = power * 10 % mod

counter = [0]*mod
for x in X:
    counter[x] += 1

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

Submission status: Accepted

Solution code:
s = input()
a = [0]
l = len(s)
for i in s:
    i = int(i)
    a.append((a[-1] + i * pow(10, l, 2019)) % 2019)
    l -= 1

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

Submission status: Accepted

Solution code:
from collections import Counter
MOD = 2019
s = input()[::-1]
n = len(s)
l = [0] * (n + 1)
t = 1
for i in range(n):
    l[i + 1] = ((ord(s[i]) - ord('0')) * t + l[i]) % MOD
    t = t * 10 % MOD
c = Counter(l)
ans = 0
for v in c.values():
    ans += (v - 1) * v // 2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as dict

s = input()
a = []
for c in s:
    a.append(int(c))

cnt = dict(int)
d = 1
a.reverse()
y = 0
cnt[y] += 1
ans = 0
for x in a:
    y += d*x
    y %= 2019
    ans += cnt[y]
    cnt[y] += 1
    d *= 10
    d %= 2019

print(ans)

Submission status: Accepted

Solution code:
S = input()

S = S[::-1]

T = [0]
t = 0
a = 1
for i in range(len(S)):
    t += int(S[i])*a
    t %= 2019
    a *= 10
    a %= 2019
    T.append(t)
from collections import Counter
c = Counter(T)
num = 0
for key in c:
    num +=(c[key]*(c[key]-1))//2

print(num)

Submission status: Accepted

Solution code:
s=input()[::-1]
n=len(s)
b=[0]
m=0
d=1
for i in range(n):
  m+=int(s[i])*d
  m%=2019
  d*=10
  d%=2019
  b.append(m)
from collections import Counter
c=Counter(b)
ans=0
for i in range(2020):ans+=c[i]*(c[i]-1)//2
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

S = input()
N = len(S)

P = 2019

if P not in [2,5]:

    dic = {}
    dic[0] = 1
    now = 0
    ans = 0

    loop = 0
    for i in range(N-1,-1,-1):
        now += int(S[i]) * pow(10,loop,P)
        now %= P
        if now in dic:
            ans += dic[now]
            dic[now] += 1
        else:
            dic[now] = 1
        loop += 1

    print (ans)

elif P == 2:

    ans = 0
    for i in range(N):

        if int(S[i]) % 2 == 0:
            ans += i+1

    print (ans)

else:

    ans = 0

    for i in range(N):

        if int(S[i]) % 5 == 0:
            ans += i+1

    print (ans)

Submission status: Accepted

Solution code:

s = input()
n = len(s)

A = [1]
mod = 2019
for i in range(n-1):
    A.append((A[-1]*10)%mod)

B = [int(s[-1])]
for i in range(1, n):
    B.append((B[-1] + A[i] * int(s[n-i-1])) % mod)

# print(B)

ans = 0
C = [0] * 2019
C[0] += 1
for i in range(n):
    C[B[i]] += 1

for i in range(len(C)):
    ans += (C[i]-1)*C[i]//2

print(ans)

Submission status: Accepted

Solution code:
p=2019
s=input()
l=len(s)
amari=[0]*l
count=[0]*p

ruijo=1

for i in range(l):
    suji=int(s[l-i-1])
    amari[i]=(suji*ruijo)%p
    ruijo*=10
    ruijo%=p

gen=0
count[0]+=1
for i in range(l):
    gen+=amari[i]
    gen%=p
    count[gen]+=1
    #print(gen)

ans=0

for c in count:
    if(c>1):
        ans+=c*(c-1)//2

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

s = list(map(int, list(ns())))
n = len(s)
l = [0]*(n+1)
t = 1
for i in range(n-1, -1, -1):
    l[i] = (l[i+1] + s[i]*t) % 2019
    t = t * 10 % 2019
d = Counter(l)
print(sum(y*(y-1)//2 for y in d.values()))

Submission status: Accepted

Solution code:
from collections import Counter
s=input()[::-1]
l=[0]*(len(s)+1)
kake=1
for i in range(1,len(s)+1):
    l[i]=l[i-1]+kake*int(s[i-1])
    l[i]%=2019
    kake*=10
    kake%=2019
S=Counter(l);ans=0
for i in S.values():
  ans+=(i*(i-1))//2
print(ans)

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:
s = input()
n, p = len(s), 2019

ans = 0

d = {i:0 for i in range(p)}
d[0] = 1

ap = 1
if p not in [2, 5]:
    pre = 0
    for si in s[::-1]:
        si = int(si)
        a = (si * ap + pre) % p
        ans += d[a]
        d[a] += 1
        pre = a
        ap = (ap * 10) % p
else:
    for i, si in enumerate(s):
        if int(si) % p == 0:
            ans += i+1
print(ans)

Submission status: Accepted

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

m = 2019
cnt = [0]*(m+1)

ans = 0
p = 1
cur = 0
for i in reversed(range(n)):
    cur += p*int(s[i])
    cur %= m
    p *= 10
    p %= m

    if cur == 0:
        ans += 1
    ans += cnt[cur]
    cnt[cur] += 1

print(ans)

Submission status: Accepted

Solution code:
def input_int():
    return int(input())

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

S = input()
N = len(S)
cnt = [0] * 2019
cnt[0] += 1
ans = 0

p = 1
now = 0

for i in reversed(range(N)):
    now = (now + int(S[i]) * p) % 2019
    p = p * 10 % 2019
    ans += cnt[now]
    cnt[now] += 1

print(ans)

Submission status: Accepted

Solution code:

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

mod = 2019
ss = [0]
tmp = 0
for i, s in enumerate(S[::-1]):
    tmp += s * pow(10, i, mod)
    tmp %= mod
    ss.append(tmp)

cnts = [0] * 2019
ans = 0
for s in ss:
    ans += cnts[s]
    cnts[s] += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
s = input()
n = len(s)
a = [0]*n
p=2019
r = defaultdict(int)
a = int(s)
r[a%p]+=1
for i in range(n):
    a = (a%p-int(s[i])%p*pow(10,(n-1-i),p))%p
    r[a]+=1
#print(r)
ans = 0
cnt=1
for i in r.values():
    ans+=i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

S = list(map(int, input()))
mod = [0] * len(S)
cur = 0
factor = 1
for i, n in list(enumerate(S))[::-1]:
    cur = (cur + n * factor) % 2019
    factor = factor * 10 % 2019
    mod[i] = cur
ans = 0
cnt = defaultdict(int)
for i in range(len(S)):
    ans += cnt[mod[i]]
    cnt[mod[i]] += 1
ans += cnt[0]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

s = input()

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

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 2019

def solve():
    a = list(map(int, input()))
    n = len(a)
    for i in range(n):
        a[i] *= pow(10,n-i-1,mod)
        a[i] %= mod
    s = [0]+list(accumulate(a))
    d = [0]*mod
    ans = 0
    for i in s:
        j = i%mod
        ans += d[j]
        d[j] += 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
S=input()[::-1]
N=len(S)
X=[0 for i in range(N+1)]
tmp=1
for i in range(N):
    X[i+1]=X[i]+(tmp*int(S[i]))
    X[i+1]%=2019
    tmp=tmp*10
    tmp%=2019
D=dict()
for i in range(N+1):
    if X[i] in D:
        D[X[i]]+=1
    else:
        D[X[i]]=1
ans=0
for k in D:
    i=D[k]
    ans+=(i*(i-1))//2
print(ans)

Submission status: Accepted

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

memo = [0]
d = 0
mod = 2019

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

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

Submission status: Accepted

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

P = 2019
S=input().strip()
N = len(S)
if P in {2, 5}:
    r=0
    for i in range(N):
        if not int(S[i])%P:
            r+=i+1
    print(r)
else:
    S = S[::-1]
    r=0
    from collections import defaultdict
    d=defaultdict(int)
    d[0] += 1
    R=0
    X=1
    for i in range(N):
        r += int(S[i])*X
        R += d[r%P]
        X = (X*10)%P
        d[r%P]+=1
    print(R)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read


s = input()

MOD = 2019
d = [0]*MOD
d[0] = 1
r = 0
t = 1
for i in reversed(s):
    r += int(i)*t
    r %= MOD
    t *= 10
    t %= MOD
    d[r] += 1
    
print(sum(i*(i-1)//2 for i in d))

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1001001001;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
    string S;
    cin >> S;
    ll N = S.size();
    vector<int> CNT(2019, 0);
    CNT[0] = 1;
    ll base = pow(10, N);
    ll num = 0;

    rep(i, N) {
        base /= 10;
        num = num * 10 + (S[i] - '0');
        ++CNT[(num*base)%2019];
    }
    int ans = 0;
    for(auto cnt : CNT) {
        ans += (cnt * (cnt - 1)) / 2;
    }
    cout << ans << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
from collections import deque
que = deque()
S = input()
s = ["0"*2000000]
count=0

for i in range(len(S)):
  s[i]=int(S[i])
for j in range(len(S)):
  que.append(s[i])

while que:
  seq = que.popleft()
  if int(join(seq))%2019==0:
    count+=1
else:
  for i in range(seq[-1], m + 1):
      seq_next = seq + [i]
      que.append(seq_next)

print(count)

Submission status: Runtime Error

Solution code:
def main():
    s = input()
    lens = len(s)

    d1 = defaultdict(int)
    ss = int(s[-4:]) % 2019
    k = 5
    while k <= lens:
        d1[ss] += 1
        ss += (int(s[-k]) * (10 ** (k - 1))) % 2019
        ss = ss % 2019
        k += 1
    d1[ss] += 1
    r = d1[0]
    for v in d1.values():
        r += v * (v - 1) // 2
    print(r)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from math import pow

def main():
    s = input()
    s = s[::-1]
    s_len = len(s)
    mod = 2019
    d = [0] * mod
    d[0] = 1
    rev_num = 0
    # 2以上なら共通するmodがあったということになる
    for i in range(s_len):
        rev_num += int(s[i]) * int(pow(10, i)%mod)
        rev_num %= mod
        d[rev_num] += 1
    # 2以上同じmodがあったらそこから2つ選ぶ選び方
    # それを全てのmodで
    print(sum(i*(i-1)//2 for i in d))
 
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    s = input()
    s_len = len(s)
    s_rev = reversed(s)
    mod = 2019
    d = [0] * mod
    d[0] = 1
    rev_num = 0
    # 2以上なら共通するmodがあったということになる
    for i in range(l_len):
        rev_num += int(s_rev(i)) * (10**i%mod)
        rev_num %= mod
        d[rev_num] += 1
    # 2以上同じmodがあったらそこから2つ選ぶ選び方
    # それを全てのmodで
    print(sum(i*(i-1)//2 for i in d))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
S = input()
P = [0 for _ in range(len(S)+1)]
mod = 2019
d = 1
for i in range(len(S), 0, -1):
    P[i-1] = int(S[i-1])*d + P[i]
    P[i-1] = P[i-1] % mod
    d *= 10

for p in P:
    A[p] += 1

ans = 0
for a in A:
    ans += a*(a-1)//2
print(ans)

Submission status: Runtime Error

Solution code:
S = input()
P = [0 for _ in range(len(S)+1)]
mod = 2019
d = 1
for i in range(len(S), 0, -1):
    P[i-1] = int(S[i-1])*d + P[i]
    P[i-1] = P[i-1] % mod
    d *= 10

for p in P:
    A[p] += 1

ans = sum(list(map(lambda n: n*(n-1)//2, A)))
print(ans)

Submission status: Runtime Error

Solution code:
S = input()

S= abs(int(S))
#print (len(S))
S = str(S)
count =0
wari = 2019
number = 0
for i in range(len(S)+1):
  for j in range(len(S)+1):
    if i<j:
      #print ("i="+str(i))
      #print ("i ="+S[i])
      #print ("j="+str(j))
      #print ("j = "+S[j+1])
      #number = ''.join(S[i:j])
      #print (number)
      number = int(float(S[i:j]))
      #print (number)
      if number%wari==0:
        #print (number)
        count+=1
        #print ("count="+str(count))
      
print (count)

Submission status: Runtime Error

Solution code:
S = input()

count =0
wari = 2019
number = 0
for i in range(len(S)+1):
  for j in range(len(S)+1):
    if i<j:
      #print (i)
      #print (j)
      #number = ''.join(S[i:j])
      #print (number)
      number = int(float(S[i:j]))
      #print (number)
      if number%wari==0:
        #number = "".join(S[i:j])
        #print (number)
        count+=1
        #print ("count="+str(count))
      
print (count)

Submission status: Runtime Error

Solution code:
S = input()

count =0
wari = 2019
number = 0
for i in range(len(S)+1):
  for j in range(len(S)+1):
    if 4<=j-i:
      #print (i)
      #print (j)
      #number = ''.join(S[i:j])
      #print (number)
      number = int(float(S[i:j]))
      #print (number)
      if number%wari==0:
        #number = "".join(S[i:j])
        #print (number)
        count+=1
        #print ("count="+str(count))
      
print (count)

Submission status: Runtime Error

Solution code:
import math
S = list(str(input()))
ans = [0]*2019
def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)
se = ''
s = [0] * 2019
L = len(S)
for i in range(len(S)):
  se  = S[L - i - 1] + se
  s[i] = int(se)%2019
  ans[s[i]] += 1
k = 0
for i in range(2019):
  if ans[i] >1:
    k += permutations_count(ans[i] , 2)
    print(i)

Submission status: Runtime Error

Solution code:
#D

from itertools import combinations
from sys import stdin

def main():
    readline = stdin.readline
    S=readline()
    len_S=len(S)
 
    if len_S <4:
        print(0)
 
    else:
        comb=list(combinations(range(len_S+1),2))
        count=0
        for i in comb:
            i_0=i[0]
            i_1=i[1]
            if int(S[i_0:i_1])%2019==0:
                count+=1
        print(count)
main()

Submission status: Runtime Error

Solution code:
#D
from numba import njit
from itertools import combinations
from sys import stdin
@njit
def main():
    readline = stdin.readline
    S=input()
    len_S=len(S)

    if len_S <4:
        print(0)

    else:
        comb=list(combinations(range(len_S+1),2))
        count=0
        for i in comb:
            i_0=i[0]
            i_1=i[1]
            if int(S[i_0:i_1])%2019==0:
                count+=1
        print(count)
main()

Submission status: Runtime Error

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

counter = [0] * 2019
counter[0] = 1
T = 0
R = 1
for i in range(N):
    T = (T + R * int(S[n - i - 1])) % 2019
    R = 10 * R % 2019
    counter[T] += 1

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

print(ans)