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: Time Limit Exceeded

Solution code:
s = input()

def naive(s):
	cnt = 0
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			k = int(s[i:j])
			if k % 2019 == 0 and k != 0:
				#print(i, j)
				cnt += 1
	return cnt

def main(s):
	nums = [(int(s[len(s) - i - 1]) * (10 ** i)) % 2019 for i in range(len(s))]
	cnt = 0
	for i in range(len(nums)):
		k = nums[i]
		if k == 0:
			cnt += 1
		for j in range(i + 1, len(nums)):
				k = (k + nums[j]) % 2019
				if k == 0:
					cnt += 1
	return cnt

print(main(s))

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
mojisu = len(S)
num = 0
for i in range(mojisu):
    for j in range(i, mojisu):
        if j-i+1<4:
            continue
        taisho = int(S[i:j+1])
        if taisho % 2019 == 0:
            num += 1
print(num)

Submission status: Time Limit Exceeded

Solution code:
s = input()
cnt = 0
for i in range(len(s)):
	for j in range(i + 1, len(s) + 1):
		k = int(s[i:j])
		if k % 2019 == 0 and k != 0:
			#print(i, j)
			cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
mojisu = len(S)
num = 0
for i in range(mojisu):
    for j in range(i, mojisu):
        mojisu2 = j-i+1
        taisho = int(S[i:j+1])
        if taisho % 2019 == 0:
            num += 1
print(num)

Submission status: Time Limit Exceeded

Solution code:
S = input()[::-1]
Surpus = [0] * 2019
Surpus[0] = 1

sum = 0
x = 1
for i in S:
    sum += int(i) * x
    Surpus[sum % 2019] += 1
    x *= 10

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def comb(S, div=2019):
    result = set()
    i = 0
    for i in range(len(S)):
        for j in range(len(S[i:])):
            s = int(S[i:i+j+1])
            if s % div == 0:
                result.add((i+1,i+j+1))
            j += 1

    return result


def main():
    S = input()

    pairs = comb(S)

    print(len(pairs))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
mods = [0]*2019
mods[0] = 1
s = input()
u = 1
t = 0
for i in range(1,len(s)+1):
    k = len(s) - i
    t = (t + int(s[k])*u)%2019
    u *= 10 % 2019
    mods[t] += 1


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)/2
print(int(cnt))

Submission status: Time Limit Exceeded

Solution code:
mods = [0]*2019
mods[0] = 1
s = input()
u = 1
t = 0
for i in range(1,len(s)+1):
    k = len(s) - i
    t = (t + int(s[k])*u)%2019
    u *= 10 % 2019
    mods[t] += 1


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)//2
print(cnt)

Submission status: Time Limit Exceeded

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


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)//2
print(cnt)

Submission status: Time Limit Exceeded

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


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)//2
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def isMultipleOf2019(s):
    return 0 == int(s) % 2019


def cal(s):
    if s not in memo:
        memo[s] = isMultipleOf2019(s)
    return memo[s]


# def inMemo(s):
#     return s in ok


def main():
    S = input().strip()
    count = 0
    for j in range(len(S)+1):
        for i in range(j-3):
            count += 1 if cal(S[i:j]) else 0
            # count += 1 if isMultipleOf2019(S[i:j]) else 0
    print(count)


if __name__ == "__main__":
    memo = {'2019': True}
    # ok = (str(2019 * i) for i in range(10**5))
    # print(len(str(2019 * 10**200000)))
    main()
    # print(memo)

Submission status: Time Limit Exceeded

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


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)//2
print(cnt)

Submission status: Time Limit Exceeded

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


cnt = 0
for x in mods:
    if x >= 2:
        cnt += x*(x-1)//2
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import collections
s = input()
dp = [0 for i in range(len(s)+1)]
for i in range(1,len(s)+1):
    k = len(s) - i
    dp[i] = (dp[i-1] + int(s[k])*(pow(10,i-1)))%2019

count_d = collections.defaultdict(int)
for mod in dp:
    count_d[mod] += 1

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

Submission status: Time Limit Exceeded

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

count_d = collections.defaultdict(int)
for mod in dp:
    count_d[mod] += 1

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

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
mojisu = len(S)
num = 0
for i in range(mojisu):
    for j in range(i, mojisu):
        mojisu2 = j-i+1
        taisho = 0
        for l in range(mojisu2):
            taisho += int(S[i+l]) * (10**(mojisu2-l-1))
        if taisho % 2019 == 0:
            num += 1
print(num)

