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())
S.reverse()
N=len(S)
R=[0]*N
R10=[0]*N
m=2019
K=0

R10[0]=1
R[0]=int(S[0])%m
for i in range(1,N):
    R10[i]=(R10[i-1]*10)%m
    R[i]=(R[i-1]+int(S[i])*R10[i])%m
d={}
for i in range(2019):
    d[i]=0

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

Submission status: Accepted

Solution code:
S=list(map(int,input()[::-1]))
lenS=len(S)
cnt = [0]*2019
tmp = 0
for n,i in enumerate(S):
    tmp += i*pow(10,n,2019)
    cnt[tmp%2019]+=1
ans = cnt[0]*(cnt[0]+1)//2
for i in cnt[1:]:
    ans += i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
import collections
MOD = 2019

def mod(n):         
  return n % MOD

def modpow(a, n):   #mod(a**n)を高速で求める
    res = 1  
    digit = len(str(bin(n))) - 2
    for i in range(digit):
      if (n >> i) & 1:
        res *= mod(a)
        res = mod(res)
      a = mod(a**2)
    return mod(res)

s = input()
lst = []
n = 0
for i in range(len(s)):
  n += mod(int(s[len(s)-i-1])*modpow(10, i))
  lst.append(mod(n))
lst.append(0)
lst.sort()
ans = 0
counter = 1
stock = lst[0]
for i in range(1, len(lst)):
  if stock == lst[i]:
    counter += 1
  else:
    ans += counter*(counter - 1)//2
    counter = 1
    stock = lst[i]
if counter >= 2:
  ans += counter*(counter - 1)//2
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

from collections import defaultdict

s = ns()
d = defaultdict(int)
d[0] += 1
k = 1
n = 0
for i in range(len(s))[::-1]:
    n += int(s[i])*k%2019
    n%=2019
    d[n] += 1
    k = (k*10)%2019

ans = 0

for j in d.values():
    if j > 1:
        ans += j*(j-1)//2

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
def power_func(a, n, p=2019):
    bi = str(format(n, "b"))  # 2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
            res=(res*a) %p
    return res

s=input()
d=[]
for i in range(len(s)):
    d.append(int(s[i])*power_func(10,len(s)-i-1,2019)%2019)
d1=[d[0]]
for g in range(1,len(s)):
    d1.append((d1[-1]+d[g])%2019)

di = defaultdict(int)
ans=0
for i in range(len(s)):
    di[d1[i]]+=1
    if d1[i]==0:
        ans+=1
    ans+=di[d1[i]]-1
print(ans)

Submission status: Accepted

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

S = input()
N = len(S)
P = 2019
if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    sys.exit()

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)

Submission status: Accepted

Solution code:
P = 2019
S = input()
N = len(S)
 
if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    exit()
 
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)

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import factorial

s = input()

rs = list()
r = 0
dr = 1
for i in range(len(s)):
    rt = (dr * int(s[-(i + 1)])) % 2019
    r = (r + rt) % 2019
    dr = (dr * 10) % 2019
    rs.append(r)

d = defaultdict(lambda: 0)

d[0] = 1
for r in rs:
    d[r] += 1

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

a = 0
for ss in s + 'x':
    if ss == '0':
        a += 1
        res -= 1
    else:
        if a >= 2:
            res -= a * (a - 1) / 2
        a = 0

print(int(res))

Submission status: Accepted

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

    val = [0] * (2019)
    tenfactor = 1
    cur = 0
    val[cur] += 1
    for i in range(N):
        cur = (cur + int(S[N - i - 1]) * tenfactor) % 2019
        tenfactor = (tenfactor * 10) % 2019
        val[cur] += 1

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
S = str(input())
l = [0]* len(S)
q = 1
l[0] = int(S[len(S) - 1])
for i in range(1,len(S)):
    t = int(S[len(S) - i - 1])
    q = q * 10 % 2019
    l[i] = (t*q + l[i - 1]%2019)%2019
l.sort()
m = [0] * len(S)
k = 1
for i in range (len(S) - 1):
    if l[i] != l[i + 1]:
        m[i] = int(k*(k-1)/2)
        k = 1
    else:
        m[i] = 0
        k += 1
