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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	S = input()
	S = S[:-1]
	S = S[::-1]

	dol = {}
	tmptmp = 0
	ans = 0
	kinou = 0
	for i,val in enumerate(S):
		if tmptmp == 0:
			tmptmp = 1
		else:
			tmptmp = tmptmp * 10
		tmp = (int(val) * tmptmp) % 2019
		tmp = tmp + kinou % 2019

		kinou = tmp
		#if tmp in dol:
		#	ans += 1
		#else:
	#		dol[tmp] = 1

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	S = input()
	S = S[:-1]
	S = S[::-1]

	dol = {}
	tmptmp = 0
	ans = 0
	kinou = 0
	for i,val in enumerate(S):
		#print(tmptmp)
		if tmptmp == 0:
			tmptmp = 1
		else:
			tmptmp = tmptmp * 10
		tmp = (int(val) * tmptmp) % 2019
		tmp = tmp + kinou % 2019
		#print(tmp)
		kinou = tmp
		if tmp in dol:
			ans += 1
		else:
			dol[tmp] = 1

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	S = input()
	S = S[:-1]
	S = S[::-1]
	I = [0]

	dol = {}
	tmptmp = 0
	ans = 0
	for i,val in enumerate(S):
		#print(tmptmp)
		if tmptmp == 0:
			tmptmp = 1
		else:
			tmptmp = tmptmp * 10
		tmp = ((int(val) * tmptmp) % 2019) % 2019

		if tmp in dol:
			ans += 1
		else:
			dol[i] = 1

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	S = input()
	S = S[:-1]
	S = S[::-1]
	I = [0]

	dol = {}
	tmptmp = 0
	for i,val in enumerate(S):
		#print(tmptmp)
		if tmptmp == 0:
			tmptmp = 1
		else:
			tmptmp = tmptmp * 10
		tmp = (int(val) * tmptmp) % 2019
		I.append((I[-1] + tmp) % 2019)

	#print(I)

	ans = 0
	for i in I:
		if i in dol:
			ans += 1
		else:
			dol[i] = 1

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
"""
：余りの等しい物をカウントし、その累積和
：Aの余りとBの余り(mod 2019)が等しい場合
　A-Bは2019の倍数である
：計算量を抑えるため各項と１０の指数乗は分けて計算する
：
"""

import sys
input=sys.stdin.buffer.readline
s = input()[::-1] # 入力文字列を逆順でsに格納

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

num, d = 0, 1

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

ans = 0

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

print(ans) # 答えの出力

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	S = input()
	S = S[:-1]
	S = S[::-1]
	I = [0]

	dol = {}
	tmptmp = 0
	for i,val in enumerate(S):
		#print(tmptmp)
		if tmptmp == 0:
			tmptmp = 1
		else:
			tmptmp = tmptmp * 10
		tmp = (int(val) * tmptmp) % 2019
		I.append((I[-1] + tmp) % 2019)

	#print(I)

	ans = 0
	for i in range(len(I)):
		tmp = I[i] % 2019
		if tmp in dol:
			ans += 1
		else:
			dol[tmp] = 1

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

##### 割り算の切り上げ #####
# tmp = -(-4 // 3)

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	S = input()
	S = S[:-1]
	S = S[::-1]

	dol = {}
	to = 0
	ans = 0
	for i,val in enumerate(S):
		tmp = (int(val) * 10**i) % 2019
		to = (to + tmp) % 2019
		if to in dol:
			ans += 1
		else:
			dol[to] = 1

	print(ans+1)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
S = input()[::-1]
N = len(S)
sum_of_mod = [0] * 2019
sum_of_mod[0] += 1
digit = 0
now = 0
for i in range(N):
    now = int(S[i])*(10**digit) + now
    sum_of_mod[now % 2019] += 1
    digit += 1
    digit %= 2019

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

Submission status: Wrong Answer

Solution code:
S = input()[::-1]
N = len(S)
sum_of_mod = [0] * 2019
sum_of_mod[0] += 1
digit = 0
now = 0
for i in range(N):
    now = int(S[i])*(10**digit) + now
    sum_of_mod[now % 2019] += 1
    digit += 1
    now %= 2019
    digit %= 2019

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