Submission status: Time Limit Exceeded

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

S = list(input())
del S[-1]
Surpus = [-1 for i in range(2019)]
Surpus[0] = 0

T = 0
for count, i in enumerate(S):
    T += int(S[-1 - count]) * (10 ** count)
    Surpus[T % 2019] += 1

ans = 0
for i in Surpus:
    ans += int(i * (i + 1) / 2)

print(ans)

Submission status: Time Limit Exceeded

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

S = int(input())
S_Len = len(str(S))
Surpus = [-1 for i in range(2019)]
Surpus[0] = 0

for i in range(1,S_Len + 1):
    x = S % (10 ** i)
    Surpus[x % 2019] += 1


ans = 0
for i in Surpus:
    ans += int(i * (i + 1) / 2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
string = str(input())
     
pairs = 0
limit = len(string)-4
secondLimit = len(string)
substring = ''
for i in range(limit):
  substring += string[i]
  for j in range(i+1,secondLimit):
    substring += string[j]
    if j-i > 3 and int(substring) % 673 == 0:
      pairs += 1
  substring = ''
print(pairs)

Submission status: Time Limit Exceeded

Solution code:
s = input()

i = 0
ct = 0
while i < len(s):
  j = i + 4
  while j <= len(s):
    n = int(s[i:j])
    if n >= 2019 and n % 2019 == 0:
        ct += 1
    j += 1
  i += 1
print(ct)

Submission status: Time Limit Exceeded

Solution code:
def isMultipleOf2019(s):
    return 0 == int(s) % 2019


def main():
    S = input().strip()
    count = 0
    for j in range(len(S)+1):
        for i in range(j-3):
            count += 1 if isMultipleOf2019(S[i:j]) else 0
    print(count)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def isMultipleOf2019(s):
    return 0 == int(s) % 2019


def main():
    S = input().strip()
    count = 0
    for j in range(len(S)+1):
        for i in range(j-2):
            count += 1 if isMultipleOf2019(S[i:j]) else 0
    print(count)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
S = str(input())
dp = [0]*len(S)#dp[i]がTiのmod2019の値（インデックスで見る)
dp[-1]=float('inf')
dp[len(S)-2] = int(S[-1])
for i in range(len(S)-2,0,-1):
    dp[i-1] = (dp[i] + int(S[i])*(10**(len(S)-1-i)))%2019
dp.insert(0,int(S)%2019)#0番目以降までで0番目を含んだのが上の定義ではない
ans = 0

for ii,i in enumerate(dp):
    if i==0:
        ans += 1
    for j in dp[ii+1:]:
        if (i==j) :
            ans += 1
if int(S)==1:
    print(0)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

s = int(stdin.readline().rstrip())
sl = len(str(s))
li = [[i,j] for i in range(sl -3) for j in range(i + 3, sl) if s % (10 ** (sl - i)) // (10 ** (sl - j - 1)) % 2019 == 0]

print(len(li))

Submission status: Time Limit Exceeded

Solution code:
S = list(input())
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = [0] * 2019
indices = []
k = 10
for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        # sub = int(S[N - i] + str(sub))
        sub += int(S[N - i]) * k
        k *= 10
    rest = sub % 2019
    counter[rest] += 1

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = [0] * 2019
indices = []
k = 10
for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        # sub = int(S[N - i] + str(sub))
        sub += int(S[N - i]) * k
        k *= 10
    rest = sub % 2019
    counter[rest] += 1

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

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = [0] * 2019
indices = []

for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        # sub = int(S[N - i] + str(sub))
        sub += int(S[N - i]) * 10 ** (i-1)
    rest = sub % 2019
    counter[rest] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

II = input_int

def map_int_input():
    return map(int, input())

MII = map_int_input

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

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

S = input()
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = [0] * 2019
indices = []

for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        # sub = int(S[N - i] + str(sub))
        sub += int(S[N - i]) * 10 ** (i-1)
    rest = sub % 2019
    counter[rest] += 1

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

Submission status: Time Limit Exceeded

Solution code:
s = str(input())
count = 0
for i in range(len(s)-3):
  for j in range(i+3,len(s)):
    if (int(s[i:j+1])%2019) == 0:
      count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

II = input_int

def map_int_input():
    return map(int, input())

MII = map_int_input

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

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

S = input()
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = [0] * 2019

for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        sub = int(S[N - i] + str(sub))
    rest = sub % 2019
    counter[rest] += 1
    # if rest in counter:  # dict を使い検索することで，O(N)の余剰
    #     counter[rest] += 1
    # else:
    #     counter[rest] = 1


# def combinations_count(n, r):
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

Submission status: Time Limit Exceeded

Solution code:
S = int(input())
n = len(str(S))
dp = [0]*2019
dp[0] = 1
for i in range(1,n+1):
    X = S%10**i
    dp[X % 2019] += 1
answer = 0
for i in range(2019):
    answer += dp[i]*(dp[i]-1)/2
print(int(answer))

Submission status: Time Limit Exceeded

Solution code:
import math

def P(n):
  return math.factorial(n) // (math.factorial(n - 2) * math.factorial(2))

N = input()
a = 0
#N2 = [int(N[-1 * _]) for _ in range(1, len(N) + 1)] #各桁ずつ取り出し
N3 = [0 for i in range(len(N))] #i番目には(i + 1)桁目までの数字の2019の剰余が保存
for i in range(len(N)):
  num = int(N[len(N) - i -1:])
  N3[i] = num % 2019

l = 0
for i in range(len(N)):
  if N3[i] == -1:
    continue
  if N3[i] == 0:
    l += 1
  else:
    k = 1
    for j in range(i + 1, len(N)):
      if N3[i] == N3[j]:
        N3[j] = -1
        k += 1
    if k >= 2:
      l += int(P(k))
print(l)

Submission status: Time Limit Exceeded

Solution code:
S = int(input())
n = len(str(S))
dp = [0]*2019
dp[0] = 1
D = {}
for i in range(1,n+1):
    X = S%10**i
    dp[X % 2019] += 1
answer = 0
for i in range(2019):
    answer += dp[i]*(dp[i]-1)/2
print(int(answer))

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
ans = 0
for i in range(N-3):
    for j in range(i+3, N):
        if int(S[i:j+1]) % 2019 == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

II = input_int

def map_int_input():
    return map(int, input())

MII = map_int_input

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

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

S = input()
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる(dp)

counter = dict()

for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N-1])
    else:
        sub = int(S[N - i] + str(sub))
    rest = sub % 2019
    if rest in counter:
        counter[rest] += 1
    else:
        counter[rest] = 1