if k != 1:
    m[len(S) - 1] = int(k*(k-1)/2)
a = 0
for i in range(len(S)):
    if l[i] == 0:
        a += 1
    else:
        break
print(sum(m) + a)

Submission status: Accepted

Solution code:
S = input()
S = S[::-1]
L = [0]
i = 0
for x in S:
    tmp = L[-1] + pow(10, i , 2019) * int(x) 
    L.append(tmp % 2019)
    i += 1
L = sorted(L[1::])
def counter(array):
    from collections import Counter
    return list(Counter(array).most_common())
c = counter(L)
from math import factorial
def comb(n,r):
    if n == 1: return 0
    return  n * (n - 1) // 2
ans = 0
for x in c:
    if x[0] == 0: ans += x[1]
    ans += comb(x[1],2)
print(int(ans))

Submission status: Accepted

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

rem = [0]*P
mod = 0
ten = 1
rem[mod]=1
for i in range(N):
    mod=(mod+int(S[N-i-1])*ten)%P
    ten=ten*10%P
    rem[mod]+=1
for j in rem:
    ans+=(j*(j-1))//2
print(ans)

Submission status: Accepted

Solution code:
from math import pow
def get_table():
    table = []
    for i in range(10):
        a = int(pow(10, i))
        table.append(a % 2019)
    return table

table = get_table()
# print(table)

def get_power_2019(idx):
    if (idx < len(table)):
        return table[idx]
    else:
        j = int(idx/2)
        i = idx - j
        return (get_power_2019(i) * get_power_2019(j)) % 2019

for i in range(10, 10000):
    curr = get_power_2019(i)
    table.append(curr)

s = input()
mod_dict = {}

last_mod = 0
for i in range(len(s)-1, -1, -1):
    current_lowest_digit = int(s[i])
    current_mod = ((current_lowest_digit * get_power_2019(len(s)-1-i))% 2019 + last_mod) % 2019
    if (current_mod not in mod_dict.keys()):
        mod_dict[current_mod] = [i]
    else:
        mod_dict[current_mod].append(i)
    last_mod = current_mod

# print(mod_dict)

count = 0
for k in mod_dict.keys():
    n = len(mod_dict[k])
    count += int(n*(n-1)/2)
    if (k == 0):
        count += n
print(count)

Submission status: Accepted

Solution code:
S = list(input())
rest = [0] * (len(S) + 1)
rest[0] = 0
rd = 1
for i in range(len(S)):
    rest[i+1] = (rest[i] + int(S[-(i+1)]) * rd) % 2019
    rd *= 10
    rd %= 2019
    # print(i, rest[i+1], rest[i], int(S[-(i+2)]), int(S[-(i+2)]) * 10 ** (i+1))
# print(rest)
cnt = [0] * (2019 + 1)
for i in rest: cnt[i] += 1
ans = 0
for i in range(2020):
    ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

s=input()
ans=0
p = 2019
n = len(s)
s=s[::-1]
accum=[0]*n
d=dict()
for i in range(n):
    accum[i]=int(s[i])*pow(10,i,p)%p
for i in range(n-1):
    accum[i+1]+=accum[i]
    accum[i+1]%=p
accum[-1]%=p
    #print(accum)
for i in range(n):
    if accum[i] not in d:
        if accum[i]==0:
            ans+=1
        d[accum[i]]=1
    else:
        if accum[i]==0:
            ans+=1
        ans+=d[accum[i]]
        d[accum[i]]+=1
    #print(d)
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    s = S()
    k = 2019
    tens = [1 for _ in range(len(s)+1)]
    for i in range(1, len(s)+1):
        tens[i] = tens[i-1] * 10 % k

    mods0toi = [0 for _ in range(len(s))]
    cur = 0
    for i in range(len(s))[::-1]:
        j = len(s) - i - 1
        mods0toi[i] = (cur + int(s[i]) * tens[j]) % k
        cur = mods0toi[i]
    s = collections.Counter(mods0toi)
    ans = 0
    t = s.keys()
    for c in t:
        if c == 0:
            ans += s[c]
        ans += (s[c]) * (s[c] - 1) // 2
    print(ans)

main()

