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 math
import queue
import copy
import bisect#2分探索
from collections import deque #popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

ss = input()
#N, K = map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=lambda x:x[1],reverse=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入

#ss=str(S)
# #print(ss)
ls=len(ss)
# l=[0]*(ls+1)

    #print(l[i])
#print(l)

# #優先度付きqueue

kl=[0]*2019
kl[0]=1
# a = [0]
# heapq.heapify(a)  # aを優先度付きキューに

tmp=0
t2=1
count=0
for s in reversed(ss):
    tmp=(tmp+int(s)*pow(10,count,2019))%2019#ここを単純にint(s[i:sl-1])%2019とか、%10**i%2019すると、TLEになる！！！DPで求めなければならない
    kl[tmp]+=1
    #t2=t2*10%2019
    count+=1
    #print(tmp)

#print(a)




ans=0
for k in kl:
    ans+=k*(k-1)//2
print(ans)

# cur=-1
# ans=0
# for i, li in enumerate(l):
#     if cur==-1:
#         cur=li
#         count=1
#     elif li==cur:
#         count+=1
#     else:
#         ans+=count*(count-1)//2
#         cur=li
#         count=1

# print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple


def solve(s: str) -> int:
    modulo = 2019
    remainders = defaultdict(int, {0: 1})
    power = 1
    curr = 0
    LOG.debug((s))
    for i in range(len(s) - 1, -1, -1):
        c = int(s[i])
        curr = (power * int(c) + curr) % modulo
        power = (power * 10) % modulo
        remainders[curr] += 1
    result = 0
    for i in remainders.values():
        result += i * (i - 1) // 2
    LOG.debug((remainders))
    return result


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    S = input()
    # values = list(map(int, input().split()))
    # values = []
    # for _ in range(N):
    #     values.append(input().split())
    result = solve(S)
    print(result)


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result))


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque,defaultdict
import sys
sys.setrecursionlimit(10**7)

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

s = input()
X = list(map(int, list(s)))
n = len(s)

ruiseki = [0] * (n+1)
for i in (range(n-1, -1, -1)):
    ruiseki[i] = (X[i] * pow(10, (n-i-1), 2019) + ruiseki[i+1]) % 2019

# log(ruiseki)

ans = 0
count = defaultdict(int)

for x in ruiseki:
    # log(count[x])
    ans += count[x]
    count[x] += 1
# log(count)
print(ans)

Submission status: Accepted

Solution code:
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

S = input()
N = len(S)

h = 2019
dp = [0]*h

ans = 0
for i in range(1, N+1):
    nextDp = [0]*h
    now = int(S[i-1])

    nextDp[now] += 1
    for k in range(h):
        n = (k * 10 + now) % h
        nextDp[n] += dp[k]

    ans += nextDp[0]
    dp = nextDp

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 20:57:47 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 2019

S = input()
l = len(S)
#S = int(S)

a, b = [],[0]
s = 0
xx = [0 for _ in range(2019)]
xx[0] += 1
for i in range(l):
    s += int(S[-i-1])*pow(10,i,mod)
    s %= mod
#    b.append(s % x)
    xx[s] += 1

ans = 0
#for i in range(len(b)):
#    xx[b[i]] += 1
def a(n):
    return n*(n+1)//2 

for i in range(len(xx)):
    if xx[i] > 1:
        ans += a(xx[i] - 1)

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

S = list(input())
n = len(S)

dp = [0] * 2019
dp[0] = 1
tmp = 0
ten = 1
for i in range(n):
    tmp += int(S[n-1-i]) * ten
    tmp %= 2019
    ten *= 10
    ten %= 2019
    dp[tmp%2019] += 1
# print(dp)

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

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

s=input()
len_s=len(s)
lst=[0]
dic=defaultdict(int)
dic[0]=1
ten=1
for i in range(len_s):
    lst.append((lst[i]+int(s[-i-1])*pow(10,i,2019))%2019)
    # ten=ten*10%2019
    dic[lst[-1]]+=1
# print(lst)
# print(dic)
ans=0
for i in dic.values():
    ans+=i*(i-1)//2
print(ans)

Submission status: Accepted

Solution code:
S = input()
 
