Problem:


Score : 400 points

Problem Statement

Given is a string S consisting of digits from 1 through 9.

Find the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the following condition:

Condition: In base ten, the i-th through j-th characters of S form an integer that is a multiple of 2019.

Constraints

1 ≤ |S| ≤ 200000

S is a string consisting of digits from 1 through 9.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the condition.

Sample Input 1

1817181712114

Sample Output 1

3

Three pairs - (1,5), (5,9), and (9,13) - satisfy the condition.

Sample Input 2

14282668646

Sample Output 2

2

Sample Input 3

2119

Sample Output 3

0

No pairs satisfy the condition.



Sample input:
1817181712114


Sample output:
3

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

s=input()[::-1]
n=len(s)
a=[0]*2019
a[0]=1
c,d=0,1
for i in s:
    c+=int(i)*d
    c%=2019
    d*=10
    d%=2019
    a[c]+=1
ans=0
for i in a:
    ans+=i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
def main():
    P = 2019
    S = [int(s) for s in input()]
    ans = 0
    if P == 2:
        for i, v in enumerate(S, start=1):
            if v % 2 == 0:
                ans += i
    elif P == 5:
        for i, v in enumerate(S, start=1):
            if v == 0 or v == 5:
                ans += i
    else:
        cnt = [0]*P
        d = 1
        pre = 0
        cnt[pre] += 1
        for v in S[::-1]:
            v *= d
            v += pre
            v %= P
            cnt[v] += 1
            d *= 10
            d %= P
            pre = v

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
S = input()
dp = [0]*(len(S)+1)
cur = int(S[len(S)-1])
mod_10 = 1
count_num = [0]*2019
count_num[0] += 1
for i in range(len(S)):
    dp[len(S)-i-1] = cur
    count_num[cur] += 1
    mod_10 = (mod_10*10)%2019
    if i <= len(S)-2:
        cur = (cur+int(S[len(S)-i-2])*(mod_10))%2019
ans = 0
for i in range(2019):
    ans += (count_num[i]*(count_num[i]-1))//2
print(ans)

Submission status: Accepted

Solution code:
s=input()
n=len(s)
d=[0]*2019
d[0]=1
j=1
ans=0
now=0
for i in s[::-1]:
  now=(now+int(i)*j)%2019
  ans+=d[now]
  d[now]+=1
  j*=10
  j%=2019
print(ans)

Submission status: Accepted

Solution code:
s = input()

len_s = len(s)

current = 0
mod_dict = dict()
mod_dict[0] = 1
for i in range(len_s-1,-1,-1):
    c = s[i]
    current = (current+pow(10,len_s-i-1,2019)*int(c)) % 2019
    if current in mod_dict:
        mod_dict[current] += 1
    else:
        mod_dict[current] = 1

count = 0
for key in mod_dict:
    count+= (mod_dict[key]*(mod_dict[key]-1))//2

print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict
import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)
S = input()[::-1]
N = len(S)
cnt = [0]*N
tmp = 0
d = defaultdict(int)
d[0] += 1
for i in range(N):
    tmp += int(S[i])*pow(10,i,2019)
    tmp %= 2019
    d[tmp] += 1
ans = 0
for v in d.values():
    if v >= 2:
        ans += C(v,2)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
S = input()
S = S[::-1]
# 1桁のmod2019, 2桁の2019, ...
# 0桁のmod2019=0と定めると都合が良いので入れておく
l = [0]
num = 0
for i in range(len(S)):
    # 繰り返し二乗法で累乗の部分を高速化
    # 自分で書かなくてもpow()で既に実装されている
    # 一つ前のmodを利用するとPythonで通せた、それをしなくてもPyPyなら通る
    num += int(S[i]) * pow(10,i,2019)
    l.append(num % 2019)