Submission status: Accepted

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

num = [0] * 2019
num[0] = 1
prev = 0
result = 0
_10 = 1
for i in range(N-1, -1, -1):
    prev = (prev + int(S[i]) * _10) % 2019
    _10 *= 10
    _10 %= 2019
    result += num[prev]
    num[prev] += 1

print(result)

Submission status: Accepted

Solution code:
s = input()

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

resten = 1
ressum = int(s[-1])
res[ressum] += 1

for i in range(2, len(s)+1):
    resten = (resten*10)%2019
    ressum = (int(s[-i])*resten + ressum)%2019
    res[ressum] += 1

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

Submission status: Accepted

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

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

s = input()
n = len(s)
mod = 2019
cum = [0] * (n + 1)
cum[0] = 0
for i in range(n):
    # print(int(s[i]) - 48)
    cum[i + 1] = (cum[i] * 10 + int(s[i])) % mod
# print(cum)
mod_cum = [0] * (n + 1)
for i in range(n + 1):
    mod_cum[i] = (cum[i] * pow(10, n - i, mod)) % mod
# print(pow(10, 15, mod))
mod_cum.sort()
# print(mod_cum)
ans = 0
cnt = 1
tmp = mod_cum[0]
for i in range(n):
    if mod_cum[i + 1] == tmp:
        cnt += 1
    else:
        tmp = mod_cum[i + 1]

        if cnt > 1:
            # print(i, cnt, tmp, ans)
            ans += cnt * (cnt - 1) // 2
        cnt = 1