Submission status: Wrong Answer

Solution code:
S=str(input())

#S="181718181718"
n=len(S)
list2019=[]
ans=0

for i in range(1,100):
    a=i*2019
    b=str(a)
    if int(S)<a:
        break
    if '0' not in b:
        list2019.append(b)

#print(list2019)
for tgt in list2019:
    for i in range(n-len(tgt)+1):
        if S.find(tgt,i,i+len(tgt))==i:
            ans=ans+1
           # print(i,tgt,i+len(tgt))
      

print(ans)

Submission status: Wrong Answer

Solution code:
S=str(input())

#S="181718181718"
n=len(S)
list2019=[]
ans=0

for i in range(1,100):
    a=i*2019
    b=str(a)
    if int(S)<a:
        break
    if '0' not in b:
        list2019.append(b)

#print(list2019)
for tgt in list2019:
    for i in range(n-len(tgt)+1):
        if S.find(tgt,i,i+len(tgt))==i:
            ans=ans+1
            print(i,tgt,i+len(tgt))
      

print(ans)

Submission status: Wrong Answer

Solution code:
S=str(input())

list2019=[]
ans=0

for i in range(1,100):
    a=i*2019
    b=str(a)
    if '0' not in b:
        list2019.append(str(a))

#print(' '.join(list2019))

for i in list2019:
    ans = ans+S.count(i)

print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
# print(s[2:len(s)])
l = len(s)
count = 0


# for i, j in itertools.combinations(range(len(s)+1), 2):
#     if(int(s[i:j]) % 2019 == 0):
#         count = count + 1
#
# print(count)

for i in range(2019):
    count2 = 0
    for j in range(l):
        if int(s[j:l]) % 2019 == i:
            count2 = count2 + 1
    count = count + (count2 * (count2 - 1)) / 2
print(int(count))

Submission status: Wrong Answer

Solution code:
s=input()
r=set()
last=0
power=1
d={0:0}
total=0
rem=0
for i in range(len(s)-1,-1,-1):
    n=int(s[i])*power+rem
    power*=10
    power=power%2019
    rem=n%2019
    if rem in r:
        d[rem]+=1
        total+=d[rem]-1
    else:
        r.add(rem)
        d[rem]=1
if d[0]==1:
    print(total+1)
else:
    print(total)

Submission status: Wrong Answer

Solution code:
s = str(input())

count = 0

if len(s) < 4:
    print(0)
else:
    for i in range(1, len(s) + 1):
        for j in range(i, len(s) + 1):
            ss = int(s[i-1:j])
            if ss < 2019:
                continue
            if (ss % 2019) == 0:
                count += 1
print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
s = str(input())
N = len(s)
array = [0]*2019
array[0] += 1
count = 0
d = 1
r = 0
for i in reversed(range(0, N)):
    r = ( r + int( s[i] ) * d ) % 2019
    d = d * 10 % 2019
    print(s[i],r,d)
    array[r] += 1
for i in array:
    count += i*(i-1)/2
print(int(count))

Submission status: Wrong Answer

Solution code:
'''
[point 1]
1817181712114 の部分 "18171"について考える...

    181710000 / 10000 ≡ 0 (MOD 2019) ならば、2019の倍数
    181710000 ≡ 0 (MOD 2019) でよい

[point 2]
    181710000
    =
    181712114
    -
         2114

    なので、特定区間の値 は 累積和の差 から瞬時に求められる。
    さらに、181710000 ≡ 0 (MOD 2019) を考えると、

    0 ≡ 181712114 - 2114
    → 181712114 ≡ 2114

    となる。
    結局の所、MOD2019において合同な累積和のペアの数の数え上げ。
'''

from collections import defaultdict

def gen_10exp_mod(n, mod):
    a = 1
    yield a
    for _ in range(1, n):
        a = (a*10) % mod
        yield a