# def combinations_count(n, r):
#     return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 0
for r in counter.values():
    ans += r*(r-1)/2
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

II = input_int

def map_int_input():
    return map(int, input())

MII = map_int_input

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

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

S = input()
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = dict()

for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N-1])
    else:
        sub = int(S[N - i] + str(sub))
    rest = sub % 2019
    if rest in counter:
        counter[rest] += 1
    else:
        counter[rest] = 1

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 0
for r in counter.values():
    if r >= 2:
        ans += combinations_count(r, 2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

II = input_int

def map_int_input():
    return map(int, input())

MII = map_int_input

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

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

S = input()
N = len(S)
# N 文字の文字列 S から、長さ N+1 の累積和 s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = dict()

for i in range(N + 1):
    sub = int(S[N - i:]) if S[N - i:] else 0
    rest = sub % 2019
    if rest in counter:
        counter[rest] += 1
    else:
        counter[rest] = 1

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 0
for r in counter.values():
    if r >= 2:
        ans += combinations_count(r, 2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
s = str(stdin.readline().rstrip())

ans = 0

for i in range(len(s)-1):
    for j in range(i+1,len(s)+1):
        num = int(s[i:j])
        if num % 2019 == 0:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

II = input_int

def map_int_input():
    return map(int, input())

MII = map_int_input

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

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

S = input()
N = len(S)
# N 文字の文字列 S から、長さ N+1 の累積和 s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

subs = [int(S[N - i:]) if S[N - i:] else 0 for i in range(N + 1)]
counter = dict()
for num in subs:
    rest = num % 2019
    if rest in counter:
        counter[rest] += 1
    else:
        counter[rest] = 1

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 0
for r in counter.values():
    if r >= 2:
        ans += combinations_count(r, 2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

II = input_int

def map_int_input():
    return map(int, input())

MII = map_int_input

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

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

S = input()
N = len(S)
# N 文字の文字列 S から、長さ N+1 の累積和 s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

subs = [int(S[N - i:]) if S[N - i:] else 0 for i in range(N + 1)]
counter = dict()
for i in range(2019):
    counter[i] = 0

for num in subs:
    counter[num % 2019] += 1

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 0
for r in counter.values():
    if r >= 2:
        ans += combinations_count(r, 2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def count_multi(s, d):
  a = np.array([int(c) for c in s])  # .astype(np.int)
  m = a
  keta = 1
  count = np.count_nonzero(m == 0)
  while len(m) > 1:
    m = (m[:-1]*10 + a[keta:]) % d
    keta += 1
    count += np.count_nonzero(m == 0)
  return count
        
print(count_multi(input().strip(), 2019))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

s = stdin.readline().rstrip()
sl = len(s)
li = [[i, j] for i in range(sl - 3) for j in range(i+4, sl+1) if int(s[i:j]) % 2019 == 0]

print(len(li))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def count_multi(s, d):
  a = np.array([int(c) for c in s])  # .astype(np.int)
  m = a  # % d
  keta = 1
  count = np.count_nonzero(m == 0)
  while len(m) > 1:
    m = (10*m[:-1] + a[keta:]) % d
    keta += 1
    count += np.count_nonzero(m == 0)
  return count
        
print(count_multi(input(), 2019))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def count_multi(s, d):
  a = np.array([c for c in s]).astype(np.int)
  m = a % d
  keta = 1
  count = np.count_nonzero(m == 0)
  while len(m) > 1:
    m = (10*m[:-1] + a[keta:]) % d
    keta += 1
    count += np.count_nonzero(m == 0)
  return count
        
print(count_multi(input().strip(), 2019))

Submission status: Time Limit Exceeded

Solution code:
N = input()
num = len(N)
mod_sum = [0]*2019
mod_sum[0] = 1
ans = 0
a = 0
for i in range(num):
  a += (int(N[-i-1])*10**i)%2019
  mod = a%2019
  mod_sum[mod] += 1
for i in mod_sum:
  ans += i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = input()
num = len(N)
mod_sum = [0]*2019
mod_sum[0] = 1
ans = 0
a = 0
for i in range(num):
  a += int(N[-i-1])*10**i
  mod = a%2019
  mod_sum[mod] += 1
for i in mod_sum:
  ans += i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

s = stdin.readline().rstrip()
cnt = 0

for i in range(len(s) - 1):
    for j in range(i + 3, len(s)):

        num = int(s[i:j+1])
        if num >= 2019 and num % 2019 == 0:
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = input()
num = len(N)
mod_sum = [0 for i in range(2019)]
ans = 0
for i in range(num):
  a = int(N[i:])
  mod = a%2019
  mod_sum[mod] += 1
  if mod == 0:
    ans += 1
for i in mod_sum:
  ans += i*(i-1)//2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = input()
num = len(N)
mod_sum = [0 for i in range(2019)]
ans = 0
for i in range(num):
  a = int(N[i:])
  mod = a%2019
  mod_sum[mod] += 1
  if mod == 0:
    ans += 1
for i in mod_sum:
  ans += i*(i-1)/2
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
# D - Multiple of 2019

s = input()

# pow[k] = 10 ** k % 2019
pow = [1]
while len(pow) <= 1 or pow[-1] > 1:
    pow.append(pow[-1] * 10 % 2019)
n = len(pow) - 1  # 10 ** n == 1 mod 2019

# memo[i % n][m] = (int(s[:i+1]) % 2019 == mであるiの個数)
memo = [{} for i in range(n)]
memo[n - 1][0] = 1  # memo[-1][0] = 1

count = 0  # int(s[i:j+1]) == 0 mod 2019 である(i,j)の個数
mod = 0
for j, c in enumerate(s):
    mod = (mod * 10 + int(c)) % 2019  # mod = int(s[:j+1]) % 2019
    for i in range(1, n + 1):
        m = mod * pow[n - i] % 2019  # m == mod * 10 ** (-i) mod 2019
        if m in memo[(j - i + n) % n]:
            count += memo[(j - i + n) % n][m]
    if mod not in memo[j % n]:
        memo[j % n][mod] = 0
    memo[j % n][mod] += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import math

val = int(input())
count = 0
length = math.floor(math.log10(val)) + 1

while val >= 2019:
  i = 4
  while length  - i >= 0:
    if (val // (10 ** (length - i))) % 2019 == 0:
      count += 1
      i += 4
    else:
      i += 1

  val %= 10 ** (length - 1)
  length -= 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import math

val = int(input())
count = 0

while val >= 2019:
  i = 4
  length = math.floor(math.log10(val)) + 1
  while length  - i >= 0:
    if (val // (10 ** (length - i))) % 2019 == 0:
      count += 1
      i += 4
    else:
      i += 1

  val %= 10 ** (length - 1)

print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

a = np.array([int(c) for c in input().strip()])
m = a % 2019
keta = 1
count = np.count_nonzero(m == 0)
while len(m) > 1:
  m = (10*m[:-1] + a[keta:]) % 2019
  keta += 1
  count += np.count_nonzero(m == 0)
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def count_multi(s, d):
  a = np.array([int(c) for c in s])
  m = a % d
  keta = 1
  count = np.count_nonzero(m == 0)
  while len(m) > 1:
    m = (10*m[:-1] + a[keta:]) % d
    keta += 1
    count += np.count_nonzero(m == 0)
  return count
        
print(count_multi(input(), 2019))

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
S = ''.join(list(reversed(S)))
A = [0]*N
B = [0]*(N+1)
list = [0]*2019
sum = 0

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

B[0] = 0
j = 1
for j in range(N+1):
    B[j] = (B[j-1]+A[j-1])%2019


for l in range(N+1):
    list[B[l]] +=1

for m in range(2019):
    num = list[m]
    sum = sum + num*(num-1)//2

print(int(sum))

Submission status: Time Limit Exceeded

Solution code:
import collections

n = input()
l = [int(x) for x in list(n)]

leng = len(l)
liste = []
S = 0
x = 0
for i in range(leng):
  x += l[leng-i-1]*pow(10,i)
 # print(x)
  a = x % 2019
  if a==0:
    S+=1
  liste.append(a)
#print(liste)

c = collections.Counter(liste)
m = list(c.values())
m2 = map(lambda x: x - 1, m)
S += int(sum(m2))
print(S)

Submission status: Time Limit Exceeded

Solution code:
S = input()

n = len(S)
x = [0,]*2019
m = [0,]*(n+1)
for i in range(n, -1, -1):
    # T(i) = T(i+1) + a(i)*10^
    # >> T(n)   = 0
    # >> T(n-1) = 0 + 6*10^0 = 6
    # >> T(n-2) = 6 + 4*10^1 = 46
    if i == n:
        c = 0
        y = 0   # c%2019
    else:
        s = S[i]
        a = int(s)
        b = int(a*10**(n-i-1))

        y = (m[i+1] + b%2019)%2019

    x[y] += 1
    m[i] = y

m = list(map(lambda x: x*(x-1)/2, x))
print(int(sum(m)))

Submission status: Time Limit Exceeded

Solution code:
import collections

n = input()
l = [int(x) for x in list(n)]

leng = len(l)
liste = []
sum = 0
x = 0
for i in range(leng):
  x += l[leng-i-1]*pow(10,i)
 # print(x)
  a = x % 2019
  if a==0:
    sum+=1
  liste.append(a)
#print(liste)

c = collections.Counter(liste)
m = list(c.values())

for i in range(len(m)):
  if m[i] != 1:
    sum += (m[i]-1)
print(sum)

Submission status: Time Limit Exceeded

Solution code:
S = input()

n = len(S)
m = [0,]*2019
m[0] = 1
for i in range(n):
    s = S[i:]
    a = int(s)
    m[a%2019] += 1

m = list(map(lambda x: x*(x-1)/2, m))
print(int(sum(m)))

Submission status: Time Limit Exceeded

Solution code:
s = list(input())
n = 0
cnt = 0
for i in range(len(s)):
    n+=1
    s[i] = int(s[i]) * 10**(len(s)-n)
for i in range(len(s)):
    c = 0
    for j in range(len(s)-int(i)):
        c += s[j+i]
        if c%2019 == 0:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def baisuu(s):
    return not (int(s) % 2019)

def main():
    s = input()
    l = len(s)
    ans = 0
    for i in range(l):
        for j in range(i + 1, l + 1):
            if baisuu(s[i:j]):
                ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
strS = input()
S = int(strS)
lenS = len(strS)
 
ans = 0
for i in range(lenS - 3):
    for j in range(i+3, lenS):
#        print(i,j)
        if int(strS[i:j+1])%2019 == 0:
#            print(int(str(S)[i:j]), i, j)
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
strS = input()
S = int(strS)
lenS = len(strS)
 
ans = 0
for i in range(lenS):
    if i+3 <= lenS:
        for j in range(i+3, lenS):
#            print(i,j)
            if int(strS[i:j+1])%2019 == 0:
#                print(int(str(S)[i:j]), i, j)
                ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S = int(input())
lenS = len(str(S))

ans = 0
for i in range(lenS):
    if i+3 <= lenS:
        for j in range(i+3, lenS):
            if int(str(S)[i:j+1])%2019 == 0:
                ans += 1
print(ans)