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(map(int, list(input())))

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

while S:
    s = S.pop()

    pops = (pops + s * digi) % 2019
    digi = (10 * digi) % 2019

    cnt[pops] += 1

ans = 0

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

print(ans)

Submission status: Accepted

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

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

D = dict()
for j in L:
    if j in D:
        D[j] += 1
    else:
        D[j] = 1
ans = 0
for k in D.values():
    ans += k * (k-1) //2

print(ans)

Submission status: Accepted

Solution code:
S = input()

mod = 2019
cnt = [0] * 2019
cur = 0  # 現在検討中の部分文字列
cnt[cur] = 1
d = 1   # 桁

for s in S[::-1]:
    cur += int(s) * d
    cur %= mod
    cnt[cur] += 1
    d *= 10
    d %= mod

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

print(ans)

Submission status: Accepted

Solution code:
S=[int(i) for i in list(input())][::-1]
R={}
def dic_add(x):
    if x in R:
        R[x]+=1
    else:
        R[x]=1
def dic_check(x):
    if x in R:
        return R[x]
    else:
        return 0
def pow_k(x,n,p=10**9+7):
    if n==0:
        return 1
    K=1
    while n>1:
        if n%2!=0:
            K=(K*x)%p
        x=(x*x)%p
        n//=2
    return (K*x)%p
N=len(S)
r=0
res=0
for i in range(N):
    r=(S[i]*pow_k(10,i,2019)+r)%2019
    if not r:
        res+=1
    res+=dic_check(r)
    dic_add(r)
print(res)

Submission status: Accepted

Solution code:
s = str(input())
MOD = 2019
m = 0
digit = 1
mods = [1] + [0] * 2018
for a in s[::-1]:
    m = (m + digit * int(a)) % MOD
    mods[m] += 1
    digit = digit * 10 % MOD