mods = [0 for _ in range(2019)]
mods[0] = 1
t = 0
mod10 = 1
for s in reversed(S):
    t += int(s) * mod10
    t = t % 2019
    mod10 *= 10
    mod10 %= 2019
    mods[t] += 1

cnt = sum([m*(m-1)/2 for m in mods])
print(int(cnt))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.buffer.readline

def main():
    S = input()
    P = 2019

    ans,base = 0,1
    MOD_list = 0
    d = {}
    d[0] = 1

    for st in S[::-1]:
        num = int(st)
        MOD_list = (MOD_list+num*base)%P
        if MOD_list not in d:
            d[MOD_list] = 1
        else:
            d[MOD_list] += 1
        base *= 10
        base %= P

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
s = input()
length = len(s)
count_dict = {}

'''for i in range(length-4):
    for j in range(i+4,length+1):
        num = int(s[i:j])
        if num%2019 == 0:
            count += 1'''

num = int(s)%2019
count_dict[num] = 1

# num = int(s[-1])
# count_dict[num] = 1

for i in range(1,length):
    num = (num-int(s[-i])*pow(10,(i-1),2019))%2019
    # num = num+int(s[-i])
    if num not in count_dict:
        count_dict[num] = 1
    else:
        count_dict[num] += 1


count = 0
for k,v in count_dict.items():
    count += v*(v-1)/2
    if k == 0:
        count += v

print(int(count))

Submission status: Accepted

Solution code:
import numpy as np
#S = list(input().strip())
#length = len(S)
#op = np.asarray(S)

def solution():
    S = input()
    N = len(S)
    num = [0] * 2019
    num[0] = 1
    c, ans, dgt = 0, 0, 1
    for i in reversed(range(N)):
        c = (c + int(S[i]) * dgt) % 2019
        dgt *= 10
        dgt %= 2019
        ans += num[c]
        num[c] += 1
        
    print(ans)

solution()



def sample():
    x = -1
    count = 0
    for i in op:
        x += 1
        group = ""
        for j, name in enumerate(op, x):
            group += name
            if int(group) % 2019 == 0:
                count += 1
    print(count)

def checkValue():
    count = 0
    for i in range(length):
        group = ""
        for j in range(i, length):
            group += op[j]
            if int(group) % 2019 == 0:
                count += 1
    print(count)
#checkValue()

Submission status: Accepted

Solution code:
from collections import Counter
s = input()
a = [0]
mod = 2019
for i,j in enumerate(s[::-1]):
    a.append(a[-1]+int(j)*pow(10,i,mod))
    a[-1] %= mod
b = Counter(a)
ans = 0
for i in b.values():
    ans += i*(i-1)//2
print(ans)

Submission status: Accepted

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


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

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

num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import Counter

s = readline().rstrip().decode()[::-1]
m = 0
d = 1
memo = [0]
for check in s:
    m += int(check) * d
    m %= 2019
    d *= 10
    d %= 2019
    memo.append(m)
counter = Counter(memo)
ans = 0
for i in range(2020):
    ans += counter[i] * (counter[i] - 1) // 2
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
S = input()
N = len(S)

DP=[0]*(N+1)
for i,s in enumerate(reversed(S)):
    DP[i+1]=(DP[i]+pow(10,i,2019)*int(s))%2019

D=defaultdict(int)
for dp in DP:
    D[dp]+=1

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

print(ans)

Submission status: Accepted

Solution code:
import sys


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


def main():
    S = list(input())
    N = len(S)
    check = [0] * 2019
    ten = 1
    mod = 1
    check[mod] += 1
    for i in range(N):
        mod = (mod + int(S[N - i - 1]) * ten) % 2019
        ten = (ten * 10) % 2019
        check[mod] += 1
    answer = 0
    for i in range(2019):
        answer += ((check[i] - 1) * check[i]) // 2
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
S = list(map(int, list(input())))
N = len(S)

dp = [0]*N
if N < 4:
    print(0)
    exit(0)

ans = 0

D = [0]*N
D[0] = 1
for i in range(1, N):
    D[i] = D[i-1]*10 % 2019
t = collections.defaultdict(int)
tmp = 0

