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 main():
    s = input()
    mod = 2019

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

    print(sum([r * (r - 1) // 2 for r in R]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input()
res = 0
m = 1
p =[0]*2019
for i in map(int,s[::-1]):
    res +=i*m
    res %=2019
    p[res] +=1
    m *=10
    m %=2019
print(p[0]+sum([i*(i-1)//2 for i in p]))

Submission status: Accepted

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


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


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


from collections import defaultdict, deque, Counter
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys

# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *


def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1 / f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

MOD = 10 ** 9 + 7
def solve():
    MOD = 2019
    s = input().strip()
    acc = [0]
    revgen = pow(10, MOD-2, MOD)
    for c in s:
        num = int(c)
        acc.append((acc[-1] * 10 + num) % MOD)

    acc.reverse()
    mul = 1
    res = []
    for ac in acc:
        ac *= mul
        ac %= MOD
        res.append(ac)
        mul *= 10
        mul %= MOD
    res.reverse()

    # print(res)
    cnt = Counter(res)
    ans = 0
    for v in cnt.values():
        ans += v * (v - 1)
    print(ans // 2)
    # print(acc)
    # print((1817 * 100000) % MOD)
    # print((817 * 100000) % MOD)
def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
S=input()
n=len(S)
a=[0]*2019
MOD=2019
current=0
a[0]=1
for i in range(n):
  current=(current+int(S[n-1-i])*pow(10,i,MOD))%MOD
  a[current]+=1
ans=0
for i in range(2019):
  ans+=(a[i]*(a[i]-1))//2
print(ans)

Submission status: Accepted

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

dp = [[0]*2019 for _ in [0]*2]
ans = 0
for i,s in enumerate(S,1):
    s = int(s)
    i %= 2
    dpi = [0]*2019
    dpi1 = dp[1-i]
    dpi[s] += 1
    for j in range(2019):
        dpi[(j*10+s)%2019] += dpi1[j]
    dp[i] = dpi
    ans += dpi[0]

print(ans)

Submission status: Accepted

Solution code:
a = input()[::-1]
add = 0
ans = [1] + [0] * 2018
ans_int = 0
d = 1

for i in range(len(a)):
    add = (add + int(a[i]) * d) % 2019
    d = (10 * d) %2019
    ans[add] += 1

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

print(int(ans_int))

Submission status: Accepted

Solution code:
s = input()
n = len(s)
m = 2019
a = [0] * (n + 1)
b = [0] * (n + 1)
b[0] = 1
for i in range(1, n + 1):
    b[i] = b[i - 1] * 10 % m
c = [0] * m
c[0] += 1
ans = 0
for i in range(n - 1, -1, -1):
    w = (a[i + 1] + (ord(s[i]) - ord('0')) * b[n - 1 - i]) % m
    ans += c[w]
    c[w] += 1
    a[i] = w
print(ans)

Submission status: Accepted

Solution code:
S = input()
ans = {0:1}
memo = [0]
last = 1
for ind, s in enumerate(S[::-1]):
    memo.append((int(s) * last + memo[-1]) % 2019)
    last *= 10
    last %= 2019
    if(memo[-1] in ans):
        ans[memo[-1]] += 1
    else:
        ans[memo[-1]] = 1

res = 0
for key in ans.keys():
    res += ans[key]*(ans[key]-1)//2
print(res)

Submission status: Accepted

Solution code:
s = input()
s = list(reversed(s))
n = len(s)
dp1 = [0]*n
dp2 = [0]*n
counting = [0]*2019
counting[0] += 1
dp1[0] = 1
dp2[0] = int(s[0])
counting[dp2[0]] += 1
if n >= 2:
    for i in range(1,n):
        dp1[i] = (10*dp1[i-1]) % 2019
        dp2[i] = (int(s[i])*dp1[i]+dp2[i-1]) % 2019
        counting[dp2[i]] += 1
#print(counting)
sm = 0
for j in range(2019):
    sm += int(counting[j]*(counting[j]-1)/2)
print(sm)

Submission status: Accepted

Solution code:
# D - Multiple of 2019
S = input()
mod = [1]+[0]*2018
tmp = 0
seki = 1
for k in range(len(S)):
    tmp = (seki*int(S[len(S)-1-k])+tmp)%2019
    mod[tmp] += 1
    seki = (seki*10)%2019
ans = 0
for k in range(2019):
    ans += mod[k]*(mod[k]-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
S = input()[::-1]
cur = 0
mods = Counter()
mods[0] += 1
MOD = 2019
for i,d in enumerate(S):
  cur += int(d) * pow(10, i, MOD)
  mods[cur%MOD] += 1

res = 0
for k,v in mods.items():
  res += (v * (v-1) // 2)

print(res)

Submission status: Accepted

Solution code:
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
from collections import deque
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
s=input()
n=len(s)
ten=[1]
mod=2019
for i in range(n-1):
  ten.append((ten[i]*10)%mod)
modls=[0]*n
modls[n-1]=int(s[n-1])
dic=defaultdict(int)
dic[modls[n-1]]+=1
dic[0]=1
for i in range(n-2,-1,-1):
  modls[i]=int(s[i])*ten[n-1-i]+modls[i+1]
  modls[i]%=mod
  dic[modls[i]]+=1
ans=0
#print(dic)
for num in dic.values():
	ans+=num*(num-1)//2
#ans+=dic[0]
print(ans)

Submission status: Accepted

Solution code:
s=list(input())
mod=2019
mdict={}
mdict[0]=1
ans=0
tmp=0
for i in range(len(s)):
    n=s.pop()
    key=(int(n)*pow(10,i,mod)+tmp)%mod

    if key in mdict:
        mdict[key]+=1
    else:
        mdict[key]=1
    tmp=key

for var in mdict.values():
    ans+=var*(var-1)//2

print(ans)

Submission status: Accepted

Solution code:
s = input()[::-1]
counts = [0] * 2019
counts[0] = 1
digit = 1
sum = 0
for c in s:
  sum = (sum + int(c) * digit) % 2019
  digit = digit * 10 % 2019
  counts[sum] += 1
 
result = 0
for c in counts:
  result += c * (c - 1) // 2
 
print(result)

Submission status: Accepted

Solution code:
S = list(map(int, list(input())))
S.reverse()
a = [0]*len(S)
y = 2019
x = 1
t = 0
cnt = [0]*y
res = 0
for i in range(len(S)):
    cnt[t] += 1
    t += S[i]*x
    t %= y
    res += cnt[t]
    x = x*10%y
print(res)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
from collections import Counter

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    S = SI()
    l = len(S)
    T = [0] * (l+1)
    inv_S = S[::-1]
    for i, s in enumerate(inv_S):
        s = int(s)
        T[i+1] = (T[i] + s * pow(10, i, 2019)) % 2019
    C = Counter(Counter(T).values())
    ans = 0
    for n, x in C.items():
        if n == 1: continue
        ans += cmb(n, 2) * x
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
s = input()[::-1]
counts = [0] * 2019
counts[0] = 1
digit = 1
sum = 0
for c in s:
  sum = (sum + int(c) * digit) % 2019
  digit = digit * 10 % 2019
  counts[sum] += 1

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

print(result)

Submission status: Accepted

Solution code:
from collections import deque
s=input()[::-1]
l=[0]*2019
ten=1
sm=0
cnt=0
l[0]=1
for i in range(len(s)):
    sm += int(s[i])*ten
    sm %= 2019
    cnt += l[sm]
    l[sm] += 1
    ten = ten *10 %2019
print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter
MOD = 2019
S = input()
T = [0]
base = 1
for si in reversed(S):
    T += [(T[-1] + int(si) * base) % MOD]
    base = (base * 10) % MOD
ans = 0
for n, count in Counter(T).items():
    ans += count*(count-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
s  = input()[::-1]
lsts = [0] * 2019
kai = 1
cou = 0
st = 0
lsts[0] = 1
for i in s:
  st += int(i) * kai
  st %= 2019
  cou += lsts[st]
  lsts[st] += 1  
  kai = kai * 10 % 2019

print(cou)

Submission status: Accepted

Solution code:
S = input()[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1
current = 0
x = 1

for s in S:
    current = (current + x * int(s)) % 2019
    ans += mods[current % 2019]
    mods[current % 2019] += 1
    x = x * 10 % 2019

print(ans)

Submission status: Accepted

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

def main():
    S = [int(s) for s in input()]
    N = len(S)
    K = 2019

    V = [0] * (N+1)
    for i in reversed(range(N)):
        rev_i = (N-1)-i
        V[rev_i+1] = V[rev_i] + S[i] * (pow(10,rev_i+1,K))
        # print(V)

    dic = {} # value:count
    U = set()
    for v in V:
        u = v % K
        if u in U:
            dic[u] += 1
        else:
            dic[u] = 1
            U.add(u)

    ans = 0
    for u in U:
        u_count = dic[u]
        ans += u_count * (u_count-1) // 2

    # print(S)
    # print(V)
    # print(dic)
    print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

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

x = []
y = 0

while 10 ** y % 2019 not in x:
    x.append(10 ** y % 2019)
    y += 1

z = len(x)

m = [0 for i in range(2019)]
m[0] = 1
a = 0
for i in reversed(range(0, t)):
    a += x[(t-i-1) % z] * (int(s[i]) % 2019)
    a = a % 2019
    m[a] += 1

def triangle(n):
    if n > 1:
        return n * (n-1) // 2
    else:
        return 0

p = list(map(triangle, m))
# print(p)
print(sum(p))

Submission status: Accepted

Solution code:
MAX = 600000
MOD = int(1e9) + 7
fac = [0] * MAX
ifac = [0] * MAX
fac[0] = 1
for i in range(1,MAX):
    fac[i] = (fac[i-1] * i) % MOD
ifac[MAX-1] = pow(fac[MAX-1],MOD-2,MOD)
for i in reversed(range(1,MAX)):
    ifac[i-1] = (ifac[i] * i) % MOD

def combinations(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return (fac[n] * ifac[k] * ifac[n-k]) % MOD
MOD2 = 2019
s = list(input())
s.reverse()
n = len(s)
ans = 0
lis = [0] * 2020
x = 1
cnt = 0
lis[cnt] += 1
for i in s:
    cnt += int(i) * x
    cnt %= MOD2
    lis[cnt] += 1

    x *= 10
    x %= MOD2

# for i in lis:
#     if i >= 2:
#         print(i)

for i in lis:
    ans += combinations(i,2)

print(ans)

Submission status: Accepted

Solution code:
MOD = 2019
s = list(input())
s.reverse()
n = len(s)
lis = [0] * 2020
ans = 0
x = 1
tot = 0
for i in range(n):
    lis[tot] += 1
    tot += int(s[i]) * x
    tot %= MOD
    ans += lis[tot]
    x *= 10
    x %= MOD
print(ans)

Submission status: Accepted

Solution code:
S = input()
from collections import defaultdict
d = defaultdict(int)
before = 0
for i in range(1,len(S)+1):
    now = (int(S[-i])*pow(10,i,2019)+before) % 2019
    d[now] += 1
    before = now
d[0] += 1
ans = 0
for i in d.values():
    ans += i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    MOD = 2019
    s = input()
    n = len(s)
    t = [0] * (n + 1)
    # n-1,n-2,...,0
    for i in range(n - 1, -1, -1):
        t[i] = t[i + 1] + pow(10, n - i - 1, MOD) * int(s[i])
        t[i] %= MOD
    c = Counter(t)
    cnt = 0
    for v in c.values():
        cnt += v * (v - 1) // 2
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
from numba import jit
@jit(nopython=True)
def nC2(n):
    return n*(n-1)//2

def main():
    #入力
    readline=stdin.readline
    s=readline().strip()

    d=dict()
    p=1
    t=0
    for i in range(len(s)-1,-1,-1):
        n=int(s[i])
        m=(n*p+t)%2019
        t=m
        p*=10
        p%=2019
        if m not in d:
            d[m]=1
        else:
            d[m]+=1
        
    if 0 in d:
        ans=d[0]
    else:
        ans=0
    for v in d.values():
        ans+=nC2(v)
    print(ans)
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
S = input()
s = S[::-1]

cnt = [0]*2019
cnt[0] = 1
number = 0
d = 1

for i in s:
  number += int(i)*d
  cnt[number % 2019] += 1
  d *= 10
  d = d % 2019

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

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

n = input()
n = reversed(n)

x = 1
count = [0 for _ in range(2019)]
MOD = 2019
acc = 0
count[0] = 1
ans = 0

for c in n:
    a = x * int(c)
    acc += a
    acc %= MOD
    ans += count[acc]
    count[acc] += 1
    x = (x * 10) % MOD

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import Counter

def main():
    S = input()
    N = len(S)
    T = [0] * (N+1)
    
    for i in range(N-1,-1,-1):
        T[i] = (T[i+1] + int(S[i]) * pow(10,N-i,2019)) % 2019
    l = Counter(T)
    ans = 0
    for v in l.values():
        ans += v * (v-1) // 2
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from sys import stdin, stdout
s = input()
n = len(s)


if len(s) <= 3:
    print(0)
    exit()

suffix_rems = [-1]*n
suffix_rems[-1] = int(s[-1])
suffix_rems[-2] = int(s[-2:])
suffix_rems[-3] = int(s[-3:])

rems_d = dict()
rems_d[0] = 1
rems_d[int(s[-1])] = 1
rems_d[int(s[-2:])] = 1
rems_d[int(s[-3:])] = 1

special_keys = set()
for i in range(n-3)[::-1]:
    rem = (pow(10, n-i-1, 2019) * int(s[i]) + suffix_rems[i + 1])%2019

    if rem in rems_d:
        rems_d[rem] += 1
        special_keys.add(rem)
    else:
        rems_d[rem] = 1

    suffix_rems[i] = rem

ans = 0
for key in special_keys:
    t = rems_d[key]
    ans += (t*(t-1))//2

print(ans)

Submission status: Accepted

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

cnt = [0 for _ in range(2019)]
S = S[::-1]
wk = 0
cnt[0] = 1

for i in range(0,N):
  wk = (wk + int(S[i]) * pow(10,i,mod)) % mod
  #print(i,wk)
  cnt[wk] += 1
  
ans = 0
for i in range(2019):
  m = cnt[i]
  ans += m * (m-1) // 2
  
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
s=input()[::-1]
DP=[0]

num,point=0,1
for i in s:
    num +=int(i)*point
    num %=2019
    DP.append(num)
    point *=10
    point %=2019

ans=0
DP=Counter(DP)
for v,m in DP.items():
    if m>=2:
        ans +=m*(m-1)//2
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

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

# modulo 2019 で同じもの、右からApple Pen
MOD = 2019
S = sr()
remain = [0] * 2019
remain[0] = 1
answer = 0
power = 1
cur = 0
for s in S[::-1]:
    num = int(s)
    cur += num * power
    cur %= MOD
    answer += remain[cur]
    remain[cur] += 1
    power *= 10; power %= MOD

print(answer)

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    s = input()
    n = len(s)
    fac = 1
    cur = 0
    value = [0] * 2019
    value[0] += 1
    for i in range(n):
        add = int(s[n - 1 - i])
        cur = (cur + fac * add) % 2019
        fac = (fac * 10) % 2019
        value[cur] += 1
    ans = 0
    for i in range(2019):
        ans += value[i] * (value[i] - 1) // 2
        
    print(ans)

if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    S = input()

    cnt = [0]*2019
    cnt[0] = 1

    # Sの右側から1ずつ左に伸ばして、cntの対応するところに加算
    rmd = 0
    num_rate = 1
    L = len(S)
    for i in range(L):
        rmd = (int(S[L-i-1])*num_rate + rmd) % 2019
        num_rate = num_rate*10%2019
        cnt[rmd] += 1

    ans = sum([i*(i-1)//2 for i in cnt])
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def main():
    s = map(int, input()[::-1])
    mod = 2019
    counts = [0] * mod
    counts[0] = 1
    t = 0
    x = 1
    for num in s:
        t = (t + num * x) % mod
        counts[t] += 1
        x = (x * 10) % mod
    ans = 0
    for count in counts:
        if count > 1:
            ans += count * (count - 1) // 2
    print(ans)


main()

Submission status: Accepted

Solution code:
from collections import defaultdict
S=input()
D=defaultdict(int)
D[0]=1
n=0
i=0
a=[0]*len(S)
b=1
for s in S[::-1]:
  n+=int(s)*b
  a[i]=n%2019
  i+=1
  b=(b*10)%2019


for i in range(len(a)):
  D[a[i]]+=1

ans=sum([i*(i-1)//2 for i in D.values()])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

S = list(input())
S = [int(i) for i in S]
D = defaultdict(int)
mod = 2019

N = len(S)
Mlis = [0]*N
Mlis[-1] = S[-1] % mod

for i in range(N-2, -1, -1):
  Mlis[i] = (Mlis[i+1] + pow(10, N-1-i, mod) * S[i]) % mod

for i in Mlis:
  D[i] += 1

ans = D[0] + sum([i*(i-1)//2 for i in D.values()])

print(ans)

Submission status: Accepted

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

mod = 2019

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

num = 0

pow10mod = 1

for i in range(len(s)):
    num = (num + s[-(i+1)] * pow10mod) % mod
    mods[num] += 1
    pow10mod = pow10mod * 10 % mod

ans = 0

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


print(int(ans))

Submission status: Accepted

Solution code:
S = input()
ans = 0
nd = 1
mod1 = 0
listmod = [0]*2019
for i in S[::-1]:
    mod1 = (int(i)*nd + mod1)%2019
    listmod[mod1] += 1
    nd = (nd*10)%2019
for i in range(2019):
    n = listmod[i]
    if(i == 0):
        if(n == 1):
            ans += 1
        elif(n >= 2):
            ans += ((n+1)*n)//2
    else:
        if(n > 1):
            ans += ((n-1)*n)//2
print(ans)

Submission status: Accepted

Solution code:
def cal(S):
    N = len(S)
    num,cnt = 0,0
    mod = 2019
    rem_dict,rem_set = {},set()
    for i in range(N):
        num = (num + int(S[N-1-i]) * pow(10,i,mod)) % mod
        if num in rem_set:
            rem_dict[num] += 1
        else:
            rem_set.add(num)
            rem_dict[num] = 1

    if 0 in rem_set:
        output = rem_dict[0] * (rem_dict[0] + 1) // 2
    else:
        output = 0
    rem_set.discard(0)
    for rem in rem_set:
        output += rem_dict[rem] * (rem_dict[rem]-1) // 2

    return output

def main():
    S = input()

    print(cal(S))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def cal(S):
    N = len(S)
    num,cnt = 0,0
    mod = 2019
    rem = [0 for _ in range(mod)]
    for i in range(N):
        num = (num + int(S[N-1-i]) * pow(10,i,mod)) % mod
        rem[num] += 1

    output = rem[0] * (rem[0] + 1) // 2
    for i in range(1,mod):
        output += rem[i] * (rem[i]-1) // 2

    return output

def main():
    S = input()

    print(cal(S))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
S = input()[::-1]
MOD = 2019
X = [0]
for i, s in enumerate(S):
  X.append((X[-1] + int(s)*pow(10,i,MOD)) % MOD)

C = Counter(X)
res = 0
for v in C.values():
  res += v*(v-1) // 2

print(res)

Submission status: Accepted

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    s=STR()
    cnt=[0]*2019
    cnt[0]=1
    temp=0
    keta=1
    ans=0
    for i in s[::-1]:
        temp=(temp+int(i)*keta)%2019
        keta=(keta*10)%2019
        cnt[temp]+=1
    for i in cnt:
        ans+=(i*(i-1))//2
    print(ans)
    
    
if __name__ == '__main__':
    do()

Submission status: Accepted

Solution code:
import sys

S = sys.stdin.readline().strip()

N = 2019
L = len(S)
curr = 0
seen = {}
INV = 210
seen[curr] = 1
for i in range(L):
    curr = (curr * 10 + int(S[i])) % N
    t = (curr * pow(10, L-i, N)) %N
    if t not in seen: seen[t] = 0
    seen[t] += 1

res = 0
for i in range(N):
    if i not in seen: continue
    t = seen[i]
    res += t * (t-1)//2
print(res)

Submission status: Accepted

Solution code:
S = input()
MOD = 2019

digit = 1
counts = [0] * 2019
counts[0] = 1
current = 0
for s in S[::-1]:
  current = (current + int(s) * digit) % MOD
  counts[current] += 1
  digit = (digit * 10) % MOD
  
ans = 0
for c in counts:
  ans += c * (c-1) // 2
  
print(ans)

Submission status: Accepted

Solution code:
S = input()[::-1]
 
## 余りを0~2018で総数保持
counts = [0]*2019
## 0桁の余りは0
counts[0] = 1
 
num, d = 0, 1
 
for c in S:
  ## 右から~桁の数字
  num += int(c) * d
  num %= 2019
  
  ## 次の桁
  d *= 10
  d %= 2019
  
  counts[num] += 1
  
ans = 0
for cnt in counts:
  ## nC2の計算
  ans += cnt * (cnt-1) //2
  
print(ans)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    s = list(map(int,input()))[::-1]
    d = defaultdict(int)
    ans = 0
    ni = 0
    mod = 2019
    d[0] = 1
    n10 = 1
    for i in s:
        ni = (ni+i*n10)%mod
        d[ni] += 1
        n10 = (n10*10)%mod
    for i in d.values():
        ans += i*(i-1)//2
    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    s = input()
    n = len(s)
    ans = 0
    num = 0
    pow10 = 1
    d = defaultdict(int)
    d[0] = 1
    for i in reversed(range(n)):
        # pow10を10 ** (n-1-i)にしてるだけでTLEしていた
        pow10 = pow10 * 10 % 2019
        num += int(s[i]) * pow10
        mod = num % 2019
        ans += d[mod]
        d[mod] += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import numpy as np
def main():
    s = input()
    n = len(s)
    d = np.zeros(2019,np.int64)
    ans = 0
    num = 0
    pow10 = 1
    d[0] = 1
    for i in reversed(range(n)):
        pow10 = pow10 * 10 % 2019
        num += int(s[i]) * pow10
        #print(num, num % 2019, i)
        mod = num % 2019
        ans += d[mod]
        d[mod] += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
S = list(input())
N = len(S)
num = 0
cnt = [0]*2019
cnt[0] = 1
d = 1
#T[i]: i+1文字目以降を数とみなしたときの数
for i in range(N-1, -1, -1):
    num += int(S[i]) * d
    num %= 2019
    # num = (num + int(S[i]) * 10 ** (N- i -1)) % 2019
    cnt[num] += 1
    d *= 10
    d %= 2019

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

Submission status: Accepted

Solution code:
s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

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

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

print(ans) # 答えの出力

Submission status: Accepted

Solution code:
def solve(s, p=2019):
    s = s[::-1]
    memo = [0] * p
    memo[0] = 1
    ans = 0
    q = 0
    r = 1
    for c in s:
        q = (q + int(c)*r) % p
        ans += memo[q]
        r = 10*r % p
        memo[q] += 1
    return ans

s = input()
print(solve(s))

Submission status: Accepted

Solution code:
S=input()
N=len(S)
mod=[0 for i in range(2019)]
s=0
ten=1
for i in range(N-1,-1,-1): 
  s+=int(S[i])*ten
  mod2=s%2019
  mod[mod2]+=1
  ten=(ten*10)%2019
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=k*(k-1)//2+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=k*(k-1)//2
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
S=input()
N=len(S)
mod=[0 for i in range(2019)]
mod2=0
ten=1
for i in range(N-1,-1,-1): 
  s=int(S[i])*ten
  mod2+=np.mod(s,2019)
  mod2=np.mod(mod2,2019)
  mod[mod2]+=1
  ten=(ten*10)%2019
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=k*(k-1)//2+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=k*(k-1)//2
print(ans)

Submission status: Accepted

Solution code:
s = (input()[::-1]) # 入力文字列を逆順でsに格納
n = len(s)
counts = [0]*2019
counts[0]=1
b = 1
num = 0
for i in s:
    num += int(i)*b
    num %=2019
    b *=10
    b %=2019
    counts[num]+=1

# print(counts)
ans = 0
for j in counts:
    ans +=j*(j-1)/2


print(int(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict
s = input()
n = len(s)
target = 2019
res = 0
dic = defaultdict(int)
dic[0] = 1
s = s[::-1]
num, d = 0, 1
for char in s:
    num += int(char) * d
    num %= target
    d *= 10
    d %= target
    dic[num] += 1
for i in dic.values():
    res += i * (i -1) //2
print(res)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    S = input()[::-1] # 入力文字列を逆順で格納
    counts = [0] * 2019
    counts[0] = 1
    num, d = 0, 1

    for char in S:
        num = num + int(char) * d
        num = num % 2019
        d = d * 10
        d = d % 2019
        counts[num] += 1 #余りの数の番号のリストに+1していくことでカウント

    ans = 0
    for cnt in counts:
        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
L=[0]
for i in range(n):
    l=(int(s[n-1-i])*pow(10,i,MOD)+L[i])%MOD
    L.append(l)
LC=Counter(L)
r=0
for v in LC.values():
    r+=v*(v-1)//2
print(r)

Submission status: Accepted

Solution code:
s = str(input())

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

mod = [1] + [0] * 2018
ans = 0
for i in num:
    ans += mod[i]
    mod[i] += 1
print(ans)

Submission status: Accepted

Solution code:
s = str(input())

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

mod = [1] + [0] * 2018
ans = 0
for i in num:
    m = i % 2019
    ans += mod[m]
    mod[m] += 1
print(ans)

Submission status: Accepted

Solution code:
s=[int(_) for _ in input()]

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

d=0
m[d]+=1
p=1
for i in range(len(s)):
  d=(d+s[-i-1]*p)%2019
  m[d]+=1
  p=(p*10)%2019
  #print(d)


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

Submission status: Accepted

Solution code:
S = input()[::-1]

#aのMOD求めるンゴ
MOD=2019
ls_rem_a=[]
d=1
for i in range(len(S)):
  ls_rem_a.append(int(S[i])*d%MOD)
  d = d*10%MOD

#次に累積和求めるンゴ
ls_rem_s=[0]
sum=0
for i in range(len(S)):
  sum+=ls_rem_a[i]
  sum%=MOD
  ls_rem_s.append(sum)

#最後にMODが同じやつの個数を調べるンゴ
from collections import Counter
C_rem = Counter(ls_rem_s)
ans=0
for i in C_rem.keys():
  n=C_rem[i]
  ans+=n*(n-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
s=input()
n=len(s)
M=[0]
mod=2019
for i in range(n):
	m=(M[-1]+int(s[n-1-i])%mod*pow(10,i,mod))%mod
	M.append(m)
MC=Counter(M)
r=0
for v in MC.values():
	if v>1:
		r+=v*(v-1)//2
print(r)

Submission status: Accepted

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

def solve():
    MOD = 2019
    S = input()

    """解説AC"""
    # A列を作成
    As = []
    d = 1
    for moji in S[::-1]:
        a = (int(moji)*d)%MOD
        As.append(a)
        d = (d*10)%MOD

    # 累積和を作成
    ruiseki = [0]
    for i, a in enumerate(As):
        r = (ruiseki[i] + a)%MOD
        ruiseki.append(r)

    # ruiseki[i] ≡ ruiseki[j] (mod 2019) となる総数を数える
    ruiseki_dic = {}  # combinationの計算でもいける
    ans = 0
    for r in ruiseki:
        if not r in ruiseki_dic:
            ruiseki_dic[r] = 1
        else:
            ans += ruiseki_dic[r]
            ruiseki_dic[r] += 1

    print(ans)


def solve2():
    MOD = 2019
    S = input()

    """解説AC"""
    # A列を作成
    As = []
    d = 1
    for moji in S[::-1]:
        a = (int(moji)*d)%MOD
        As.append(a)
        d = (d*10)%MOD

    # 累積和を作成
    ruiseki = [0]
    for i, a in enumerate(As):
        r = (ruiseki[i] + a)%MOD
        ruiseki.append(r)

    # ruiseki[i] ≡ ruiseki[j] (mod 2019) となる総数を数える
    # combinationの計算でもいける
    ruiseki_dic = {}
    ans = 0
    for r in ruiseki:
        if not r in ruiseki_dic:
            ruiseki_dic[r] = 0
        ruiseki_dic[r] += 1

    def combination_formula(n, r):
        """nCrは、O(min(n-r, r))で実装する
        Notes:
            分子と分母がかなり大きな値になった場合、計算は遅くなるので注意
            求める値がmodをとった値でいい場合、フェルマーの小定理を使った方法が速い。
        """
        if n < r: return 0

        r = min(n-r, r)
        bunsi, bunbo = 1, 1
        for i in range(r):
            bunsi = bunsi*(n-i)
            bunbo = bunbo*(i+1)
        return bunsi//bunbo

    ans = 0
    for v in ruiseki_dic.values():
        if v < 2: continue
        ans += combination_formula(v,2)

    print(ans)


if __name__ == "__main__":
    solve2()