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:
def d_multiple_of_2019():
    from collections import Counter
    S = [int(ch) for ch in input()]

    s = S[::-1]
    n = len(S)
    u = [0] * n

    # u[0] = s[0]
    # power = 1
    # for i in range(1,n):
    #     power *= 10
    #     u[i] = u[i-1] + power * s[i]

    p = 2019
    u[0] = s[0] % p
    power = 1
    for i in range(1, n):
        power *= 10
        power %= p
        u[i] = u[i - 1] + power * s[i]
        u[i] %= p
    count = Counter(u)
    ans = 0
    for k, v in count.items():
        ans += v * (v - 1) // 2
    return ans + count[0]

print(d_multiple_of_2019())

Submission status: Accepted

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


def combi(x):
    return (x*(x-1))//2

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

D={i:0 for i in range(2019)}
for ele in L:
    D[ele]+=1

ans=0
for key in D:
    if D[key]>1:
        ans+=combi(D[key])
    
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().strip()


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

    # base[i] = 10**i % 2019
    base = [0] * l
    base[0] = 1
    for i in range(1, l):
        base[i] = (base[i - 1] * 10) % 2019 

    d = defaultdict(int)
    #show = [0] * l
    pre = 0
    for i in range(l):
        j = l - i - 1
        rem = (pre + int(S[j]) * base[i]) % 2019 # rem = (S[j]...S[l-1]) % 2019
        d[rem] += 1
        #show[j] = rem
        pre = rem
    #print(show)
    
    ans = 0
    for rem in d:
        n = d[rem]
        ans += n * (n - 1) // 2
    print(ans + d[0])

    
    
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
s=input()
n=len(s)
s=s[::-1]
accum=[0]*n
p=2019
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
ans=0
#print(accum)
for i in range(n):
    #print(d)
    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(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import Counter

s = input()
s = list(s)[::-1]
ten = [1]
for _ in range(len(s)):
  ten.append(ten[-1]*10 % 2019)
  
A = [(int(s[i])  * ten[i])%2019 for i in range(len(s))]
A = list(accumulate(A))
A = [a%2019 for a in A]
A = [0] + A

A = Counter(A).most_common()
ans = 0
for _, count in A:
  if count == 1:
    break
  ans += count*(count-1)//2
print(ans)

Submission status: Accepted

Solution code:
s = input()

tens = 1
mod = 2019

rests = [0 for i in range(len(s))]

for i in range(len(s)):
    if i == 0:
        rests[-(i+1)] = int(s[-(i+1)])
    else:
        rests[-(i+1)] = (rests[-i] + (tens * int(s[-(i+1)]))) % mod

    tens *= 10
    tens = tens % mod

dic = {}
for i in range(len(rests)):
    if dic.get(rests[i], None) is None:
        dic[rests[i]] = 1
    else:
        dic[rests[i]] += 1

ans = 0

for k in dic:
    if k == 0:
        ans += dic[k]
        ans += dic[k] * (dic[k] - 1) // 2

    elif dic[k] > 1:
        ans += (dic[k] * (dic[k] - 1)) // 2

print(ans)

Submission status: Accepted

Solution code:
S = input()
ans = 0
mods = [0] * 2019
mods[0] = 1
curr = 0
x = 1
for d in S:
    curr = curr * 10 + int(d)
    ans += mods[curr * x % 2019]
    mods[curr * x % 2019] += 1
    x = x * 202 % 2019
    curr %= 2019
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
from operator import mul
from functools import reduce


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def solve(S: str):
    if len(S) < 4:
        print(0)
        exit()
    prev = int(S[-1])
    digit = 10
    count = defaultdict(int)
    for i in range(1,len(S)+1):
        k = prev % 2019
        # print(prev)
        count[k]+=1
        if i == len(S):
            break
        prev = (prev + digit*int(S[-i-1]))%2019
        digit=digit*10%2019
    sum = 0
    for k in count:
        if k == 0:
            sum += count[k]
            if count[k] >= 2:
                sum += combinations_count(count[k], 2)
            continue
        if count[k] < 2:
            continue
        sum += combinations_count(count[k],2)
    print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens) # type: int
    solve(S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import Counter

mod = 2019
s = input()
keta = len(list(s))
JJ = [0 for i in range(keta + 2)]
JJ[0] = 1
JJG = [0 for i in range(keta + 2)]
JJG[0] = 1
for i in range(1, keta + 2):
    JJ[i] = (10 * JJ[i - 1]) % mod
    JJG[i] = pow(JJ[i], mod - 2, mod)

S = [0] * (keta)


for i in range(keta - 1, -1, -1):

    S[i] = int(s[keta - 1 - i]) * JJ[i]
    S[i] %= mod

SA = [0] * (keta)
SA[0] = S[0]
for i in range(keta - 1):
    SA[i + 1] = SA[i] + S[i + 1]
    SA[i + 1] %= mod


ans = 0

SC = Counter(SA)
for e, i in Counter(SA).items():
    if e > 0:
        ans += i * (i - 1) // 2
    else:
        ans += i
        ans += i * (i - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
S = input()

S = S[::-1]
N = len(S)
cnt = [0] * 2019
mod = 2019
m = 0
cnt[0] += 1
for i in range(N):
    s = int(S[i]) * (pow(10, i, mod))
    s %= mod
    m += s
    m %= mod
    cnt[m] += 1


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

print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict

def submit():
    s = [int(c) for c in input()]
    modp = 2019

    curr = 0
    modp_count = defaultdict(int)
    modp_count[0] = 1
    ans = 0
    base = 1
    for c in reversed(s):
        curr += base * c
        curr_mod = curr % modp
        ans += modp_count[curr_mod]
        modp_count[curr_mod] += 1
        base *= 10
        base %= modp
    
    print(ans)
    

submit()

Submission status: Accepted

Solution code:
def modpow(d, b, p, mod=2019):
    ret = 1
    while p > 0:
        if p % 2 == 1:
            ret = ret * b % mod
        b = b * b % mod
        p //= 2
    return (d * ret) % mod


S = input()
C = [0]
for i in range(len(S)):
    C.append((C[-1] + modpow(int(S[-(i + 1)]), 10, i)) % 2019)
Cd, C0 = {}, 0
for c in C[1:]:
    if c == 0:
        C0 += 1
    else:
        Cd[c] = Cd.get(c, 0) + 1
print(C0 + C0 * (max(0, C0 - 1)) // 2
      + sum([v * (v - 1) // 2 for v in Cd.values()]))

Submission status: Accepted

Solution code:

S = input()
N = len(S)
P = 2019

# ABC158
cnt = 0

table = [0] * P 
Ui = 0
ten = 1

S = S[::-1]
table[0] = 1 

for i in range(N):
    Ui = (Ui + int(S[i]) * ten) % P 
    
    cnt += table[Ui] 
    
    table[Ui] += 1 
    ten = (ten * 10) % P 
print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

MOD = 2019

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return a*b%MOD

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = (1,0,a)
    w = (0,1,b)
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return (w[0],w[1])

def mod_inv(a):
    x,_  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res    
s=s_in()

from collections import Counter


p = 2019
c = Counter()
current = int(s[len(s)-1])
c[0]+=1
c[current]+=1

for i in range(len(s)-2, -1,-1):
    current = mod_add(current, mod_mul(int(s[i]), mod_pow(10, len(s)-i-1)))
#    print(current)
    c[current%p] += 1

#print(c)
res = 0
for k in c.values():
    res += k*(k-1)//2

print(res)

Submission status: Accepted

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

    l = [[[] for j in range(3)] for i in range(673)]
    l[0][0].append(0)
    mo = 0
    ten = 1
    mod = 673
    now = 0
    ans = 0
    for i in range(len(s)):
        a = int(s[i])*ten
        mo = (mo+a)%3
        now = (now+a)%mod
        if l[now][mo]:
            ans += len(l[now][mo])
        l[now][mo].append(i+1)
        ten *= 10
        ten %= 2019
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = input()
l = len(n)
key = [0]*2019
mod = 1
judge = 0
for i in range(l):
  judge += ((mod%2019)*int(n[l-i-1]))%2019
  judge %= 2019
  k = judge%2019
  key[k] += 1
  mod *= 10
  mod %= 2019

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

Submission status: Accepted

Solution code:
p = 2019
s  = list(map(int, list(input())))[::-1]
sm = 0
cnt = [0] * p
cnt[0] = 1
n = len(s)
for i in range(n):
    d = s[i] * pow(10, i, p)
    sm = (sm + d) % p
    cnt[sm] += 1
ans = 0
for i in range(p):
    ans += cnt[i] * (cnt[i]-1) // 2
print(ans)

Submission status: Accepted

Solution code:
s=input()
l=len(s)
se=dict()
k=0
for i in range(l-1,-1,-1):
    #print(0)
    k+=(pow(10,l-1-i,2019)*int(s[i]))
    k%=2019
    if k in se:
        se[k]+=1
    else:
        se[k]=1

ans=0
for j in se:
    i=se[j]
    if i>1:
        ans+=(i*(i-1)//2)
    if j==0:
        ans+=i
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

S = input()
S = S[::-1]
N = len(S)
MOD = 2019
D = defaultdict(int)
res = 0
p = 1
for i in range(N):
    tmp = res + int(S[i]) * p
    tmp %= MOD
    D[tmp] += 1

    res = tmp
    p *= 10
    p %= 2019 

ans = 0
for k,v in zip(D.keys(), D.values()):
    if k == 0:
        ans += v
        ans += v * (v - 1) //2
    elif v >= 2:
        ans += v * (v - 1) // 2

print(ans)

Submission status: Accepted

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

mod = {}

_s = 0
for i in range(n):
  _s = (_s + int(s[-(i + 1)]) * pow(10, i, 2019)) % 2019
  if _s in mod:
    mod[_s] = mod[_s] + 1
  else:
    mod[_s] = 1

ans = 0
for x in mod.keys():
  if x == 0:
    ans += mod[x] * (mod[x] + 1) // 2
  else:
    ans += mod[x] * (mod[x] - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
s = input()
n = len(s)
MOD=2019
ls=[0]*n
ls[-1] = int(s[-1])
freq=[0]*2019
for i in reversed(range(1,n)):
    ls[i-1] = (ls[i]+int(s[i-1])*pow(10,n-i,MOD))%MOD
    
for i in range(n):
    freq[ls[i]]+=1
ans=0
for i in range(2019):
    if i==0:
        ans+=freq[i]*(freq[i]+1)//2
    else:
        ans+=freq[i]*(freq[i]-1)//2

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as dict

s = input()
n = len(s)
p = 2019
a = []
for x in s:
    a.append(int(x))

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

print(ans)

Submission status: Accepted

Solution code:
s = str(input())
MOD = 2019
modl = [0 for _ in range(2019)]
modl[0] = 1
cnt = 1
x = 0
for i in range(len(s)):
	x = (x+(int(s[len(s)-1-i])*cnt))%MOD
	modl[x] += 1
	cnt = (cnt*10)%MOD

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

Submission status: Accepted

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

N = len(S)
A = [0]
base = 1
for i in range(N):
	A.append((A[-1] + S[N-1-i] * base) % 2019)
	base = base * 10 % 2019
A.sort()
ans = 0
cnt = 1
for i in range(N):
	if i == N-1:
		if cnt > 1:
			cnt += 1
			ans += (cnt * (cnt - 1)) // 2
	elif A[i] == A[i+1]:
		cnt += 1
	else:
		ans += (cnt * (cnt - 1)) // 2
		cnt = 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

p = 2019
s = list(map(int, input()))

ans = 0

s = s[::-1]
power = 1
t = [0] * len(s)
t[0] = s[0] % p
for i in range(1, len(s)):
    power = power * 10 % p
    t[i] = (t[i-1] + s[i] * power) % p

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

Submission status: Accepted

Solution code:
S=input()
N=len(S)
a=[0]*(N+1)
m=2019
for i,c in enumerate(reversed(S)):
    a[i+1]=(int(c)*pow(10,i,m)+a[i])%m
from collections import Counter
c=Counter(a)
r=0
for k,v in c.items():
    r+=v*(v-1)//2
print(r)

Submission status: Accepted

Solution code:
from collections import Counter

def main():
    s = list(map(int,input()[::-1]))

    t = []
    m = 0
    for i,s_i in enumerate(s):
        m = m+s_i*pow(10,i,2019)
        t.append(m%2019)
    
    c = Counter(t)
    ans = c[0]
    for i in c.values():

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
x = input()
ll = len(x)

now = 0
mod_dict = {}
mod_dict[0] = 1
for i in reversed(range(len(x))):
    now = now + int(x[i]) * pow(10, (ll - i - 1), 2019)

    now %= 2019
    if now not in mod_dict:
        mod_dict[now] = 1
    else:
        mod_dict[now] = mod_dict[now] + 1

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

Submission status: Accepted

Solution code:
from collections import Counter
Next = [i*10 % 2019 for i in range(2019)]
S = input()
L = list(reversed(S))
Amaris = []#「右から」x桁まで見た場合の余り
amari = 0
kurai = 1
for l in L:
    amari += kurai*int(l)
    amari %= 2019 
    kurai *= 10
    kurai %= 2019
    Amaris.append(amari)
C = Counter(Amaris)
ans = 0 
for d in C.values():
    ans += d*(d-1)//2
print(ans + C[0])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
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)
    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:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

s = ins()
n = len(s)
t = [-1]*(n+1)
r = [0]*2019
c = 1
t[n] = 0
r[0] = 1
t[n-1] = int(s[n-1])
r[t[n-1]] = 1
for i in range(n-2,-1,-1):
    c = (c*10)%2019
    t[i] = (t[i+1]+int(s[i])*c)%2019
    r[t[i]] += 1
#ddprint(t)
sm = 0
for i in range(2019):
    sm += r[i]*(r[i]-1)//2
print(sm)

Submission status: Accepted

Solution code:

MOD = 10 ** 9 + 7

def main():
    for _ in inputt(1):
        S = input()
        D = [0] * 2019
        t = 0
        for ch in S:
            c = ord(ch) - 48
            nD = [0] * 2019
            nD[c] = 1
            for i, d in enumerate(D):
                nD[(i * 10 + c) % 2019] += d
            D = nD
            t += D[0]
        print(t)

# region M


# region import
# 所有import部分

from math import *
from heapq import *
from itertools import *
from functools import reduce, lru_cache, partial
from collections import Counter, defaultdict
import re, copy, operator, cmath
import sys, io, os, builtins
sys.setrecursionlimit(1000)

# endregion

# region fastio

BUFSIZE = 8192
class FastIO(io.IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = io.BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(io.IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
def print(*args, **kwargs):
    if args:
        sys.stdout.write(str(args[0]))
        split = kwargs.pop("split", " ")
        for arg in args[1:]:
            sys.stdout.write(split)
            sys.stdout.write(str(arg))
    sys.stdout.write(kwargs.pop("end", "\n"))
def debug(*args, **kwargs):
    print("debug", *args, **kwargs)
    sys.stdout.flush()
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip()
inputt = lambda t = 0: range(t) if t else range(int(input()))
inputs = lambda: input().split()
inputi = lambda: map(int, inputs())
inputl = lambda t = 0, k = lambda: list(inputi()): [k() for _ in range(t)] if t else list(k())

# endregion

# region bisect

def len(a):
    if isinstance(a, range):
        return -((a.start - a.stop) // a.step)
    return builtins.len(a)
def bisect_left(a, x, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    while lo < hi:
        mid = (lo + hi) // 2
        if key(a[mid]) < x: lo = mid + 1
        else: hi = mid
    return lo
def bisect_right(a, x, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    while lo < hi:
        mid = (lo + hi) // 2
        if x < key(a[mid]): hi = mid
        else: lo = mid + 1
    return lo
def insort_left(a, x, key = None, lo = 0, hi = None):
    lo = bisect_left(a, x, key, lo, hi)
    a.insert(lo, x)
def insort_right(a, x, key = None, lo = 0, hi = None):
    lo = bisect_right(a, x, key, lo, hi)
    a.insert(lo, x)
do_nothing = lambda x: x
bisect = bisect_right
insort = insort_right
def index(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    i = bisect_left(a, x, key, lo, hi)
    if lo <= i < hi and key(a[i]) == x: return a[i]
    if default != None: return default
    raise ValueError
def find_lt(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_left(a, x, key, lo, hi)
    if lo < i <= hi: return a[i - 1]
    if default != None: return default
    raise ValueError
def find_le(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_right(a, x, key, lo, hi)
    if lo < i <= hi: return a[i - 1]
    if default != None: return default
    raise ValueError
def find_gt(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_right(a, x, key, lo, hi)
    if lo <= i < hi: return a[i]
    if default != None: return default
    raise ValueError
def find_ge(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_left(a, x, key, lo, hi)
    if lo <= i < hi: return a[i]
    if default != None: return default
    raise ValueError

# endregion

# region csgraph
# TODO

class Tree:
    def __init__(n):
        self._n = n
        self._conn = [[] for _ in range(n)]
        self._list = [0] * n
    def connect(a, b):
        pass

# endregion

# region ntheory
# TODO

class Sieve:
    def __init__(self):
        self._n = 6
        self._list = [2, 3, 5, 7, 11, 13]
    def extend(self, n):
        pass


sieve = Sieve()
def isprime(n):
    pass
def prime(n):
    pass
def factorint(n):
    factordict = defaultdict(int)
    for i in sieve:
        if n <= i * i:
            break
        while not n % i:
            factordict[i] += 1
            n //= i
    if n != 1:
        factordict[n] += 1
    return factordict

# endregion

# region main

if __name__ == "__main__":
    main()

# endregion


# endregion

Submission status: Accepted

Solution code:
import sys,math,copy,queue,itertools,bisect,collections
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
INF = 10**18
MOD = 2019
DD = ((1,0),(0,1),(-1,0),(0,-1))

s = [int(x) for x in sys.stdin.readline().rstrip()]
amari = {0:1}
m = 0
t = 1
for i in range(len(s)-1,-1,-1):
    m = (t *s[i] + m) % MOD
    if m in amari:
        amari[m] += 1
    else:
        amari[m] = 1
    t = (t * 10) % MOD

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

print (ans)

Submission status: Accepted

Solution code:
def main():
    mod = 2019
    s = input()
    dp = []
    mods = {}
    for i in range(len(s)):
        x = int(s[i])*pow(10,len(s)-1-i,mod)
        x %= mod
        if not dp:
            dp.append(x)
        else:
            dp.append(dp[-1]+x)

        dp[-1] %= mod
        if dp[-1] not in mods.keys():
            mods[dp[-1]] = 0

        mods[dp[-1]] += 1

    ans = 0
    for i in mods.keys():
        if i == 0:
            ans += mods[i]

        x = mods[i]
        ans += x*(x-1)//2

    print(ans)


main()

Submission status: Accepted

Solution code:
s = input()

remain = [0]*2020
now = 0
ans = 0
for i in range(len(s)-1, -1, -1):
    now += int(s[i])*pow(10, len(s)-i-1, 2019)
    ans += remain[now%2019]
    remain[now%2019] += 1

ans += remain[0]

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
p = 2019
s = list(map(int, input()))
n = len(s)
ans = 0
if p == 2:
    for i, c in enumerate(s):
        if c % 2 == 0:
            ans += i + 1
elif p == 5:
    for i, c in enumerate(s):
        if c % 5 == 0:
            ans += i + 1
else:
    l = [0] * (n + 1)
    for i, c in enumerate(s):
        l[i + 1] = l[i] + pow(10, n - i - 1, p) * c
        l[i + 1] %= p
    for v in Counter(l).values():
        ans += v * (v - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
s=input().rstrip()
n=len(s)
l=[0]
for i in range(n):
    x=int(s[n-1-i])
    y=l[-1]+x*pow(10,i,2019)
    l.append(y%2019)
c=[0]*2019
for i in l:
    c[i]+=1
ans=0
for i in c:
    ans+=i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

S = input()
L = len(S)

dp = [0] * (L + 1)
pow = [1] * (L + 1)
cnt = [0] * 2019

ans = 0
for i in range(L):
    pow[i + 1] = pow[i] * 10 % 2019
    dp[i + 1] = (dp[i] + int(S[L - i - 1]) * pow[i]) % 2019
    if dp[i + 1] == 0:
        cnt[dp[i + 1]] += 1
        ans += cnt[dp[i + 1]]
    else:
        ans += cnt[dp[i + 1]]
        cnt[dp[i + 1]] += 1

print(ans)

Submission status: Accepted

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

S = readline().strip()
S = list(map(int, S))
N = len(S)
P = 2019

rems = [0] * N
a = 1
b = 0
for i in range(N):
    b = (b + (a * S[N - i - 1]) % P) % P
    rems[N - i - 1] = b
    a = a * 10 % P

rems = rems + [0]

counts = [0] * P


for i in range(len(rems)):
    counts[rems[i]] += 1

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

print(ans)

Submission status: Accepted

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

T = [0] * (N + 1)
T[0] = 0
e = 1
for i in range(N):
  T[i + 1] = T[i] + int(S[N - i - 1]) * e
  T[i + 1] %= P
  e *= 10
  e %= P

a = {}
for i in range(N + 1):
  if T[i] in a:
    a[T[i]] += 1
  else:
    a[T[i]] = 1

num = 0
if P % 2 == 0 or P % 5 == 0:
  for i in range(N):
    if int(S[i]) % P == 0:
      num += 1 + i
else:
  for k in a:
    num += a[k] * (a[k] - 1) // 2

print(num)

Submission status: Accepted

Solution code:
S = input()
#revS = S[::-1]
ls = len(S)
cur_num = 0
cur_r = 0
r = [0]*ls
ans = 0
for i in range(ls):
    if i == 0:
        r[i] = (int(S[ls-i-1])*pow(10,i,2019))%2019
    else:
        r[i] = r[i-1] + (int(S[ls-i-1])*pow(10,i,2019))%2019
        r[i] %= 2019
#print(r)
from collections import Counter
c = Counter(r)

#print(c)
ans = 0
c[0] += 1
for k,v in c.items():
    # if k == 0:
    #     pass
    if v >= 2:
        ans += v*(v-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

S = input()
N = len(S)
dp = [0 for _ in range(N+1)]

MOD = 2019

dp[-1] = int(S[-1])
tmp = 10
for i in range(N-1, 0, -1):
    m = int(S[i-1])
    dp[i] = (dp[i+1]+tmp*m)%MOD
    tmp = tmp*10%MOD

d = defaultdict(int)

for i in range(N+1):
    d[dp[i]] += 1

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

print(ans)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
n = len(s)
t = []
for i in range(n):
    t.append(int(s[i])*pow(10,n-i-1,2019))
t = list(accumulate(t))
u = [i % 2019 for i in t]
u = list(Counter(u).items())
ans = 0
for i,j in u:
    if i == 0:
        ans += j
    if j >= 2:
        ans += j*(j-1) // 2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
s = input()
n = len(s)
p = 2019
sur1 = [int(s[0]) % p]
sur2 = [int(s[-1]) % p]
sur10 = [1 % p]
for i in range(n - 1):
    sur1 += [(sur1[i] * 10 + int(s[i + 1])) % p]
    sur10 += [(sur10[i] * 10) % p]
    sur2 += [(sur2[i] + sur10[i + 1] * int(s[-i - 2])) % p]

ans = 0
d = defaultdict(int)
for x in sur2:
    d[x] += 1

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

Submission status: Accepted

Solution code:
s=input()
a=0
now=1
l=[0]*2019
for i in list(s)[::-1]:
    a=(a+now*int(i))%2019
    l[a]+=1

    now*=10
    now%=2019
ans=0
for i in l:
    ans+=(i-1)*i//2
print(ans+l[0])

Submission status: Accepted

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

digitssum = [0] * n

for i, c in enumerate(s):
    digitssum[i] = int(c) * pow(10, n-i-1, 2019)

for i in range(1, n):
    digitssum[i] += digitssum[i-1]
    digitssum[i] %= 2019

counter = [0] * 2019
counter[0] = 1

for d in digitssum:
    counter[d] += 1

print(sum((counter[i] * (counter[i]-1) // 2) for i in range(2019)))

Submission status: Accepted

Solution code:
s = input()
MOD = 2019

dp = [0] * MOD
dq = [0] * MOD
ans = 0

for i in range(len(s)):
    tmp = int(s[i])
    if i % 2 == 0:
        for val in range(MOD):
            dp[((val * 10) + tmp) % MOD] += dq[val]
            dq[val] = 0
        dp[tmp] += 1
        ans += dp[0]

    else:
        for val in range(MOD):
            dq[((val * 10) + tmp) % MOD] += dp[val]
            dp[val] = 0
        dq[tmp] += 1
        ans += dq[0] 
    
print(ans)

Submission status: Accepted

Solution code:
def main():
    *s, = map(int, input())  # <= 2*10**5

    r = [0] * 2019
    r[0] = 1

    ans = 0

    t = 0
    p = 1
    for x in reversed(s):
        t = (t + x * p) % 2019
        p = (p * 10) % 2019
        ans += r[t]
        r[t] += 1

    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Accepted

Solution code:
from collections import Counter

S = input()
N = len(S)

M = []
cum = [0]

ans = 0

for i in range(N):
    M.append(pow(10, i, 2019) * int(S[-1 - i]) % 2019)

for i in range(N):
    cum.append((cum[-1] + M[i]) % 2019)

C = Counter(cum)

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

print(ans)

Submission status: Accepted

Solution code:
S = input()
from collections import defaultdict
d = defaultdict(lambda:0)
N = len(S)
s = 0
p = [1]*N
for i in range(N):
    p[i] = p[i-1]*10%2019

for i in range(N-1,-1,-1):
    s += int(S[i])*(p[N-1-i])
    s %= 2019
    d[s] += 1
ans = 0
for k in d:
    n = d[k]
    ans += (n*(n-1))//2
ans += d[0]
print(ans)