t[0] += 1
for i in range(N):
    tmp += S[N-1-i]*D[i]
    tmp %= 2019
    t[tmp] += 1

for x in t:
    ans += t[x]*(t[x]-1) // 2

# print(N)
# print(*dp, sep='\n')

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
#S = list(input().strip())
#length = len(S)
#op = np.asarray(S)

def solution():
    S = input()
    N = len(S)
    num = [0] * 2019
    num[0] = 1
    c, ans, dgt = 0, 0, 1
    for i in range(N-1, -1, -1):
        c = (c + int(S[i]) * dgt) % 2019
        dgt *= 10
        dgt %= 2019
        ans += num[c]
        num[c] += 1
        
    print(ans)

solution()



def sample():
    x = -1
    count = 0
    for i in op:
        x += 1
        group = ""
        for j, name in enumerate(op, x):
            group += name
            if int(group) % 2019 == 0:
                count += 1
    print(count)

def checkValue():
    count = 0
    for i in range(length):
        group = ""
        for j in range(i, length):
            group += op[j]
            if int(group) % 2019 == 0:
                count += 1
    print(count)
#checkValue()

Submission status: Accepted

Solution code:
def main():

    S = input()
    d = dict()
    d[0] = 1
    v = 0
    p = 1
    for i in range(len(S)):
        v = v + int(S[len(S)-i-1]) * p
        v %= 2019
        d[v] = d.get(v, 0) + 1
        p *= 10
        p %= 2019

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


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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    S = list(input())
    N = len(S)
    
    d = defaultdict(int)
    d[0] = 1
    ans = 0
    tmp = 0
    for i in range(N):
        si = int(S[N - 1 - i])
        tmp = (tmp + si * pow(10, i, 2019)) % 2019
        ans += d[tmp]
        d[tmp] += 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math
import collections


S = input()


N = len(S)
P = 2019
ans = 0
juu = 1
S = S[::-1]
amari = 0
amaris = [0] * (P) #あまりの配列
if P == 2 or P == 5:
    for i,c in enumerate(S):
        n = int(c)
        if n % P == 0:
            ans += N - i
else:


    for c in S:
        i = int(c)
        amari += (i * juu)
        amari %= P
        amaris[amari] += 1
        juu *= 10
        juu %= P


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

Submission status: Accepted

Solution code:
from collections import Counter

S = input()

ans = 0
mod_list = [0] * len(S)
mod_list[-1] = int(S[-1])
m = 1
for i in range(2, len(S) + 1):
    m = (10 * m) % 2019
    mod_list[-i] = (mod_list[-i + 1] + (int(S[-i]) * m)) % 2019

mod_counter = Counter(mod_list)
mod_counter[0] += 1

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

print(ans)

Submission status: Accepted

Solution code:
S = input()
n = len(S)
res = 0
cur = 0
count = [0] * 2020
for i, c in enumerate(map(int, S)):
    cur = (cur * 10 + c) % 2019
    if cur == 0:
        res += 1
    temp = (cur * pow(10, (n - i), 2019)) % 2019
    res += count[temp]
    count[temp] += 1
print(res)

Submission status: Accepted

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