ans = 0
for x in mods:
    ans += x * (x - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import defaultdict
def main():
    S_ = S()
    mod_list = defaultdict(int)
    ans = 0
    num = 0
    point = 1
    for i in S_[::-1]:
        num += int(i) * point
        mod = int(num) % 2019
        mod_list[mod] += 1
        point *= 10
        point %= 2019
    values_ = mod_list.values()
    ans += mod_list[0]
    for value in values_:
        ans += (value - 1) * value // 2

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
h = collections.Counter([0])
cumul,m,ans = 0,2019,0
pt = 1
for j,u in enumerate(map(int,list(raw_input()))[::-1]):
	cumul += u * pt
	cumul %= m
	pt *= 10
	pt %= m
	ans += h[cumul]
	h[cumul]+=1
print ans

Submission status: Accepted

Solution code:
def inN():
    return int(input())
def inL():
    return list(map(int,input().split()))
def inNL(n):
    return [list(map(int,input().split())) for i in range(n)]

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

cnt += mod[0]

for i in range(2019):
    if mod[i] > 1:
        cnt += (mod[i]*(mod[i]-1))/2
        #print(i)
print(int(cnt))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    s = tuple(map(int, input()))
    lens = len(s)

    d1 = defaultdict(int)
    ss = 0
    num10 = 1
    for se in s[::-1]:
        ss += (int(se) * num10) % 2019
        ss = ss % 2019
        d1[ss] += 1
        num10 = (num10 * 10) % 2019
    r = d1[0]
    for v in d1.values():
        r += v * (v - 1) // 2
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    s = tuple(map(int, input()))
    lens = len(s)

    d1 = defaultdict(int)
    ss = 0
    num10 = 1
    for i1 in range(1, lens+1):
        ss += (int(s[-i1]) * num10) % 2019
        ss = ss % 2019
        d1[ss] += 1
        num10 = (num10 * 10) % 2019
    r = d1[0]
    for v in d1.values():
        r += v * (v - 1) // 2
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    s = tuple(map(int, input()))
    lens = len(s)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import numpy as np
from collections import Counter

YEAR = 2019


def solve(S: str):
    # S の各桁を modYear 計に修正する
    mod_year = np.arange(1, 10)
    mod_s = []
    for Si in map(int, reversed(S)):
        mod_s.append(mod_year[Si - 1])
        mod_year = (mod_year * 10) % YEAR
    # print(mod_s)
    # mod_s を累積和にする
    cum_sum = 0
    cum_sums = [cum_sum]
    for x in mod_s:
        cum_sum = (cum_sum + x) % YEAR
        cum_sums.append(cum_sum)

    # 場合分けの数を足し合わせる
    answer = 0
    for _, num in Counter(cum_sums).items():
        answer += (num * (num - 1)) // 2  # 1 の時0なので場合分けはいらない
    return answer


def main():
    S = input().strip()
    answer = solve(S)
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

import numpy as np
from collections import Counter

YEAR = 2019


def solve(S: str):
    # S の各桁を modYear 計に修正する
    mod_year = np.arange(1, 10)
    mod_s = []
    for Si in map(int, reversed(S)):
        mod_s.append(mod_year[Si - 1])
        mod_year = (mod_year * 10) % YEAR
    #print(mod_s)
    # mod_s を累積和にする
    cum_sum = 0
    cum_sums = [cum_sum]
    for x in mod_s:
        cum_sum = (cum_sum+x) % YEAR
        cum_sums.append(cum_sum)

    answer = 0
    for _, num in Counter(cum_sums).items():
        answer += (num * (num-1)) // 2   # 1 の時0なので場合分けはいらない
    return answer


def main():
    S = input().strip()
    answer = solve(S)
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
S = input()
N = len(S)
A = [int(S[i]) for i in range(N)]
A = A[::-1]

MOD = 2019

p10 = [1] * N
for i in range(1, N):
	p10[i] = (p10[i - 1] * 10) % MOD

for i in range(N):
	A[i] = (A[i] * p10[i]) % MOD

cumsum = [A[0]] * N
for i in range(1, N):
	cumsum[i] = (cumsum[i - 1] + A[i]) % MOD

cnt = [0] * MOD
cnt[0] = 1
for i in range(N):
	cnt[cumsum[i]] += 1

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Sep  7 00:38:11 2020

@author: liang
"""

"""
＜D - Multiple of 2019>
【方針】
a = b(mod2019) => a - b は　2019の倍数
余りが等しいグループの組み合わせの総数が解になる。
既に2019の倍数であるものは単体で成立するため、[0]のカウントを一つあげておく


＜累積和＞
【計算量削減】
大きな数を使わない　⇒　mod を使う
tmp += 7 * 100000000  => 7 * ( 2019*N + α) => 7 * α　と同じ
　　⇒　累乗(10**N) に  mod をかけると良い

100000000 + γ => (2019*N + β) + γ => β + γ と同じ
　⇒　累積和　に　mod をかけると良い
 
 for文で１文字ずつ足し算していくことで実装可能
 
 reversed() : 逆順に並べ替え
 reversed(input()) : 入力を逆順に取り出す
 
"""
S = input()

MOD = 2019 

counter = [0] * 2019
counter[0] = 1
t = 1
tmp = 0
for i in reversed(S):
    tmp += int(i)*t
    tmp %= MOD #累積和を効率化
    t *= 10
    t %= MOD   #累乗を効率化 
    #print(tmp)
    counter[tmp] += 1

ans = sum( i*(i-1)//2 for i in counter)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def combinations_count(n, r):
    if n == 1:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def main():
    S = SI()
    
    ls = []
    len_S = len(S)
    rem = 0

    for s in range(len_S-1,-1,-1):
        rem = (rem+int(S[s])* pow(10, len_S-s-1, 2019))%2019
        ls.append(rem)
    
    import collections

    cls = collections.Counter(ls)
    clsv= list(cls.values())

    ans = 0

    for p in clsv:
        ans += combinations_count(p,2)
    ans += cls[0]
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Sep  6 23:39:24 2020

@author: liang
"""
#from scipy.special import comb

counter = [0]*2019
counter[0] = 1 # 0 = 0 (mod 2019)

S = input()
tmp = 0
"""
#大きい数を一気に掛けない
for i in range(1,len(S)+1):
    tmp += int(S[-i])*10**(i-1)    #スライスの方が早い（けど、漸化式的に累積和を出せ）
    #print(tmp%2019)
    tmp %= 2019                    #大きい数を割るな
    counter[tmp%2019] += 1

ans = 0
for i in range(2019):
    if counter[i] >= 2:
        #ans += comb(counter[i], 2, exact=True)
        ans += counter[i]*(counter[i]-1)//2
print(ans)
"""
MOD = 2019
#reversed(s) ?
t = 1
for i in range(1,len(S)+1):
    tmp += int(S[-i])*t
    #print("A", tmp)
    tmp %= MOD 
    t *= 10
    #print("B", tmp)
    t %= MOD
    #print(tmp)
    counter[tmp] += 1
    
print(sum(i*(i-1)//2 for i in counter))

Submission status: Accepted

Solution code:
s = input()
n = len(s)
dp = [0 for _ in range(n)]
dp[-1] = int(s[-1])
cnt_dic = {}
tmp = 1
ans = 0
cnt_dic[0] = 1
cnt_dic[dp[-1]] = 1
for i in range(n-2, -1, -1):
    dp[i] = (dp[i+1] + int(s[i]) * pow(10, n-i-1, 2019)) % 2019
    if not dp[i] in cnt_dic:
        cnt_dic[dp[i]] = 0
    ans += cnt_dic[dp[i]]
    cnt_dic[dp[i]] += 1

print(ans)

Submission status: Accepted

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

r_list = [0] * 2019
r_list[0] = 1
num, d = 0, 1
for i in range(len(S)):
    num += d*int(s_rev[i])
    num %= 2019
    r_list[num] += 1
    d *= 10
    d %= 2019

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

print(ans)

Submission status: Accepted

Solution code:
s = input()
n = len(s)
dp = [0 for _ in range(n)]
dp[-1] = int(s[-1])
memo = 0
cnt_dic = {}
tmp = 1
ans = 0
cnt_dic[0] = 1
for i in range(n-1, -1, -1):
    memo = (memo + int(s[i]) * pow(10, n-i-1, 2019)) % 2019
    if not memo in cnt_dic:
        cnt_dic[memo] = 0
    ans += cnt_dic[memo]
    cnt_dic[memo] += 1

print(ans)

Submission status: Accepted

Solution code:
s = input()
mod = 2019
dic = [0] * mod
dic[0] += 1

tmp = 0
d = 1
for i in reversed(range(len(s))):
    tmp += int(s[i]) * d
    tmp %= mod
    d *= 10
    d %= mod
    dic[tmp] += 1

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

Submission status: Accepted

Solution code:
def main():
    def modpow(x, n, mod):
        res = 1
        while n:
            if n % 2:
                res *= x % mod
            x *= x % mod
            n >>= 1
        return res

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#https://mirucacule.hatenablog.com/entry/2020/04/27/090908
#https://drken1215.hatenablog.com/entry/2020/04/29/171300

S=str(input())[::-1]#逆順で格納
N=len(S)
counter=[0]*2019
counter[0]=1
ans=0
num,d=0,1
for c in S:
    num += int(c) * d
    num %= 2019
    d *= 10
    d %= 2019
    counter[num]+=1
for i in counter:
    ans += i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
import sys

S = input()[::-1]

c = [0] * 2019
c[0] = 1

num = 0
d = 1

for a in S:
    num += int(a) * d
    num %= 2019
    d *= 10
    d %= 2019
    c[num] += 1

a = 0
for i in c:
    a += i * (i - 1) // 2

print(a)

Submission status: Accepted

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

rest = 0
ans = 0
memo = defaultdict(int)
memo[0] = 1
for i in range(len(S)):
    rest = (rest + int(S[i])*pow(10,i,2019)) %2019
    ans += memo[rest]
    memo[rest] += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

P = Counter(P)
ans = 0
for p in P.values():
    ans += p*(p-1)//2
print(ans)

Submission status: Accepted

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

ls = len(s)
t = [0]
j = 1
for i in range(ls):
    u = (int(s[ls-1-i])*j + t[-1]) % 2019
    t.append(u)
    j = (j * 10) % 2019
c = Counter(t)
k = list(c.keys())
ans = 0
for i in k:
    ans += c[i]*(c[i]-1)/2
print(int(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict

S = input()

d = defaultdict(int)

d[0] += 1

mod = 0
R = 1
for i in range(len(S)):
    mod = (mod + R * int(S[len(S) - i - 1])) % 2019
    R = R * 10 % 2019
    d[mod] += 1
ans = 0
for i in d.values():
    if i > 1:
        ans += i * (i - 1) / 2

print(int(ans))

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353


S = input() + "0"
mod = 2019

dp = [0]
a = 1
for i in range(len(S)-1):
    dp.append((dp[-1] + int(S[len(S)-2-i])*a%mod) % mod)
    a = (a * 10) % mod

count = Counter(dp)

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

Submission status: Accepted

Solution code:
from collections import Counter


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


S = input()
div = []
s = 0
kurai = 1
for i in range(len(S) - 1, -1, -1):
    # s += int(S[i]) * ((10 ** (len(S) - 1 - i)) % 2019)
    # s %= 2019
    if i == len(S) - 1:
        s += int(S[i]) * kurai
    else:
        s += int(S[i]) * kurai
    kurai *= 10
    kurai %= 2019
    s %= 2019
    div.append(s)
div_cnt = Counter(div)
ans = div_cnt[0]
for l in div_cnt.values():
    if l >= 2:
        ans += l * (l-1) // 2
print(ans)

Submission status: Accepted

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

A=[0]
num,point=0,1
for i in n:
    num +=int(i)*point
    num %=2019
    A.append(num)
    point *=10
    point %=2019

count=Counter(A)
ans=0
for i,j in count.items():
    if j>=2:ans +=j*(j-1)//2
print(ans)

Submission status: Accepted

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

A=[]
num,point=0,1
for i in n:
    num +=int(i)*point
    num %=2019
    A.append(num)
    point *=10
    point %=2019

count=Counter(A)
ans=0
for i,j in count.items():
    if i==0:ans +=j*(j+1)//2
    else:ans +=j*(j-1)//2
print(ans)

Submission status: Accepted

Solution code:
# D - Multiple of 2019

from collections import Counter

s = input()

r = [0]
for d in map(int, s):
    r.append((r[-1] * 10 + d) % 2019)

e = 1
for i in range(len(r) - 1, -1, -1):
    r[i] = r[i] * e % 2019
    e = e * 10 % 2019

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

counter = Counter(r)
print(sum(choose2(counter[i]) for i in counter))

Submission status: Accepted

Solution code:
"""
dp的な発想で解けるかな？
下の桁から見る。桁を一つずつ
"""
from collections import defaultdict
S = input()
N = len(S)
S = S[::-1]

ans = 0
memo = defaultdict(int)
num = 0
memo[0] = 1
for i in range(N):
    num = (num+(pow(10,i,2019)*int(S[i]))%2019)%2019
    ans += memo[num]
    memo[num] += 1

print(ans)

Submission status: Accepted

Solution code:
S = input()
N = len(S)
 
counter = [0] * 2019
counter[0] = 1
T = 0
R = 1
for i in range(N):
    T = (T + R * int(S[N - i - 1])) % 2019
    R = 10 * R % 2019
    counter[T] += 1
 
ans = 0
for i in range(2019):
    m = counter[i]
    ans += m * (m - 1) // 2
 
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    S = list(input())
    rem = [0 for _ in range(2019)]
    v = 0
    rem[0] += 1
    p = 1
    for i in range(len(S)-1, -1, -1):
        v = p*int(S[i]) + v
        v %= 2019
        rem[v] += 1
        p = (p*10)%2019

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



if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
S = list(map(int, input()))
L = len(S)
mod = 2019
T = []
A = [0 for i in range(mod)]
t = 0
p = 1
for i in range(L-1, -1, -1):
  t = (t + S[i] * p) % mod
  A[t] += 1
  p = (p * 10) % mod
print(A[0] + sum([a * (a-1) // 2 for a in A]))

Submission status: Accepted

Solution code:
from collections import Counter
s=input()
n=len(s)
ans=0
arr=[0]*(n+1)
if s=='0':
    print(1)
    exit()
elif n==1:
    print(0)
    exit()
for i in reversed(range(n)):
    arr[i]=(arr[i+1]+int(s[i])*pow(10,n-i-1,2019))%2019
m=Counter(arr)
for j in m.keys():
    ans+=m[j]*(m[j]-1)//2
print(ans)

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

s = input()

@lru_cache(None)
def F(s, k):
    # sの左からk文字目以降を整数と見なしたとき、
    # 2019で割った余りを返す
    if k == len(s)-1:
        return int(s[k])
    ret = F(s, k+1) + int(s[k])*pow(10, len(s)-1-k, 2019)
    ret %= 2019
    return ret

a = [0]*2020
for i in range(len(s)):
    a[F(s, i)] += 1

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

print(ans)

Submission status: Accepted

Solution code:
import collections

s = input()

mod = 2019
n = len(s)
t = [0]*(n+1)
for i in range(1,n+1):
    t[i] = (t[i-1] + int(s[n-i]) * pow(10, i-1, mod)) % mod
c = collections.Counter(t)
num = c.values()
ans = 0
for i in num:
    ans += i*(i-1) // 2

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


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


def LI():
    return list(MI())


S = ST()

cnt = np.zeros(2019)
cnt[0] = 1
res = 0
tmp = 1
for s in S[::-1]:
    res += int(s) * tmp
    res %= 2019
    cnt[res] += 1
    tmp *= 10
    tmp %= 2019

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

print(int(ans))

Submission status: Accepted

Solution code:
#! /usr/bin/env python3
import sys
sys.setrecursionlimit(10**9)


INF=10**20
class Counter:
    def __init__(self):
        self.dict = {}

    def add(self,x):
        if x in self.dict: self.dict[x] += 1
        else: self.dict[x] = 1

    def decrement(self,x):
        self.dict[x] -= 1
        if self.dict[x] <= 0:
            del self.dict[x]

    def get_dict(self):
        return self.dict


def solve(S):
    N = len(S)

    v1 = [0] * (N+1)
    v1[0] = 0

    for i in range(N):
        v1[i+1] = v1[i] * 10 + int(S[i])
        v1[i+1] %= 2019

    counter = Counter()
    for i in range(N+1):
        u = v1[i] * pow(10,201900-i,2019) % 2019
        counter.add(u)

    
    ans = 0
    # print(counter.get_dict())
    for _,count in counter.get_dict().items():
        ans += count * (count-1) // 2
    
    print(ans)

    return

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



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
s = input()
len_s = len(s)
s_array = [int(i) for i in s]

mod = 2019
mod_array = [0]*mod

num = 0
mod_array[0] += 1
for i in range(len_s):
    num = pow(10, i, mod) * s_array[len_s - i - 1] + num
    num %= mod
    mod_array[num] += 1

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

print(int(ans))

Submission status: Accepted

Solution code:
import collections

s=list(input())
a=[0]

s.reverse()

mod=2019

mod10=1

for i in range(len(s)):
  x=int(s[i])
  y=a[-1]
  ans=(x*mod10+y)%mod
  a.append(ans)
  mod10=(mod10*10)%mod
  
ans1=0

c = collections.Counter(a)
d=list(c.values())

for r in d:
  if r>=2:
    ans1+=(r*(r-1))//2
    
print(ans1)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in S[::-1]:
  s=(s+int(i)*k)%2019
  k=(k*10)%2019
  ans+=dp[s]
  dp[s]+=1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

S=input()

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

def nC2(n):
  return n*(n-1)//2
  
ans = c[0]
for k in c.keys():
  if c[k] >= 2:
    ans += nC2(c[k])
    
print(ans)

Submission status: Accepted

Solution code:
import sys;      from decimal import Decimal
import math;     from itertools import combinations, product
import bisect;   from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

import numpy as np

def Main():
    s = read_str()
    dp = np.zeros(2019, dtype=np.int64)
    dp[0] = 1

    cur = 0
    digit = 1

    for i in reversed(s):
        cur = (cur + int(i) * digit) % 2019
        dp[cur] += 1
        digit = digit * 10 % 2019
    
    print(np.sum([x * (x - 1) // 2 for x in dp]))

if __name__ ==  '__main__':
    Main()

Submission status: Accepted

Solution code:
s=input()
n=len(s)
rui=[0]
juu=[1]
for i in range(n+5):
  juu.append(juu[-1]*10%2019)  
for i in range(n):
  rui.append((rui[-1]+int(s[n-1-i])*juu[i])%2019)
ama=[0]*2019
for i in range(len(rui)):
  ama[rui[i]]+=1
ans=0
def ui(n):
  return max(0,n*(n-1)//2)
for i in range(2019):
  ans+=ui(ama[i])
print(ans)

Submission status: Accepted

Solution code:
import sys

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

mod = 2019
S = S[::-1]

acum = [0] * (ls+1)
counter = {0: 1}
for i, s_i in enumerate(S):
    acum[i+1] = (acum[i] + int(s_i) * pow(10, i, mod)) % mod
    if acum[i+1] not in counter:
        counter[acum[i+1]] = 0
    counter[acum[i+1]] += 1
# print(counter)

# mod が同じものになっている桁の組み合わせなら2019の倍数
ans = 0
for value, count in counter.items():
    ans += count * (count - 1) // 2

print(ans)

Submission status: Accepted

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

# stmp = s[::-1]
# for i in range(len(s)):
#     for j in range(i,len(s)):
#         sint = int(stmp[i:j+1])
#         if sint % 2019 == 0: 
#             print(n-j,n-i)
#             print(sint)
#             print()


rem2019_cnts = [0]*2019
rem2019_cnts[0] = 1
curr_rem = int(s[0])
rem2019_cnts[curr_rem] = 1
curr_10_rem = 1
ans = 0
for i,si in enumerate(s[1:]):
    sint = int(si)

    next_10_rem = (curr_10_rem*10)%2019
    next_rem = (next_10_rem*sint + curr_rem)%2019

    ans += rem2019_cnts[next_rem]
    rem2019_cnts[next_rem] += 1
    
    curr_10_rem = next_10_rem
    curr_rem = next_rem
    # print(i+2, curr_rem)

print(ans)

Submission status: Accepted

Solution code:
s=input()[::-1]
n=len(s)
p=2019
S=[0 for i in range(n+1)]
ans=[0]*p

x10=1
for j, i in enumerate(s):
  S[j+1]=(S[j]+(x10*int(i)))%p
  x10*=10
  x10%=p
  ans[S[j+1]]+=1

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

Submission status: Accepted

Solution code:
S = input().strip()
N = len(S)
A = [0 for _ in range(N)]
B = [0 for _ in range(N)]
B[0] = 1
for i in range(1,N):
    B[i] = (B[i-1]*10)%2019
a = 0
for i in range(N-1,-1,-1):
    a = (int(S[i])*B[N-1-i]+a)%2019
    A[i] = a
C = {i:0 for i in range(2019)}
for i in range(N):
    C[A[i]] += 1
cnt = C[0]
for i in range(2019):
    cnt += (C[i]*(C[i]-1))//2
print(cnt)

Submission status: Accepted

Solution code:
from itertools import accumulate
from collections import Counter


def solve(n):
    return n * (n - 1) // 2


s = input()[::-1]
MOD = 2019

# 事前計算
rest = []
for i, x in enumerate(s):
    # 1, 10, 100, 1000...の剰余を順に計算し、各桁までの剰余を計算
    if i == 0:
        tmp = 1
    else:
        tmp = tmp * 10 % MOD
    rest.append(int(x) * tmp % MOD)

result = [x % MOD for x in list(accumulate(rest))]

# 0は単独で2019の倍数
zero = result.count(0)

# 他はコンビネーションの結果
c = Counter(result)
c = list(c.values())

# 足して出力
print(sum([solve(x) for x in c if x >= 2]) + zero)

Submission status: Accepted

Solution code:
s=list(map(int,list(input())))
#print(s)
#modで考える
# 2019100を
# 2019100%2019 と100%1019
#同じmodの組み合わせ

#右から見ていく

mod=[0]*2019

tmp=0
ten=1

#hoge=""

for ii in range(len(s)):
    i=len(s)-ii-1
    if ii==0:
        ten=1
    else:
        ten=(ten*10)%2019

    tmp=((tmp+s[i]*ten)%2019)
    #hoge=str(s[i])+hoge
    #print(tmp,int(hoge)%2019,hoge)
    mod[tmp]+=1

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

ans+=mod[0]

print(ans)

Submission status: Accepted

Solution code:
s=input()[::-1]
p=2019
ans=[0]*p

x10, S=1, 0
for i in s:
  S+=x10*int(i)
  S%=p
  x10*=10
  x10%=p
  ans[S]+=1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

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

ans = 0
for l in Counter(mod).values():
    ans += l * (l-1) // 2
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

S = list(map(int, list(input())))
mod = 2019
lens = len(S)
mods = [0]*lens
cum = 0
for i in range(lens):
    s = S[-i-1]
    cum += s*pow(10, i, mod)
    cum %= mod
    mods[i] = cum
mods += [0]
from collections import Counter
c = Counter(mods)

ans = 0
for num, cnt in c.most_common():
    if cnt<2:
        break
    ans += cnt*(cnt-1)//2
print(ans)

Submission status: Accepted

Solution code:
S = input()

cs = [0]
r = 1
for c in S[::-1]:
    cs.append((cs[-1] + r*int(c)) % 2019)
    r *= 10
    r %= 2019

from collections import Counter
ctr = Counter(cs)
ans = 0
for v in ctr.values():
    ans += v*(v-1)//2
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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


mod=[0]*2019
mod[0]+=1

ans=0
temp=0
p=1
for i in range(len(S)):
    temp+=S[i]*p
    p=p*10%2019
    temp%=2019
    ans+=mod[temp]
    mod[temp]+=1

print(ans)

Submission status: Accepted

Solution code:
s=list(input())
s.reverse()
mod=2019

n=[0]*len(s)
n[0]=1
cnt=[0]*len(s)
cnt[0]=int(s[0])
ans=[0]*2019
answer=0

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

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

for i in cnt:
  ans[i]+=1

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

answer+=ans[0]

print(answer)

Submission status: Accepted

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

acc_mod = [0]
for i, s in enumerate(S[::-1]):
    acc_mod.append((acc_mod[-1] + s * pow(10, i, MOD)) % MOD)

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

Submission status: Accepted

Solution code:
s=[int(x) for x in reversed(list(input()))]
n=len(s)
x=[0]*2019
dp = 0
dim = 1
for si in s:
  dp = (dp + si*dim) % 2019
  x[dp] += 1
  dim = dim * 10 % 2019
ans = x[0]
for i in range(2019):
  ans += x[i]*(x[i]-1)//2
print(ans)