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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
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

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

l = [0]*2019

tmp = 0
z = 1
for i, s in enumerate(S):
	tmp += s*z
	z = z*10%2019
	l[tmp%2019] += 1
ans = 0
for v in l:
	ans += v*(v-1)//2
print(ans+l[0])

Submission status: Accepted

Solution code:
S = input()

# do shakutori
#以下が an mod p を求めるソースコードです.
def power_func(a, n, p):
    res = 1 #これは答え
    while n > 0:
        if n & 1:
            res = res * a % p
        a = a * a % p #1が立っているかどうかに関わらず次のaの累乗を用意しておく
        n = n >> 1
    return res

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

import collections
dct = dict(collections.Counter(Q))
# print(dct)
ans = 0
for val in dct.values():
    ans += val * (val - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
S = input()
N = len(S)
mod = 2019
X = [0 for _ in range(N)]
base = 1
for i in range(N, 0, -1):
    X[i-1] = ((int(S[i-1]) * base) % mod)
    base *= 10
    base %= mod
for i in range(1, N):
    X[i] += X[i-1]
    X[i] %= mod
D = {i: 0 for i in range(mod)}
for i in range(N):
    D[X[i]] += 1
XX = 0
for i in D:
    if i != 0:
        XX += (D[i] * (D[i] - 1)) // 2
    else:
        XX += (D[0] * (D[0] + 1)) // 2
print(XX)

Submission status: Accepted

Solution code:
S = [int(i) for i in list(input())]
S.reverse()
l = len(S)
T = [0]
for i in range(l):
    T.append((T[-1]+S[i]*(pow(10, i, 2019))) % 2019)
C = {}
for t in T:
    try:
        C[t] += 1
    except:
        C[t] = 1
ans = 0
for c in C.values():
    ans += c*(c-1)//2
print(ans)

Submission status: Accepted

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

ans = 0

if P in (2, 5):
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i + 1
else:
    count = [0] * P
    count[0] = 1
    u = 0
    for i, s in enumerate(reversed(S)):
        u = (int(s) * pow(10, i, P) + u) % P
        ans += count[u]
        count[u] += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    S = [int(s) for s in list(input().strip())][::-1]
    N,P = len(S), 2019
    
    num = 0
    ans = 0
    
    if P == 2 or P == 5:
    	for i in range(N):
    		if S[i] % P == 0:
    			ans += N-i
    	print(ans)
    	return

    L = [0] * P
    L[0] = 1
    t = 0
    s = 1
	
    for z in S:
    	t = (z * s + t)%P	
    	L[t]+=1
    	s = s * 10 % P
	
    for l in L:
    	ans += l * (l - 1) // 2
    
    print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
S = list(map(int, list(input())[: -1]))
N = len(S)
P = 2019
rcs = [0] * (N + 1)
for i in range(N, 0, -1): rcs[i - 1] = (rcs[i] + S[i - 1] * pow(10, N - i, P)) % P
#print(rcs)
d = dd(list)
for i in range(N + 1):d[rcs[i]].append(i)
res = 0
if P == 2 or (P == 5):
  for i in range(N - 1, -1, -1):
    res += (S[i] % P == 0) * (i + 1)
  print(res)
  exit(0)
table = [0] * P
for i in range(N, -1, -1):
  x = rcs[i]
  res += table[x]
  table[x] += 1
print(res)

Submission status: Accepted

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

R=[0]
r=0
k=1
for c in S:
    r = (r+k*c) % 2019
    k = k*10 % 2019
    R.append(r)
    
N = [0]*2019
ans = 0
for r in R:
    ans += N[r]
    N[r] += 1
print(ans)

Submission status: Accepted

Solution code:
s = list(map(int, input()))
n = len(s)
p = 2019
ans = 0

s.reverse()
cum = [0] * (n+1)
for i in range(n):
    cum[i+1] = (cum[i] + s[i] * pow(10, i, p)) % p
t = [0] * p
for x in cum: t[x] += 1

for x in t:
    ans += x * (x-1) // 2
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    s = input()
    l = len(s)

    from collections import Counter
    counter = Counter()
    prev = 0
    counter[0] += 1

    for i in range(l):
        num = int(s[l - i - 1])
        m = (num * pow(10, i, 2019) + prev) % 2019
        counter[m] += 1
        prev = m

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
S=list(reversed(input()))
lst=[0 for i in range(len(S))]
num=0
z=1
for i in range(len(S)):
    num+=int(S[i])*z
    num%=2019
    z*=10
    z%=2019
    lst[i]=num
lst=Counter(lst)
lst[0]+=1
count=0
for l in lst:
    n=lst[l]
    count+=n*(n-1)//2
print(count)

Submission status: Accepted

Solution code:
from collections import Counter
s = input()
leng = len(s)
cnt = 0
mod = 2019

SUM = [0] * (leng + 1)
for i in range(leng):
    temp = int(s[-(i + 1)]) * pow(10, i, mod)
    SUM[i + 1] = (SUM[i] + temp) % mod

#print(SUM)
ans = Counter(SUM)
for i in ans.values():
    if i >= 2:
        cnt += i * (i - 1) // 2
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter
# sys.setrecursionlimit(100000)
# input = sys.stdin.buffer.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(S):
    # 2019 = 3 * 673
    L = 2019
    rl = [0] * L
    rl[0] = 1
    ans = 0
    for c in S:
        n = int(c)
        nrl = [0] * L
        nrl[0] = 1
        for r in range(L):
            m = rl[r]
            r = (r * 10 + n) % 2019
            if r == 0:
                ans += m
            nrl[r] += m
        rl = nrl
        # print(rl)

    return ans


def main():
    S = read_str()
    print(slv(S))

    # import random
    # S = ''.join(map(str, random.choices(range(1, 10), k=2*10**5)))
    # print(slv(S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 2019
eps = 10**-9


def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    S = input().rstrip('\n')
    S = S[::-1]
    N = len(S)
    CS = [0] * (N+1)
    for i in range(N):
        CS[i+1] = (CS[i] + (int(S[i]) * pow(10, i, mod))%mod)%mod
    dic = defaultdict(int)
    for a in CS:
        dic[a] += 1
    ans = 0
    for v in dic:
        a = dic[v]
        ans += a * (a-1) // 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(n):
    p+=x*int(s[i])
    p%=2019
    a[p]+=1
    x=(x*10)%2019
ans=0
for i in range(2019):
    ans+=a[i]*(a[i]-1)//2
print(ans)

Submission status: Accepted

Solution code:
s = list(map(int, input()))
#print(s)
n = len(s)

l_sum = [0]
for i in range(n):
    x = (l_sum[-1] + int(s[n-i-1]) * (pow(10, i, 2019))) % 2019
    l_sum.append(x)

#print(l_sum)
l_sum.sort()
ans = 0
tmp = 0
cnt = 1
for i in range(1, len(l_sum)):
    if l_sum[i] == tmp:
        cnt += 1
    else:
        ans += cnt * (cnt - 1) // 2
        cnt = 1
        tmp = l_sum[i]

ans += cnt * (cnt - 1) // 2
print(ans)

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=2019
    S=list(input())
    S=S[::-1]
    N=len(S)
    
    from collections import defaultdict
    dd = defaultdict(int)
    #2019で割ったあまりの個数
    p=[1]*N
    for i in range(N-1):
        p[i+1]=(p[i]*10)%mod
    
    now=0
    dd[0]=1
    for i in range(N):
        now=now+int(S[i])*p[i]
        now%=mod
        dd[now]+=1
        
    ans=0
    for k,v in dd.items():
        ans+=(v*(v-1))//2
    print(ans)
    

main()

Submission status: Accepted

Solution code:
s = input()
p=2019;n=len(s)
digit_rm = [0 for _ in range(n)]
for i in range(n):
	digit_rm[i] = (int(s[n-1-i]) * pow(10, i, p) ) % p

remain = [0 for _ in range(n)]
for i in range(n):
	if i == 0:
		remain[i] = digit_rm[i]
	else:
		remain[i] = (remain[i-1] + digit_rm[i]) % p
pcnt = [0 for _ in range(p)]
for i in remain:
	pcnt[i] += 1
ans = pcnt[0]
for num in pcnt:
	if num != 0:
		ans += num * (num - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 2019
mans = inf ;ans = 0 ;count = 0 ;pro = 1

S = list(map(int,input()))
n = len(S)
now10 = 1
for i in range(n-1,-1,-1):
  S[i] = S[i] * now10 % mod
  now10 = now10 * 10 % mod
A = [0]* (n+1)
for i in range(n):
  A[i+1] = (A[i] + S[i]) % mod
C = collections.Counter(A)
for k,e in C.items():
  ans += (e-1)*e//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

S = input()
MOD = 2019
redisuals = [0]


for i in range(len(S)):
    s = int(S[-i - 1])
    redisuals.append((redisuals[-1] + s * pow(10, i, MOD)) % MOD)

c = Counter(redisuals)

ans = 0
for k, v in c.items():
    ans += v * (v - 1)

ans //= 2
print(ans)

Submission status: Accepted

Solution code:
#昔のコピペ
s = input()
n = len(s)
p = 2019

c = 0
mm = {}
r = 0
mten = 1
for i in range(n - 1, -1, -1):
    ch = int(s[i])
    r = (r + ch * mten) % p
    mten = (mten * 10) % p
    if r in mm:
        c += mm[r]
        mm[r] += 1
    else:
        mm[r] = 1
    if r == 0:
        c += 1

print(c)

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    S = list(map(int,list(input())))
    N = len(S)
    M = [0] * (N + 1)
    ten = 1
    for i in range(N-1,-1,-1):
        M[i] = (S[i] * ten + M[i+1]) % 2019
        ten *= 10
        ten %= 2019

    d = defaultdict(int)

    for m in M:
        d[m] += 1
    ans = 0
    for i, j in d.items():
        ans += j * (j - 1) // 2
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = list(input())
L = len(S)

c = 0
t = 0
md = [0] * 2019
md[0] += 1
for i in range(L - 1, -1, -1):
    t += int(S[i]) * pow(10, c, 2019)
    c += 1
    md[t % 2019] += 1

ans = 0
for i in range(2019):
    m = md[i]

    if m == 0:
        continue

    ans += m * (m - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

S = input()
S = S[::-1]
U = [0] * len(S)

a = 1
for k,v in enumerate(S):
    U[k] = U[k-1] + a * int(v)
    U[k] %= 2019
    a *= 10
    a %= 2019

U.append(0)

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

print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

S = list(inputS())
N = len(S)

r = []
for i in range(N)[::-1]:
  n = int(S[i])
  if r == []:
    r.append(n)
  else:
    r.append((r[-1]+n*pow(10,N-i-1,2019))%2019)

import collections

c = collections.Counter(r)

res = 0
for i in c.items():
  res += i[1]*(i[1]-1)/2
  if i[0]==0:
    res += i[1]

print(int(res))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(S: str):
    N = len(S)
    U = [0]*(N+1)
    a = 0
    beki = 1
    for i in range(N-1, -1, -1):
        a += beki*(ord(S[i])-ord("0"))
        a %= 2019
        beki = (beki*10) % 2019
        U[i] = a
    table = [0]*2019

    tot = 0
    for i in range(N-1, -1, -1):
        tot += table[U[i]]
        table[U[i]] += 1
    tot += table[0]
    print(tot)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = str(next(tokens))  # type: str
    solve(S)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            index=0
            a,b,c=(list(ls[i])+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True


## Segment Tree ##

## Initializer Template ##
# Range Sum:        sg=SegTree(n)
# Range Minimum:    sg=SegTree(n,inf,min,inf)

class SegTree:

    def __init__(self,n,init_ls=None,init_val=0,function=lambda a,b:a+b,ide=0):
        self.n=n
        self.ide_ele=ide_ele=ide
        self.num=num=2**(n-1).bit_length()
        self.seg=seg=[self.ide_ele]*2*self.num
        self.lazy=lazy=[self.ide_ele]*2*self.num
        self.segfun=segfun=function
        #set_val
        if init_ls==None:
            for i in range(n):
                self.seg[i+self.num-1]=init_val
        else:
            for i in range(n):
                self.seg[i+self.num-1]=init_ls[i]
        #build
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.segfun(self.seg[2*i+1],self.seg[2*i+2])
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfun(self.seg[k*2+1],self.seg[k*2+2])
        
    def evaluate(k,l,r): #遅延評価処理
        if lazy[k]!=0:
            node[k]+=lazy[k]
            if(r-l>1):
                lazy[2*k+1]+=lazy[k]//2
                lazy[2*k+2]+=lazy[k]//2

        lazy[k]=0
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res
    
    def find_min_index(self,p,q,m):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p >>= 1
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res


    def __str__(self):
        # 生配列を表示
        rt=self.seg[self.num-1:self.num-1+self.n]
        return str(rt)

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)

def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    
    # calc
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev


ans=0

s=input()
n=len(s)

a=[0]
t=0
m=2019
d=0
for i in s[::-1]:
    t=t+int(i)*pow(10,d,m)
    t%=m
    d+=1
    a.append(t%m)
#    show(t)



c=Counter(a)

#for i in range(n):
for i,j in c.items():
    ans+=j*(j-1)//2
#    show(i,j)

print(ans)

Submission status: Accepted

Solution code:
import math

M = 2019

S = input().strip()

data = []
l = len(S)
d = 1
for i in range(l):
	data.append((d * int(S[l - i - 1]) % M))
	d = (d * 10 % M)

table = [0] * M
table[0] = 1

count = 0
n = 0
for rem in data:
	n = (n + rem) % M
	count += table[n]
	table[n] += 1

print(count)

Submission status: Accepted

Solution code:
def main():
    S = input()
    p = 2019
    d = {i:0 for i in range(p)}
    d[0] = 1
    r = 0
    x = 0
    for i in range(len(S)):
        x += int(S[len(S)-1-i]) * pow(10, i, p)
        x %= p
        r += d[x]
        d[x] += 1
    return r
print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
s = list(input())
n = len(s)
p = 2019

ans = 0
d = [0] * (n + 1)
ten = 1
for i in range(n - 1, -1, -1):
    a = int(s[i]) * ten % p
    ten *= 10
    ten %= p
    d[i - 1] = (d[i] + a) % p
cnt = [0] * p
for i in range(n, -1, -1):
    ans += cnt[d[i]]
    cnt[d[i]] += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

NN = 202020
MOD = 10**9+7
# MOD = 998244353
INF = float("inf")

s = input()
d = defaultdict(int)
d[0] = 1
su = 0
for i in range(len(s)):
    t = pow(10, i, 2019)
    su = (su + int(s[-i-1])*t)%2019
    d[su] += 1

# print(d)
ans = 0
for k,v in d.items():
    ans += v*(v-1)//2

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

S = input()

x = [0]
dec = 1
for s in S[::-1] :
  x.append((x[-1] + dec * int(s)) % 2019)
  dec *= 10
  dec %= 2019

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline
import collections


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


    N = len(S)
    P = 2019
    M = [0] * N
    for i, s in enumerate(S[::-1]):
        M[i] = (int(s) * pow(10, i, P)) % P

    MA = []
    MA.append(M[0])
    c = collections.Counter()
    ans = 0
    c[0] += 1
    ans += c[MA[0]]
    c[M[0]] += 1
    for i in range(1, N):
        MA.append((MA[i - 1] + M[i]) % P)
        ans += c[MA[i]]
        c[MA[i]] += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline


s = [int(item) for item in list(input().rstrip())]
s.reverse()

mod2019 = []
base = 1
for item in s:
    mod2019.append(base * item % 2019)
    base = base * 10 % 2019

cumsum = [0]
for item in mod2019:
    cumsum.append((cumsum[-1] + item) % 2019)

count = [0] * 2020
for item in cumsum:
    count[item] += 1
ans = 0
for cnt in count:
    ans += cnt * (cnt - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
S = input()
S_rev = S[::-1]
# amari = [0]
a = 0
from collections import defaultdict
d = defaultdict(int)
d[0]+=1
for i,s_r in enumerate(S_rev):
    x = pow(10,i,2019)
    # print(x)
    a = (a+int(s_r)*x)%2019
    # amari.append(a)
    d[a] += 1


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

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    S = list(input().strip("\n"))
    N = len(S)
    mod = 2019
    D = [0] * (N + 1)
    D[N] = 0
    D[N-1] = int(S[N-1])
    modType = dict()
    modType[D[N-1]] = 1
    modType[0] = 1
    ans = 0
    for i in reversed(range(N - 1)):
        D[i] = (D[i + 1] + int(S[i]) * pow(10, N - i - 1, mod)) % mod
        if D[i] in modType:          
            ans += modType[D[i]]   
            modType[D[i]] += 1
        else:
            modType[D[i]] = 1
    print(ans)
    #print(D)
    
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

data = [0]*2019
pre = 0
for i in range(len(S)):
    x = pow(10,i,2019)
    x *= S[-i-1]
    x %= 2019
    data[(pre+x)%2019] += 1
    pre += x

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

print(ans)

Submission status: Accepted

Solution code:
#N,P = map(int,input().split())
s = list(input())
N = len(s)
P = 2019
S = [0]*N

for i in range(N):
    S[i] = int(s[i])

count = 0

if P != 2 and P != 5:
    now = 0
    remainder = []
    for i in range(1,N+1):
        now += S[N-i] * (pow(10,(i-1),P) )
        remainder.append(now % P)

    result={}
    for i in range (0,len(remainder)):
        item = remainder[i]
        if item in result:
            result[item] = result[item]+1
        else:
            result[item] = 1

    for k in result.keys():
        if k == 0:
            if result[0] >= 2:
                count += result[0] + result[0]*(result[0]-1)//2
            else:
                count += result[0]
        else:
            count += result[k]*(result[k]-1)//2

print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a = input()
n = len(a)
s = [[0, 0] for i in range(n+1)]
MOD1 = 3
MOD2 = 673
u = [[0 for i in range(MOD2)] for j in range(MOD1)]
ret = 0
c1 = pow(10, MOD1-2, MOD1)
c2 = pow(10, MOD2-2, MOD2)
for i in range(n):
    s[i+1] = [(s[i][0]*10+int(a[i]))%MOD1, (s[i][1]*10+int(a[i]))%MOD2]
    x, y = s[i][0]*pow(c1, i, MOD1)%MOD1, s[i][1]*pow(c2, i, MOD2)%MOD2
    u[x][y] += 1
    x, y = s[i+1][0]*pow(c1, i+1, MOD1)%MOD1, s[i+1][1]*pow(c2, i+1, MOD2)%MOD2
    ret += u[x][y]
print(ret)

Submission status: Accepted

Solution code:
S=list(input())
N=len(S)
ls=[0 for _ in range(N)]
mod=[0 for _ in range(2019)]
d=10
ls[0]=int(S[-1])
mod[ls[0]]+=1
for i in range(1,N):
  ls[i]=(ls[i-1]+d*int(S[-1-i]))%2019
  d=(d*10)%2019
  mod[ls[i]]+=1
#print(ls)
#print(mod)  
ans=mod[0]
for i in range(N):
  m=ls[i]
  mod[ls[i]]-=1
  ans+=mod[ls[i]]
print(ans)

Submission status: Accepted

Solution code:
def equalfind(A):#配列中の等しい要素の組をカウント　オーダーはO(NlogN)
    A.sort()
    s=1
    count=0
    if len(A)==1:
        return count
    else:
        for i in range(0,len(A)-1):
            if A[i]==A[i+1]:
                s+=1
            else:
                count+=s*(s-1)//2
                s=1
        return count+s*(s-1)//2

S=input()
N=len(S)
mod=2019
data=[(int(S[-i-1])*pow(10,i,mod)) for i in range(0,N)]

for i in range(1,N):
    data[i]+=data[i-1]
    data[i]%=mod

data=[0]+data
data.sort()
print(equalfind(data))