def main():
    S = input()
    P = 2019

    ans,base = 0,1
    MOD_list = [0]

    for st in S[::-1]:
        num = int(st)
        MOD = (MOD_list[-1]+num*base)%P
        MOD_list.append(MOD)
        base *= 10
        base %= P

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import Counter
    P = 2019
    S = [int(s) for s in input()]
    N = len(S)
    ans = 0
    if P == 5 or P == 2:
        for i, s in enumerate(S, start=1):
            if s % P == 0:
                ans += i
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1], start=1):
            # print(i, s)
            acc[i] = (s * d + acc[i-1]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
S=list(map(int,input()))
P=2019
N=len(S)
if P not in [2,5]:
  pt = [1]
  for i in range(N):
    pt.append(pt[-1]*10%P)
  dp = [(S[0]*pt[N-1])%P]
  for i in range(1,N):
    dp.append((dp[-1]+S[i]*pt[N-1-i])%P)

  c = Counter(dp)
  ans = sum(u*(u-1)//2 for u in c.values())
  print(ans+c[0])
elif P==2:
  S = [int(c) for c in input()]
  ans = 0
  for i in range(N):
    if S[i]%2==0:
      ans += i+1
  print(ans)
else:
  ans = 0
  S = [int(c) for c in input()]
  for i in range(N):
    if S[i]%5==0:
      ans += i+1
  print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read
s = input()
res = [0]*2019
res[0] = 1
t = 1
now = 0
for i in s[::-1]:
    i = int(i)
    now += i*t
    now %= 2019
    res[now] += 1
    t = t*10%2019
 
ans = 0    
for i in res:
    ans += i*(i-1)//2
 
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import queue
import copy
import bisect#2分探索
from collections import deque #popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])

#mod = 10**9+7

ss = input()
#N, K = map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [inputl() for i in range(H)]
#q = queue.Queue() #q.put(i) #q.get() 
#q = queue.LifoQueue() #q.put(i) #q.get() 

#a= [[0]*3 for i in range(5)] #2次元配列はこう準備、[[0]*3]*5だとだめ
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#w.sort(key=lambda x:x[1],reverse=True)  #二個目の要素で降順並び替え

#素数リスト
# n = 100
# primes = set(range(2, n+1))
# for i in range(2, int(n**0.5+1)):
#     primes.difference_update(range(i*2, n+1, i))
# primes=list(primes)

#bisect.bisect_left(a, 4)#aはソート済みである必要あり。aの中から4未満の位置を返す。rightだと以下
#bisect.insort_left(a, 4)#挿入

#ss=str(S)
# #print(ss)
ls=len(ss)
# l=[0]*(ls+1)

    #print(l[i])
#print(l)

# #優先度付きqueue

kl=[0]*2019
kl[0]=1
# a = [0]
# heapq.heapify(a)  # aを優先度付きキューに

tmp=0
t2=1
for s in reversed(ss):
    tmp=(tmp+int(s)*t2)%2019
    kl[tmp]+=1
    t2=t2*10%2019
    #print(tmp)

#print(a)




ans=0
for k in kl:
    ans+=k*(k-1)//2
print(ans)

# cur=-1
# ans=0
# for i, li in enumerate(l):
#     if cur==-1:
#         cur=li
#         count=1
#     elif li==cur:
#         count+=1
#     else:
#         ans+=count*(count-1)//2
#         cur=li
#         count=1

# print(ans)

Submission status: Accepted

Solution code:
S = list(input())
n = len(S)
res = 0
cur = 0
count = [0] * 2020
count[0] = 1
for i, c in enumerate(map(int, S)):
    cur = (cur * 10 + c) % 2019
    temp = (cur * pow(10, (n - i), 2019)) % 2019
    count[temp] += 1
print(sum(c * (c - 1) // 2 for c in count))

Submission status: Accepted

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

ans = 0
cnt = [0] * 2019
a = 1
s = 0

for i in range(N)[::-1]:
    s = int(S[i]) * a + s
    a *= 10
    a = a % 2019
    cnt[s % 2019] += 1
    s = s % 2019

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

Submission status: Accepted

Solution code:
# coding: utf-8

S = input()
P = 2019
N = len(S)
num = [0] * P
num[0] = 1
c = 0
ans = 0
dgt = 1
for i in range(N-1, -1, -1):
    c = (c + int(S[i]) * dgt) % P
    dgt *= 10
    dgt %= P
    ans += num[c]
    num[c] += 1
 
print(ans)

Submission status: Accepted

Solution code:
def main():
    S = list( map( int, list( input())))
    N = len(S)
    A = [0]*2019
    Q = 2019
    now = 0
    A[0] = 1
    for i in range(N-1,-1,-1):
        now = (S[i]*pow(10,N-1-i,Q)+now)%Q
        A[now] += 1

    ans = 0
    for a in A:
        ans += a*(a-1)//2
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

    mod1 = []
    for i in reversed(range(lens)):

        mod1.append((int(s[i]) * pow(10, lens-i-1, 2019))%2019)
    mod2 = {}
    sums = 0
    for i in range(lens):
        sums += int(mod1[i])
        sums %= 2019
        if sums in mod2:
            mod2[sums] += 1
        else:
            mod2[sums] = 1
    if 0 in mod2:
        mod2[0] +=1

    keys = list(mod2.keys())
    ans = 0
    for i in range(len(mod2)):
        if mod2[keys[i]] >1:
            test = mod2[keys[i]]
            ans += test*(test-1)//2
    print(ans)
resolve()

Submission status: Accepted

Solution code:

S = input()
lenS = len(S)
rui = [0] * 2019
rui[0] = 1
tmp = 1
m = 0
for i in range(lenS):
    m += int(S[-i - 1]) * tmp
    m %= 2019
    tmp *= 10
    tmp %= 2019
    rui[m] += 1

ans = 0
for i in rui:
    if i >= 2:
        ans += (i * (i - 1) // 2)

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


mod = 2019
S = map(int, reversed(input()))

mods = [0]
num = 0
digit = 1
for s in S:
    num += s * digit
    num %= mod
    mods.append(num)
    digit = digit * 10 % mod

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

Submission status: Accepted

Solution code:
from collections import Counter

s = input()
mod1 = 673
mod2 = 3

num1 = 0
num2 = 0
li1 = []
li2 = []
pw1 = 10
pw2 = 10
for i, e in enumerate(s, 1):
    num1 *= 10
    num1 += int(e)
    num1 %= mod1
    inv = pow(pw1, mod1 - 2, mod1)
    li1.append(num1 * inv % mod1)

    num2 *= 10
    num2 += int(e)
    num2 %= mod2
    inv = pow(pw2, mod2 - 2, mod2)
    li2.append(num2 * inv % mod2)

    pw1 *= 10
    pw1 %= mod1
    pw2 *= 10
    pw2 %= mod2

li = [0] + [10 * e1 + e2 for e1, e2 in zip(li1, li2)]
c = Counter(li)

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

print(ans)

Submission status: Accepted

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

def main():
    S = list(input())
    S.pop()
    m = 2019
    div_list = [0]*m
    num = 0
    for i, l in enumerate(reversed(S)):
        num += pow(10, i, m)*int(l)
        div_list[num%m] += 1

    div_list[0] += 1
    ans = 0
    for item in div_list:
        ans += int(item*(item-1)/2)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
S = list(input())
n = len(S)
cur = 0
count = [0] * 2020
count[0] = 1
for i, c in enumerate(map(int, S[::-1])):
    cur = (cur + c * pow(10, i, 2019)) % 2019
    count[cur] += 1
    
print(sum(c * (c - 1) // 2 for c in count))

Submission status: Accepted

Solution code:
S = input()
count = 0
l = [0]*2019
l[0] = 1
mod = 2019
tmp = 0

for i in range(1,len(S)+1):
    tmp = (tmp + int(S[len(S)-i])*pow(10,i-1,mod))%mod
    l[tmp] += 1
    

for j in range(2019):
    if l[j] >= 2:
        count += l[j]*(l[j]-1)//2

print(count)

Submission status: Accepted

Solution code:


def solve():

    s = input()
    mod = 2019
    remains = [0]*mod

    ans = 0
    now = 0
    remains[0] = 1
    for i, val in enumerate(s[::-1]):
        now += int(val) * pow(10, i, mod)
        now %= mod
        ans += remains[now]
        remains[now] += 1

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
S=input()
P=2019

mod_table=[0]*P
mod_table[0]=1

modp=0
mod10=1
for i in reversed(range(len(S))):
  si=int(S[i])
  modp=(si*mod10+modp)%P
  mod_table[modp]+=1
  mod10=(mod10*10)%P
  
answer=0
for m in mod_table:
  answer+=m*(m-1)//2
  
print(answer)

Submission status: Accepted

Solution code:
import numpy as np
s = list(map(int,input()))
n = len(s)
ans = 0
mod = 2019
past = s[n-1]
ima = 0
d = dict()
d[s[n-1]] = 1
now = 10
for i in range(1,n):
    ima = (past+s[n-i-1]*now)%mod
    if ima == 0:
        ans += 1
    if ima in d:
        d[ima] += 1
    else:
        d[ima] = 1
    past = ima
    now = (now*10)%mod

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

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
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:
import sys
sys.setrecursionlimit(10**9)


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

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

num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1

print(ans)

Submission status: Accepted

Solution code:
S = str(input())
s = len(S)
cnt = 0
A = [0]*2019
r = 0
for i in range(s):
  x = (r+pow(10, i, 2019)*int(S[s-i-1]))%2019
  A[x] += 1
  r = x
  
for i in range(1,2019):
  if A[i] >= 2:
    cnt += A[i]*(A[i]-1)//2
cnt += A[0]*(A[0]+1)//2

print(cnt)

Submission status: Accepted

Solution code:
P=2019
S = input()
N=len(S)
count=[0]*P
ans = 0
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:
from collections import defaultdict


s = input()[::-1]
cntr = defaultdict(int)
cntr[0] += 1
tens = 1
n = 0
for c in s:
    n += tens * int(c) % 2019
    n %= 2019
    cntr[n] += 1
    tens = tens * 10 % 2019

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

Submission status: Accepted

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

s = readline().rstrip().decode('utf-8')
n = len(s)
m = 2019
lst1 = [0]*len(s)
res = ""
for i in range(n):
    res = int(str(res)+s[i])
    res %= m
    lst1[i] = res
 
ans = 0
 
if m == 2 or m == 5:
    for i in range(n):
        if lst1[i] == 0:
            ans += i+1
 
 
else:
    s = s[::-1]
    dig = 1
    lst1 = [0]*n
    for i in range(n):
        if i == 0:
          lst1[i] = int(s[i])%m
          continue
          
        dig *= 10
        dig %= m
        lst1[i] = lst1[i-1] + dig*int(s[i])
        lst1[i] %= m
    c = Counter(lst1)
    #zero sum range
    for i in c.values():
        #余りがその値だった時の個数iについて、割った値が0になる状態数はi*(i-1)//2
        ans += i*(i-1)//2
    ans += c[0]#割った余りが0の時はもちろん条件を満たす
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    S=readline().strip()
    li=[0]*2019
    n=int(S[-1])%2019
    m=1
    for i in range(len(S)):
        if i==0:
            pass
        else:
            m*=10
            m%=2019
            l=int(S[len(S)-i-1])
            n+=m*l
            n%=2019
        li[n]+=1

    res=li[0]
    for i in range(2019):
        res+=li[i]*(li[i]-1)//2
    print(res)
    
if __name__=="__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
s = input()[::-1]
l = len(s)
x = [0 for _ in range(2019)]
x[0] += 1
k = 0
p = 1
for si in s:
    k += int(si) * p % 2019
    k %= 2019
    x[k] += 1
    p *= 10
    p %= 2019
 
ans = 0
for xi in x:
    ans += max(0, xi * (xi - 1) // 2)
print(ans)

Submission status: Accepted

Solution code:
s = input()[::-1]
l = len(s)
x = [0 for _ in range(2019)]
x[0] += 1
k = 0
p = 1
for si in s:
    k += int(si) * p % 2019
    k %= 2019
    x[k] += 1
    p *= 10
    p %= 2019

ans = 0
for xi in x:
    ans += max(0, xi * (xi - 1) // 2)
print(ans)

Submission status: Accepted

Solution code:

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

for i in range(len(S)):
    s[i]=int(S[i])
CHECK=[0 for i in range(2021)]
ans=0
temp=0
for i in range(1,len(s)+1):
    #print(s[-i])
    temp=(temp+s[-i]*pow(10,i-1,2019)+2019*2)%2019
    #print(i,temp)
    #print(temp)
    CHECK[temp]+=1
for i in CHECK:
    ans+=i*(i-1)//2

ans+=CHECK[0]
 
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

s = list(input())
n = len(s)-1

res = 0

d = dict()
mod = 2019
d[0] = 1

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

print(res)

Submission status: Accepted

Solution code:
from collections import Counter

S = input()

p = 2019
N = len(S)

# p は 10 と互いに素なのであんまり桁のずれは関係ないはずなので、とりあえず位は大きいのに合わせる
m = [(int(S[i]) * pow(10, N-i, p)) % p for i in range(N)]# m は各桁の mod

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

# この r[i] が一致するような区間が答えになるのでこれをもとめる（0は別途対応）
c = Counter(r)

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

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

print(ans)