if cnt > 1:
    ans += cnt * (cnt - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    md=2019
    s=SI()
    n=len(s)
    vv=[0]*(n+1)
    ten=1
    for i in range(n-1,-1,-1):
        vv[i]=(vv[i+1]+int(s[i])*ten)%2019
        ten=(ten*10)%md
    vc=Counter(vv)
    ans=0
    for c in vc.values():
        ans+=c*(c-1)//2
    print(ans)

main()

Submission status: Accepted

Solution code:
S = input()
N = len(S)
C = [0 for i in range(2019)]
C[0] = 1
now = 0
tenfactor = 1

for i in range(N):
    s = int(S[-i-1])
    now = (now + s*tenfactor)%2019
    tenfactor = tenfactor*10%2019
    C[now] += 1
ans = 0
for i in range(2019):
    ans += C[i]*(C[i]-1)//2
print(ans)

Submission status: Accepted

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

a = 0
r = [0 for _ in range(m+1)]
r[0] = 1
z = 0
j = 1
for i in range(0,n):
    j = j * 10 % m
    ss = int(s[n-i-1])*j + z
    z = ss%m



    a += r[z]
    r[z] += 1

print(a)

Submission status: Accepted

Solution code:
from collections import Counter
s = input()[::-1]
n = len(s)
ans = 0
tmp_3, tmp_673 = 0, 0
c = Counter()
c[(0, 0)] = 1
for i in range(n):
	tmp_3 += int(s[i]) * pow(10, i, 3)
	tmp_3 %= 3
	tmp_673 += int(s[i]) * pow(10, i, 673)
	tmp_673 %= 673
	ans += c[(tmp_3, tmp_673)]
	c[(tmp_3, tmp_673)] += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

S = input()
S = S[::-1]
base = 2019
count = 0
mod_list = [0]
ten = 1
for i in range(len(S)):
    mod = (ten*int(S[i]))%base
    mod_list.append((mod+mod_list[i])%base)
    ten*= 10
    ten%= base

c = Counter(mod_list)

for i in range(2019):
    num = c[i]
    count += num*(num-1)//2
print(count)

Submission status: Accepted

Solution code:
s=str(input())
n=len(s)
k=[0]*(n+1)
for i in range (1,n+1):
    k[i]=int(s[i-1])
t=[0]*(n+1)
t[0]=0  
for i in range(1,n+1):
    t[i]=(10*t[i-1]+k[i])%2019

p=1
q=[0]*448
for z in range(0,448):
    q[z]=p%2019
    p=10*q[z]

d=[0]*n   
for j in range(1,n+1):
    f=(n-j)%448
    d[j-1]=q[f]*t[j]%2019
ds=sorted(d)
ct=0
ans=0
if ds[0]==0:
    ct=1
    ans=1
for i in range(n-1):
    if ds[i+1]==ds[i]:
        ct+=1
        ans+=ct
    else:
        ct=0
print(ans)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

mod = 2019
s = input()
rui = []
ima = 0
ten = []
ten = 1
ss = [0]*len(s)
for i in reversed(range(len(s))):
    num = int(s[i])*ten
    ss[i] = num % mod
    ten *=10
    ten %= mod

ima = 0
for i in reversed(range(len(ss))):
    ima +=  int(ss[i])
    ima = ima % mod
    rui.append(ima)
dp = [0]*mod
for  i in range(len(rui)):
    dp[rui[i]] += 1
ans = dp[0]
for i in range(mod):
    tmp = dp[i] 
    ans += tmp*(tmp-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

S = input()
#S = "1"*20000

p = 2019 # 10 と互いに素なのであんまり桁のずれは関係ない？
N = len(S)

# m は各桁の累積和
m = [(int(S[i]) * pow(10, N-i, p)) % p for i in range(N)]

# m の mod 累積和
r = [0] * N
r[0] = m[0]
for ri in range(1, N):
    r[ri] = (r[ri-1] + m[ri]) % p

# この r[i] が一致するような区間が答えになるのでこれをもとめる
c = Counter(r)

ans = 0
for ci in [cv for cv in c.values() if cv >= 2]:
    ans += ci * (ci-1) // 2

if 0 in c.keys():
    ans += c[0]

print(ans)

Submission status: Accepted

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

if n<=4:
  print('0')
  exit()  

yo_list1=[1,10,100,1000]
yo1=1000
for i in range(200000):
  yo1 = yo1*10 % 2019
  yo_list1.append(yo1)

yo_dict = {i:0 for i in range(2019)}

yo2=int(s[n-1])
yo_dict[0]=1
yo_dict[yo2]=1

for i in range(1,n):
  yo2 = ( int(s[n-1-i])*yo_list1[i] + yo2 ) % 2019
  yo_dict[yo2]+=1

count=0
for i in range(2019):
  yo3 = yo_dict[i]
  if yo3>=2:
    count+=yo3*(yo3-1)//2
print(count)

Submission status: Accepted

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

Submission status: Accepted

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

s_len = len(s)
ref = [0] * s_len

for i in range(1, s_len + 1):
    ref[-i] = int(s[-i]) * pow(10, i, MOD) % MOD

for i in range(1, s_len):
    ref[-i - 1] += ref[-i]
    ref[-i - 1] %= MOD

ref_cnt = Counter(ref)
ans = sum(ref_cnt.values()) - len(ref_cnt)


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

if 0 in ref:
    ans += ref_cnt[0]

print(ans)

Submission status: Accepted

Solution code:
s = input()
p = 2019
n = len(s)
ans = 0

d = [0 for _ in range(n + 1)]
ten = 1

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

cnt = [0 for _ in range(p)]
for i in range(n, -1, -1):
    ans += cnt[d[i]]
    cnt[d[i]] += 1


print(ans)

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 collections import Counter

S = input()

"""
counts = Counter()
total = 0
for d in S:
    d = int(d)
    nextCounts = Counter()
    nextCounts[d] += 1
    for k, v in counts.items():
        nextCounts[(10 * k + d) % 2019] += v

    counts = nextCounts
    total += counts[0]
    #print(counts)

print(total)

"""

"""
def modInverse(a, m):
    m0 = m
    y = 0
    x = 1

    if m == 1:
        return 0

    while a > 1:

        # q is quotient
        q = a // m

        t = m

        # m is remainder now, process
        # same as Euclid's algo
        m = a % m
        a = t
        t = y

        # Update x and y
        y = x - q * y
        x = t

    # Make x positive
    if x < 0:
        x = x + m0

    return x
"""


#div10 = modInverse(10, 2019)

div10 = 202
#m = 1
mInv = 1

off = 0
counts = [0 for i in range(2019)]
total = 0
for d in S:
    d = int(d)
    off = (10 * off + d) % 2019
    #m *= 10
    mInv = (mInv * div10) % 2019
    #assert modInverse(m, 2019) == mInv
    counts[((d - off) * mInv) % 2019] += 1
    total += counts[((0 - off) * mInv) % 2019]

print(total)

Submission status: Accepted

Solution code:
# 2019 = 3*673
MOD = 2019
S = input()
N = len(S)
X = [0]*2100
X[0] += 1
tmp = 0
hoge = pow(10,N,2019)

for i in range(N):
    tmp = (tmp*10+int(S[i]))%MOD
    hoge = (hoge*202)%MOD 
    X[(tmp*hoge)%MOD] += 1

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
s=input()
dic=dict()
accum=0
exp=1
dic[0]=1
ans=0
length=len(s)
for i in range(length):
  temp=exp*int(s[length-i-1])
  exp*=10
  exp%=2019
  accum+=temp
  accum%=2019
  if accum in dic:
    ans+=dic[accum]
    dic[accum]+=1
  else:
    dic[accum]=1
print(ans)

Submission status: Accepted

Solution code:
P = 2019
S = input()
N = len(S)
res = 0
 
if P in [2,5]:
    for i in range(N):
        if int(S[i])% P == 0:
            res += i+1
else:
    dic = {0:1}
    t1 = 0
    t2 = 1
    for i in range(N):
        t2 = (10*t2) % P
        t1 = (int(S[N-1-i])*t2 + t1) % P
        if t1 in dic:
            res += dic[t1]
            dic[t1] += 1
        else:
            dic[t1] = 1
 
print(res)

Submission status: Accepted

Solution code:
P = 2019
S = input()
N = len(S)
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:
S = input()
N = len(S)
C = [0 for i in range(2019)]
C[0] = 1
now = 0
tenfactor = 1

for i in range(N):
    s = int(S[-i-1])
    now = (now + s*tenfactor)%2019
    tenfactor = tenfactor*10%2019
    C[now] += 1
ans = 0
for i in range(2019):
    ans += C[i]*(C[i]-1)//2
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
readline = sys.stdin.readline

S = list(map(int, readline().strip()))
N = len(S)
C = Counter()
C[0] = 1
ans = 0
MOD = 2019
res = 0
for i in range(N):
    s = S[N-1-i]
    res = (res+s*pow(10, i, MOD))%MOD
    ans += C[res]
    C[res] += 1
print(ans)

Submission status: Accepted

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

def solve(S,P):
    S = S[::-1]
    T = [0] * len(S)
    T[0] = S[0] % P
    power = 1
    for i in range(1, len(S)):
        power *= 10
        power %= P
        T[i] = T[i-1] + power * 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 math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

s=input()
su=[0 for _ in range(len(s))]
su[0]=int(s[-1])
for i in range(1,len(s)):
    ii=len(s)-i-1
    o=int(s[ii])*pow(10,i,2019)
    su[i]=(su[i-1]+o)

    su[i]%=2019
su=su+[0]
a_dic=Counter(su)
ans=0

for i in a_dic.keys():
    if a_dic[i]<2:
        continue
    ans+=combinations_count(a_dic[i],2)

print(ans)

Submission status: Accepted

Solution code:
s=input()
a=len(s)
b=a-4
c=0
mod=2019
num=[0]*mod
num[0] = 1
now=0
ans=0
_10 = 1
for i in range(a-1, -1, -1):
    now=(now+int(s[i])*_10)%mod
    _10*=10
    _10%=mod
    ans+=num[now]
    num[now]+=1
print(ans)

Submission status: Accepted

Solution code:
# %%time
s = input()
c = 0
mod = 2019
s_int = list(map(int, list(s)))

tens = [1]
for k in range(len(s)):
    tens.append((tens[-1] * 10)%mod )

ms = []
m = s_int[-1]%mod
ms.append(m)
for i in range(len(s) - 1)[::-1]:
    m = s_int[i] * tens[len(s) - i - 1] +  m
    m = m %mod
    ms.append(m)
    if m == 0:
        c += 1
        
from collections import Counter
co = Counter(ms)
for v in co.values():
    c += v * (v - 1) // 2

print(c)

Submission status: Accepted

Solution code:
from collections import Counter
  
P = 2019
S = input()
N = len(S)

ans = 0
S = S[::-1]
a, temp = [int(S[0]) % P], 1
for i in range(1, N):
    temp *= 10
    temp %= P
    val = (a[i-1] + (int(S[i]) % P * temp) % P) % P
    a.append(val)    
    
c = Counter(a)
if 0 in c:
    ans += c[0]
    ans += c[0] * (c[0] - 1) // 2
    del c[0]
for x in c.keys():
    ans += c[x] * (c[x]-1) // 2 
print(ans)

Submission status: Accepted

Solution code:
S = input()
N = len(S)
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)

Submission status: Accepted

Solution code:
from itertools import combinations
s = input()
d = {0: 1}
tmp = 0
i = 0
for char in s[::-1]:
    tmp += int(char) * pow(10, i, 2019)
    tmp %= 2019
    if tmp not in d:
        d[tmp] = 1
    else:
        d[tmp] += 1
    i += 1

result = 0
for num, v in d.items():
    result += v * (v - 1) // 2

print(result)

Submission status: Accepted

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

T=[]
now=1
for i in range(n):
    T.append(now*int(S[-i-1])%mod)
    now=now*10%mod
C=[]
now=0
for i in range(n):
    now+=T[i]
    now%=mod
    C.append(now)
C.sort()
now=0
cnt=1
A=[]
for i in range(n):
    if now==C[i]:
        cnt+=1
    else:
        if cnt>=2:
            A.append(cnt)
        now=C[i]
        cnt=1
if cnt>=2:
    A.append(cnt)

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

Submission status: Accepted

Solution code:
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
import math
import itertools
from collections import defaultdict
from collections import Counter
import numpy as np
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def binary(n):
    return bin(n)[2:]

# バイナリ法
def pow_by_binary_exponentiation(a, x, n): # a^x mod n
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y

# モンゴメリ冪乗法
def pow_by_montgomery_ladder(a, x, n): # a^x mod n
    x = [int(b) for b in binary(x)[::-1]]
    k = len(x)
    a1 = a
    a2 = a**2
    for i in range(k - 2, -1, -1):
        if x[i] == 0:
            a2 = (a1 * a2) % n
            a1 = (a1**2) % n
        else:
            a1 = (a1 * a2) % n
            a2 = (a2**2) % n
    return a1

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
#a,b,c,d=list(map(int,input().split()))
s=input()
#s="3"*20000
su=[0 for _ in range(len(s))]
su[0]=int(s[-1])
for i in range(1,len(s)):
    ii=len(s)-i-1
    o=int(s[ii])*pow(10,i,2019)
    #su[i]=su[i-1]+(int(s[ii])*(10**i))
    #su[i]=su[i-1]+pow(int(s[ii]),10**i,2019)
    su[i]=(su[i-1]+o)

    su[i]%=2019
a_dic=Counter(su)
#print(su)
#print(a_dic)
ans=0
if 0 in a_dic.keys():
    ans+=a_dic[0]

for i in a_dic.keys():
    if a_dic[i]<2:
        continue
    ans+=combinations_count(a_dic[i],2)

print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = str(onem())

dp = [0 for i in range(2019)]
ans = 0
dp[0] = 1
dp[int(n[-1])] = 1
ten = 1
po = int(n[-1])
for i in range(len(n)-2,-1,-1):
    ten *= 10
    ten %= 2019
    po += ten*int(n[i])
    po %= 2019
    
    ans += dp[po]

    dp[po] += 1
    



print(ans)

Submission status: Accepted

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

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

def input_multiple_number_as_list():
    return list(map(int, input().split()))
 
mod = 2019
S = input()
 
checklist = [0] * mod
checklist[0] = 1
ans = 0
obs = 1
now = 0
for i in range(len(S)-1, -1, -1):
    now = (now + int(S[i]) * obs) % mod
    obs = (obs*10)%mod
    ans += checklist[now]
    checklist[now] += 1
 
print(ans)

Submission status: Accepted

Solution code:
s = str(input())
p = 2019
mod = [0]*2019
mod[0] += 1#右端から見たときに2019の倍数がある場合に対応
now = 0
_10 = 1
for i in range(len(s)-1, -1, -1):
  now = (now + int(s[i])*_10) % p
  _10 *= 10
  _10 %= p
  mod[now] += 1
ans =  0
for i in mod:
  ans += i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
s=input()
n=len(s)
rst=[0 for j in range(2019)]
rst[0]=1
x=0
ans=0
drst=1
for i in range(n):
    y=(int(s[n-1-i])*drst)%2019
    drst=(drst*10)%2019
    x+=y
    if x>=2019:
        x%=2019
    #print(x,y,drst)
    ans+=rst[x]
    rst[x]+=1
#if rst[0]==1:
    #ans+=0

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

d = defaultdict(int)
d[0] = 1
s, p = 0, 1
for c in reversed(input()):
  s = (s + p * int(c)) % 2019
  d[s] = d.get(s, 0) + 1
  p = p * 10 % 2019
print(sum(x * (x - 1) // 2 for x in d.values()))

Submission status: Accepted

Solution code:
def resolve():
    s = [int(i) for i in input()]
    p_cnt = 0

    p = 2019

    s = s[::-1]
    div_dic = dict(zip(range(p), [0] * p))
    tmp = 0

    for i in range(len(s)):
        tmp += s[i] * pow(10, i, p)
        tmp %= p
        div_dic[tmp] += 1

    for v in div_dic.values():
        p_cnt += v * (v - 1)
    p_cnt //= 2
    p_cnt += div_dic.get(0)


    print(p_cnt)
    
resolve()

Submission status: Accepted

Solution code:
import sys
from collections import Counter, defaultdict
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

S = read().decode().rstrip()

reminders = defaultdict(lambda: 0)
tmp = 0
mul = 1

for c in S[::-1]:
    c = int(c)
    tmp = (tmp + c * mul) % 2019
    mul = mul * 10 % 2019
    reminders[tmp] += 1
reminders[0] += 1

ans = 0

for r, cnt in reminders.items():
    ans += cnt * (cnt - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
import os

import math
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def get_factors(n):
    """
    素因数分解
    :param int n:
    :rtype: list of int
    """
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


S = sys.stdin.buffer.readline().decode().rstrip()
N = len(S)
MOD = 2019

hist = []
mod_counts = [0] * MOD
power = 1
n = 0
for i in reversed(range(N)):
    n += int(S[i]) * power
    n %= MOD
    mod_counts[n] += 1
    hist.append(n)
    power *= 10
    power %= MOD

ans = 0
m = 0
power = 1
for i in reversed(range(N)):
    # m = int(S[i + 1:] or 0) % MOD
    ans += mod_counts[m]
    mod_counts[hist[~i]] -= 1

    m += int(S[i]) * power
    m %= MOD
    power *= 10
    power %= MOD
print(ans)



def test(S, mod):
    ans = 0
    for l in range(len(S)):
        for r in range(l + 1, len(S) + 1):
            n = int(S[l:r])
            if n % mod == 0:
                print(n)
                ans += 1
    print(ans)


# test(S, 2019)
# print()
# test(S, 2019 // 3)

Submission status: Accepted

Solution code:
S = input()
N=len(S)
M = [0 for _ in range(2019)]
# 0は予め右端に一個あるとする
M[0]+=1
old = 0
for i in range(N):
    new_s = int(S[N-1-i])*pow(10,i,2019)
    new = (new_s + old) % 2019
    M[new] += 1
    old = new
count = 0
for m in M:
    count += int(m*(m-1)/2)
print(count)

Submission status: Accepted

Solution code:
d = {0: 1}
s, p = 0, 1
for c in reversed(input()):
  s = (s + p * int(c)) % 2019
  d[s] = d.get(s, 0) + 1
  p = p * 10 % 2019
print(sum(x * (x - 1) // 2 for x in d.values()))

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:
p = 2019
s = input()
n = len(s)
l = [0 for i in range(p)]
l[0] = 1
ten = 1
cnt = 0
 
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    for i in range(n):
        cnt = (cnt + int(s[-i-1]) * ten) % p
        l[cnt] += 1
        ten = (ten * 10) % p
    for i in l:
        if i > 1:
            ans += i * (i - 1) // 2
print(ans)