# print(l)
ans = 0
c = Counter(l)
for v in c.values():
    ans += v*(v-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
S = input()
S = S[::-1]
# 1桁のmod2019, 2桁の2019, ...
# 0桁のmod2019=0と定めると都合が良いので入れておく
l = [0]
num = 0
for i in range(len(S)):
    # 繰り返し二乗法で累乗の部分を高速化
    # 自分で書かなくてもpow()で既に実装されている
    # 一つ前のmodを利用しても良いが、ボトルネックはクソデカ累乗（のmod計算）の方なのでそこまで意味はない
    num += int(S[i]) * pow(10,i,2019)
    l.append(num % 2019)
# print(l)
ans = 0
c = Counter(l)
for v in c.values():
    ans += v*(v-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
S = input()
S = S[::-1]
# 1桁のmod2019, 2桁の2019, ...
# 0桁のmod2019=0と定めると都合が良い
l = [0]
num = 0
for i in range(len(S)):
    num += int(S[i]) * pow(10,i,2019)
    l.append(num % 2019)
# print(l)
ans = 0
c = Counter(l)
for v in c.values():
    ans += v*(v-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

# forを逆から回して下から素直にmodを取るとTLEだった
# 累積和的な計算で高速化、やりやすくするためにreverse
S = input()[::-1]
# ex. 1817181712114 → 4112171817181
# print(S)

# 0桁目までのMODを0とすることで、
# 1桁目を含む数が2019の倍数の時に都合が良くなる
X = [0]

# 4,14,114,2114,12114,...のmod2019を計算

# pow(a,b,c)は普通にMODするより速い
# 普通にやったらTLEだった
for i, s in enumerate(S):
    X.append((X[-1] + int(s) * pow(10, i, 2019)) % 2019)
# print(X)


C = Counter(X)
# print(C)

ans = 0
# Xが同じになったところを2つ選べば題意を満たす
# v_C_2の計算
for v in C.values():
    ans += v * (v - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
MOD = 2019
S = input()[::-1]
X = [0]
for i in range(len(S)):
    X.append((X[-1]+int(S[i])*pow(10, i, MOD))%MOD)
C = Counter(X)
ans = 0
for v in C.values():
    ans += v*(v-1)//2
print(ans)

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

S=input().rstrip()
Smod2019=[0]
num = 0
deg = 0
for i in range(len(S)-1,-1,-1):
    num = (num+int(S[i])*pow(10,deg,2019))%2019
    Smod2019.append(num)
    deg += 1
Sc = collections.Counter(Smod2019)

cnt = 0
for val in Sc.values():
    cnt += val*(val-1)//2
print(cnt)

Submission status: Accepted

Solution code:
S=input()
S=list(reversed(S))

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

len_S=len(S)
x=1
tot=0
ans=0

for i in range(len(S)):
    cnt[tot]+=1
    tot+=(ord(S[i])-ord('0'))*x
    tot %= m
    ans+=cnt[tot]
    x=x*10%m

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    S = input()[::-1]

    counts = [0] * 2019
    counts[0] = 1
    res, digit = 0, 1
    for i in S:
        res += int(i) * digit
        res %= 2019
        digit *= 10
        digit %= 2019
        counts[res] += 1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

def modpow(a, n, m):
	r = 1
	while n > 0:
		if n & 1:
			r = r*a%m
		a = a*a%m
		n >>= 1
	return r

S,r = input(),0
dp = list(range(len(S)+1))
dp[-1],dp[-2] = 0,int(S[-1])

for i in range(3,len(S)+2):
	dp[-i] = (dp[-i+1] + modpow(10,i-2,2019)*int(S[-i+1])) % 2019

for x in Counter(dp).values():
	r += x*(x-1)//2
print(r)

Submission status: Accepted

Solution code:
from collections import defaultdict
S = input()
l = len(S)
d = {0:0}
mod10n = 1
for i in range(1, len(S)+1):
    s = int(S[l-i])
    d[i] = (d[i-1] + s * mod10n) %2019
    mod10n = (mod10n * 10) % 2019
count_d = defaultdict(int)
for key in d.keys():
    count_d[d[key]] += 1
counter = 0
for key in count_d.keys():
    counter += (count_d[key] * (count_d[key]-1)) //2

print(counter)

Submission status: Accepted

Solution code:
S = str(input())
N = len(S)
b = [0] * 2019
count = 0
b[0] = 1
t = 0
k = 1

if len(S) < 4:
    print(0)
else:
    t = int(S[-1])
    b[t] += 1
    for i in range(1,N):
        k = k * 10 % 2019
        t = (k * int(S[-i-1]) + t) % 2019 
        b[t] += 1

    for i in b:
        count += i*(i-1)//2

    print(count)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import Counter
def main():
    s = input()
    n = len(s)

    amari = [0] * n
    ketaamari = 1
    t = 0
    for i1 in range(n):
        t = (t + ketaamari * int(s[-i1 -1])) % 2019
        amari[-i1-1] = t
        ketaamari = (ketaamari * 10) % 2019
    amari.append(0)
    ac = Counter(amari)
    r = 0
    for v in ac.values():
        r += v * (v - 1) // 2
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
s=input()
n=len(s)
cnts=[0]*2019

cnts[0]=1
now=0
for i in range(n-1,-1,-1):
  now+=int(s[i])*pow(10,n-1-i,2019)
  now%=2019
  #print(now)
  cnts[now]+=1

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

Submission status: Accepted

Solution code:
import copy

s = list(input())

s.reverse()
n = len(s)
MOD = 2019
m = [0] * n
msum = [0] * (n+1)
cnt = [0] * (MOD)
cnt[0] = 1
t = 1
for i in range(n):
    m[i] = int(s[i]) * t % MOD
    msum[i+1] = (msum[i] + m[i]) % MOD
    cnt[msum[i+1]] += 1
    t = t * 10 % MOD

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

Submission status: Accepted

Solution code:


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


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    """
    modulos = [0]*2019
    modulos[0] = 1
    S = input()
    base = 1
    num = 0
    for c in S[::-1]:
        num = (base*int(c)+num)%2019
        base = (base*10)%2019
        modulos[num] += 1
    answer = 0
    for n in modulos:
        answer += n*(n-1)//2
    return answer


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:

from collections import defaultdict

S = input()

ctr = defaultdict(int)
ctr[0] = 1
cur = 0
n = len(S)
mod = 2019
for i in reversed(range(n)):
    cur = (cur + int(S[i]) * pow(10, n - i - 1, mod)) % mod
    ctr[cur] += 1

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

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

l = [0]*2019
z = 1
tmp = 0
for i, s in enumerate(S):
	tmp += s*z
	l[tmp%2019] += 1
	z = z*10%2019

ans = 0
for v in l:
	ans += v*(v-1)//2
ans += l[0]

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

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

l = [0]*2019
l[0] = 1

tmp = 0
z = 1

for i, s in enumerate(S):
	tmp += s*z
	z = z*10%2019
	l[tmp%2019] += 1

ans = 0
for v in l:
	ans += v*(v-1)//2

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

S = input()
n = len(S)
s = [0]
for i, x in enumerate(S):
	s.append(int(S[i])*pow(10, n-i-1, 2019)%2019)

tmp = 0
t = []
for x in s:
	tmp = (tmp+x)%2019
	t.append(tmp)

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

Submission status: Accepted

Solution code:
s=input()[::-1]
alist=[0]*2019
num1=0
num2=1/10
lens=len(s)
for i in range(lens):
  num2=int(((num2)*10)%2019)
  num1=(num1+int(s[i])*(num2))%2019
  alist[num1]+=1
alist[0]+=1
ans=0
for i in range(2019):
  ans+=alist[i]*(alist[i]-1)//2
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read


s = input()

MOD = 2019
d = [0]*MOD
d[0] = 1
r = 0
t = 1
for i in reversed(s):
    r += int(i)*t
    r %= MOD
    t *= 10
    t %= MOD
    d[r] += 1
    
print(sum(i*(i-1)//2 for i in d))

Submission status: Accepted

Solution code:
mod = 2019
# import time

a = input()
n = len(a)
x = [0] * n
# begin = time.time()
for i in range(n):
    x[n - i - 1] = int(a[i])
# print("elapsed 1 = ", time.time() - begin)

# begin = time.time()
ans = 0
cnt = [0] * mod
cnt[0] = 1
s = [0] * (n + 1)
e = 1
# print("elapsed 2 = ", time.time() - begin)

# begin = time.time()
for i in range(n):
    s[i + 1] = ((x[i] * e) % mod + s[i]) % mod
    _ = s[i + 1]
    ans += cnt[_]
    cnt[_] += 1
    e = (e * 10) % mod
# print("elapsed 3 = ", time.time() - begin)

print(ans)

Submission status: Accepted

Solution code:
s = input()

ans=0
s=s[::-1]
t=1
ketame=0
amari10=1
kosuu=[1]+[0]*2020
for i in s:
    ketame=(ketame+(int(i)*amari10)%2019)%2019
    amari10*=10
    amari10%=2019
    kosuu[ketame]+=1

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

Submission status: Accepted

Solution code:
from collections import Counter
def main():
    S = input()
    A = [0] * ((n := len(S)) + 1)
    A[1] = (a := int(S[-1])) % 2019
    for i in range(2, n + 1):
        a += pow(10, i - 1, 2019) * int(S[-i])
        A[i] = a % 2019
    c = Counter(A)
    ans = 0
    for v in c.values():
        ans += v * (v - 1) // 2
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

S = readline().rstrip()
DIV = 2019

cur = 0
from collections import defaultdict
dic = defaultdict(int)
for i in range(len(S) - 1, -1, -1):
  cur += ((int(S[i]) % DIV) * pow(10, (len(S) - 1 - i), DIV)) % DIV
  cur %= DIV
  dic[cur] += 1

ans = 0
# 0は単独でもよい
for key, val in dic.items():
  if key == 0:
    ans += val
  ans += (val * (val - 1)) // 2

print(ans)

Submission status: Accepted

Solution code:
N = str(input())
n,mods = 0,[1]+[0]*2018
d = 1
for i in reversed(N):
  n = (n+int(i)*d)%2019
  mods[n] += 1
  d = (d*10)%2019

print(sum([i*(i-1)//2 for i in mods]))

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:
s = input().rstrip()
tmp = 0
pw = 1
from collections import Counter
c = Counter()
c[0] += 1

for d in s[::-1]:
    tmp += int(d) * pw
    tmp %= 2019
    pw *= 10
    pw %= 2019
    c[tmp] += 1

print(sum([v*(v-1)//2 for v in c.values() if v > 1]))

Submission status: Accepted

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

T=[0]
for i in range(N):
    p = int(S[-1-i])
    T.append( (T[-1]+ pow(10,i,2019)*p)%2019 )
    
from collections import Counter
ans=0
U=dict(Counter(T))
for num in U:
    ans += U[num]*(U[num]-1)//2
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = list(input())
M = [0]
S = 0
K = 1
ans = 0

for i in range(len(N)):
    S += int(N[-i-1])*K
    S %= 2019

    K *= 10
    K %= 2019
    M.append(S)

P = Counter(M)
for i in range(2020):ans+=P[i]*(P[i]-1)//2
print(ans)

Submission status: Accepted

Solution code:
s = list(map(int,input()))
s.reverse()
t = len(s)
mod = 2019

arr = [0] * (t+1)
arr[-2] = s[0]
for i in range(1,t):
    arr[t-i-1] = (arr[t-i] + s[i]*pow(10,i,mod)) % mod

from collections import Counter
arr = Counter(arr)

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

print(ans)

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)
print(sum([v*(v-1)//2 for v in C.values()]))

Submission status: Accepted

Solution code:
def main():
  # S = input()[-1:0:-1]
  S = input()[::-1]
  MOD = 2019

  # dp = [0]*(len(S)+1)
  # dp[0] = 0
  dic = [0]*2019
  dic[0] = 1

  ten = 1
  pre = 0
  for i, s in enumerate(S):
    # dp[i] = (dp[i-1] + ten*int(s)) % MOD
    pre = (pre + ten*int(s)) % MOD
    dic[pre] += 1
    ten *= 10
    ten %= MOD

  sum_ = 0
  # for sup in dp:
  #   dic[sup] += 1

  for v in dic:
    sum_ += v*(v-1)//2

  print(sum_)


if(__name__ == '__main__'):
  main()

Submission status: Accepted

Solution code:
S=input()
MOD=2019
dp=[0]*MOD
dp[0]=1
r=0
t=1
for c in reversed(S):
    r+=int(c)*t
    r%=MOD
    t*=10
    t%=MOD
    dp[r]+=1
print(sum(i*(i-1)//2 for i in dp))

Submission status: Accepted

Solution code:
import sys
import collections


def resolve(in_):
    s = next(in_).strip()
    mod = 2019
    dp = [0] * (len(s) + 1)
    ch0 = ord(b'0')
    for i, b in enumerate(reversed(s), 1):
        dp[i] = (dp[i - 1] + (b - ch0) * pow(10, i, mod)) % mod

    return sum(v * (v - 1) // 2 for v in collections.Counter(dp).values())


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def solve():
    s=input().split()[0]
    cnt=[0]*2020
    cnt[0]=1
    m=0
    t=1
    for d in map(int,s[-1::-1]) :
        m=(m+d*t)%2019
        t=(t*10)%2019
        cnt[m]+=1
    return sum([ k*(k-1)//2 for k in cnt])

print(solve())

Submission status: Accepted

Solution code:
from collections import Counter
S = list(map(int, list(input())))
A = [0]
for i, s in enumerate(S[::-1]):
    A.append((A[-1] + s * pow(10, i, 2019)) % 2019)
print(sum([v * (v - 1) // 2 for v in Counter(A).values()]))

Submission status: Accepted

Solution code:
from collections import Counter

S = input()
# S = "12345"*40000
N = len(S)

l = [0]*(N+1)
for i in range(N-1, -1, -1):
    l[i] = (l[i+1] + pow(10, N-i, 2019) * int(S[i])) % 2019
    # if i%10000 == 0:
    #     print(i)

# print(list(Counter(l).values()))

r = sum(m*(m-1)//2 for m in Counter(l).values())
print(r)

Submission status: Accepted

Solution code:
def main():
    import collections

    S = input()

    mod_list = [0]

    for i in range(len(S)):
        index = len(S) - i - 1
        num = int(S[index])

        mod_list.append((mod_list[-1] + num * pow(10, i, 2019)) % 2019)

    CTR_mod_list = collections.Counter(mod_list).most_common()
    cnt = 0

    for i in range(len(CTR_mod_list)):
        n = CTR_mod_list[i][1]

        if (n == 1):
            break

        cnt += n * (n - 1) // 2

    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

# forを逆から回して下から素直にmodを取るとTLEだった
# 累積和的な計算で高速化、やりやすくするためにreverse
S = input()[::-1]
# ex. 1817181712114 → 4112171817181
# print(S)

# 0桁目までのMODを0とすることで、
# 1桁目を含む数が2019の倍数の時に都合が良くなる
X = [0]

# 4,14,114,2114,12114,...のmod2019を計算

for i, s in enumerate(S):
    X.append((X[-1] + int(s) * pow(10, i, 2019)) % 2019)
# print(X)


C = Counter(X)
# print(C)

ans = 0
# Xが同じになったところを2つ選べば題意を満たす
# v_C_2の計算
for v in C.values():
    ans += v * (v - 1) // 2

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
S = input()
S = S + '0'
mod = 2019
p = [-1] * len(S)
r = 0
d = 1
for i,s in enumerate(S[::-1]):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[i] = r

ans = 0
c = Counter(p)
for k,n in c.most_common():
  if n > 1:
    ans += n*(n-1)//2
  else:break
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in S[::-1]:
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1

#ans = 0
#c = Counter(p)
#for k,n in c.most_common()[::-1]:
#  if k > 1 and k%2 == 0:
#    ans += n
#  else:break
#print(ans)
print(sum([i*(i-1)//2 for i in p]))

Submission status: Accepted

Solution code:
from collections import Counter
S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in S[::-1]:
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1

#p.append(0)
#ans = 0
#c = Counter(p)
#for k,n in c.most_common():
#  if n > 1:
#    ans += 1
#  else:break
  
print(sum([i*(i-1)//2 for i in p]))

Submission status: Accepted

Solution code:
from collections import Counter
S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1

#p.append(0)
#ans = 0
#c = Counter(p)
#for k,n in c.most_common():
#  if n > 1:
#    ans += 1
#  else:break
  
print(sum([i*(i-1)//2 for i in p]))

Submission status: Accepted

Solution code:
S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1

print(sum([i*(i-1)//2 for i in p]))

Submission status: Accepted

Solution code:
S = input()
mod = [0 for _ in range(len(S))]
mod[0] = int(S[-1])
for i in range(1, len(S)):
    mod[i] = (mod[i - 1] + pow(10, i, 2019) * int(S[-1 - i])) % 2019
ans = 0
res = [0 for _ in range(2019)]
for i in range(len(S)):
    ans += res[mod[i]]
    res[mod[i]] += 1
print(ans + res[0])

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Summarize count of factor within list -- START --
def summarizeList(l):
  sl=sorted(l)

  a=sl[0]
  c=1
  res=[]

  for x in sl[1:]:
    if x==a:
      c+=1
    else:
      res.append([a,c])
      a=x
      c=1
  res.append([a,c])

  return res
# Summarize count of factor within list --- END ---

def main():
  s=S()
  n=len(s)
  s=s[::-1]

  rl=[0]*(n+1)
  for i,x in enumerate(s):
    rl[i+1]=(int(x)*pow(10,i,2019))%2019

  for i in range(n):
    rl[i+1]+=rl[i]
    rl[i+1]%=2019


  sl=summarizeList(rl)
  # print(sl)

  ans=0
  for x,c in sl:
    ans+=(c*(c-1))//2

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

print(ans)

Submission status: Accepted

Solution code:
s = input()

d = [0 for i in range(len(s) + 1)]
i = len(s) - 1
deg = 1
while i >= 0:
    d[i] = (int(s[i]) * deg + d[i + 1]) % 2019
    deg = (deg * 10) % 2019
    i -= 1

#print(d)

cnt = [0 for i in range(2019)]
for i in d:
    cnt[i] += 1

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

print(res)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 2019


s = readline().decode().rstrip()
s = s[::-1]
n = len(s)
d = [0] * (n)
d[0] = int(s[0]) % mod

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

d = [0] + d

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

Submission status: Accepted

Solution code:
from collections import Counter
S = input()
S = S[::-1]
N = len(S)
counter = Counter()
counter[0] = 1
prev = 0
MOD = 2019
for i in range(N):
  c = (int(S[i]) * pow(10, i, MOD) )%MOD
  prev = (prev+c)%MOD
  counter[prev] += 1

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


print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

MOD = 2019


def main(input, print):
    s = input().strip()
    ans = 0
    cnt = [0] * MOD
    k = 1
    t = 0
    # tj - ti-1 = 0 -> tj = ti-1
    cnt[0] = 1  # ti-1の値が必要なため
    for i in reversed(range(len(s))):
        t += int(s[i])*k
        t %= MOD
        ans += cnt[t]
        cnt[t] += 1
        k = k * 10 % MOD
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Accepted

Solution code:
s=input()
p=2019
ans=0
M=[0]*p
M[0]=1
tmp=0
for i in range(len(s)):
    tmp+=(int(s[-i-1])*pow(10,i,p))
    tmp%=p
    ans+=M[tmp]
    M[tmp]+=1
print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict

S = input()
n = len(S)

mod = 2019
d = defaultdict(int)
d[0] = 1
num = 0
for i in reversed(range(n)):
    num += int(S[i]) * pow(10, n - i - 1, mod)
    num %= mod
    d[num] += 1

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

Submission status: Accepted

Solution code:
#import numpy as np
#import math
#from decimal import *
#from numba import njit
from collections import Counter

#@njit
def main():
    S = input()
    A = list(map(int, S))[::-1]
    mod = []
    ten = 10
    for i in range(len(A)):
        if i == 0:
            mod += A[i],
        else:
            mod += (mod[i-1]+ten*A[i])%2019,
            ten = (ten*10)%2019
    mod += 0,

    C = Counter(mod)
    print(sum([c*(c-1)//2 for c in C.values()]))

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
S = input()[::-1]
remainder = [0] * 2019

# 2つ選ぶ組み合わせにおいて余り0の場合は1つしか選ばなくて良いので
# 2つ目に0を選んだ場合として便宜的に設定
remainder[0] = 1

num = 0
d = 1
for s in S:
  num += int(s) * d
  remainder[num % 2019] += 1
  d *= 10
  
  # numが大きくなりすぎると計算量が膨大になってしまうのを防ぐ
  # num%2019を計算するので、先に%2019で計算しても結果は変わらない
  d %= 2019
ans = 0
for i in range(2019):
  ans += remainder[i] * (remainder[i]-1) // 2
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


s = input()
n = len(s)
a = [None]*n
c = 0
v = 1
for i in range(n-1, -1, -1):
    c = (c + v*int(s[i])) % 2019
    a[i] = c
    v *= 10
    v %= 2019
from collections import Counter
cc = Counter(a)
ans = 0
for k,v in cc.items():
    ans += v*(v-1)//2
ans += cc[0]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

s = input()
n = len(s)
digits = [int(c) for c in s[::-1]]
a = [0] * (n + 1)
p = 2019

for i, digit in enumerate(digits):
    a[i + 1] = (digit * pow(10, i, p) + a[i]) % p

counter = Counter(a)
ans = 0
for count in counter.values():
    ans += count * (count - 1) // 2

print(ans)

Submission status: Accepted

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

S = input().strip()
#-----
num = 0
cnt_mod = {0:1}  # type {int: int} , contents {remainder : count}
mod = 2019
base_pow = 1

for i in range(len(S)):
    digit = int( S[len(S)-1-i] )
    
    num += (digit * base_pow) % mod
    num %= mod
    
    base_pow = (base_pow * 10) % mod
    
    cnt_mod.setdefault(num, 0)
    cnt_mod[num] += 1


ans = 0

for r,c in cnt_mod.items():
    # r: remainder
    # c: count
    if c >= 2:
        ans += c*(c-1)//2

print(ans)

Submission status: Accepted

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

t = [0]*n
dp = [0]*2020
t[0] = int(s[-1])
dp[t[0]] += 1
for i in range(n-1):
    t[i+1] = t[i] + int(s[-2-i])*pow(10, i+1, mod)
    t[i+1] %= mod
    dp[t[i+1]] += 1
ans = 0
for D in dp[1:]:
    ans += D*(D-1)//2
print(ans+(dp[0]+1)*(dp[0])//2)

Submission status: Accepted

Solution code:
import math
import fractions
import collections
import itertools
from collections import deque
S=input()
N=len(S)
cnt=0
l=[]
"""
cnt=0
p=10**9+7
for i in range(K,N+2):
    cnt=(cnt+((N-i+1)*i)+1)%p
    #print(((N-i+1)*i)+1)
print(cnt)
"""
amari=[0]*(N+1)
num=0
for i in range(N):
    num=num+pow(10,i,2019)*int(S[N-1-i])
    amari[i+1]=num%2019
#print(amari)
c=collections.Counter(amari)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
#for i in range(len(key)):
#    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#xprint(l)
for i in range(len(values)):
    cnt=cnt+(values[i]*(values[i]-1))//2
print(cnt)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc164/tasks/abc164_d


S = input()

res = 0

x = 0
p = 1
MOD = 2019
reminder = [0]*2019
reminder[0] = 1
for s in reversed(S):
    """ 累積和 """
    x = (int(s)*p + x)%MOD
    p = p*10%MOD
    res += reminder[x]
    reminder[x] += 1

print(res)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc164/tasks/abc164_d

import sys
input = sys.stdin.readline


S = input().rstrip()

res = 0

x = 0
p = 1
MOD = 2019
reminder = [0]*2019
reminder[0] = 1
for s in reversed(S):
    """ 累積和 """
    x += int(s)*p
    x %= MOD
    p *= 10
    p %= MOD
    res += reminder[x]
    reminder[x] += 1

print(res)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc164/tasks/abc164_d

import sys
input = sys.stdin.readline


S = input().rstrip()

res = 0

x = 0
p = 1
MOD = 2019
reminder = [0]*2019
reminder[0] = 1
for s in reversed(S):
    """ 累積和 """
    x = (int(s)*p + x)%MOD
    p = p*10%MOD
    res += reminder[x]
    reminder[x] += 1

print(res)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc164/tasks/abc164_d

import sys
input = sys.stdin.readline


S = input().rstrip()

res = 0

x = 0
p = 1
L = len(S)
MOD = 2019
reminder = [0]*2019
reminder[0] = 1
for s in reversed(S):
    """ 累積和 """
    x = (int(s)*p + x)%MOD
    p = p*10%MOD
    res += reminder[x]
    reminder[x] += 1

print(res)