def main():
    MOD = 2019
    S = input()[::-1]
    # 桁ごとの実際の値を計算 (MOD)
    A = [int(s)*n % MOD for s, n in zip(S, gen_10exp_mod(len(S), MOD))]
    # 累積和を計算
    ACC = [0]
    for a in A:
        ACC.append((ACC[-1] + a) % MOD)
    # ペア数え上げ
    print(ACC)
    d = defaultdict(int)
    for acc in ACC:
        d[acc] += 1
    ans = sum(v*(v-1)//2 for v in d.values())
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import collections

mod = 2019

def main():
    S = list(input())
    lenS = len(S)
    Smod2019 = [0] * lenS
    tmp = 0
    for i in range(lenS):
        tmp += (pow(10, i, mod)*int(S[-(i+1)]))%mod
        Smod2019[i] = tmp%mod
    
    cnt = collections.Counter(Smod2019)
    cntitems = cnt.items()
    ans = 0
    #print(cntitems)
    for c in cntitems:
        if c[0] == 0:
            ans += c[1]
        else:
            ans += (c[1]*(c[1]-1))//2
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections

mod = 2019

def main():
    S = list(input())
    lenS = len(S)
    Smod2019 = [0] * lenS
    tmp = 0
    for i in range(lenS):
        tmp += (pow(10, i, mod)*int(S[-(i+1)]))%mod
        Smod2019[i] = tmp%mod
    
    cnt = collections.Counter(Smod2019)
    cntitems = cnt.items()
    ans = 0
    #print(cntitems)
    for c in cntitems:
        if c[0] == 0:
            ans += c[1]
        else:
            ans += (c[1] >= 2)*(c[1]-1)
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from scipy.special import comb
from collections import Counter, deque

D = deque(map(int, list(input())))
a = {}
value = 0

for i in range(len(D)):
    value = value + D.pop() * 10**i
    modulo = value % 2019
   # print(modulo)
    if modulo in a.keys():
        a[modulo] += 1
    else:
        a[modulo] = 1


b = [comb(i, 2, exact=True) for i in a.values() if i > 1]
#print(b)
print(sum(b))

Submission status: Wrong Answer

Solution code:
def main():
  s = input()[::-1]
  l = len(s)
  n = 2019
  dp = [0]*n
  wk = 0
  r = 1
  for i in range(l):
    wk += int(s[i])*r
    wk %= n
    dp[wk] += 1
    r*= 10
    r %= n
  print(sum([i*(i-1)//2 for i in dp]))
main()

Submission status: Wrong Answer

Solution code:
def main():
  s = input()[::-1]
  l = len(s)
  n = 2019
  dp = [0]*n
  wk = 0
  r = 1
  for i in range(l):
    wk += int(s[i])*r
    wk %= n
    dp[wk] += 1
    r*= 10
    r %= n
  print(sum([i*(i-1)//2 for i in dp]),dp)
main()

Submission status: Wrong Answer

Solution code:
s=str(input())
n=len(s)
ans=0
l=[0 for i in range(2019)]
now=l[int(s[n-1])]
r=1
for i in range(1,n+1):
  now=(now+int(s[-i])*r)%2019
  l[now]+=1
  r=r*10
  r=r%2019
ans+=l[0]
l[0]=0
for i in l:
  ans+=int(i*(i-1)//2)
print(ans)
#print(l)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
S =input()
count=0
for i in range(1,len(S)):
    for j in range(i+1,len(S)+1):
        if int(S[i:j+1]) % 2019 == 0:
            count+=1
        else:
            pass
print(count)

Submission status: Wrong Answer

Solution code:
S = list(reversed(input()))
print(S)
length = len(S)

a = [0]*length
for i in range(length):
    pickup = int(S[i])
    a[i] = pickup*pow(10, i, 2019)

b = [0]*(length+1)
for i in range(1, length+1):
    b[i] = (b[i-1] + a[i-1]) % 2019
cnt, ans = [0] * 2019, 0
for x in b:
    ans += cnt[x]
    cnt[x] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
s = str(input())
n = len(s)
print(s)
s = s[::-1]
print(s)
x, tot = 1, 0
m = 2019
ans = 0
cnt = [int() for _ in range(m)]
for i in range(n):
    cnt[tot] += 1
    tot += (int(s[i])) * x
    tot %= m
    ans += cnt[tot]
    x = x * 10 % m
print(ans)