Problem:


Score : 500 points

Problem Statement

Takahashi has a string S of length N consisting of digits from 0 through 9.

He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S - there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.

Here substrings starting with a 0 also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.

Compute this count to help Takahashi.

Constraints

1 \leq N \leq 2 \times 10^5

S consists of digits.

|S| = N

2 \leq P \leq 10000

P is a prime number.

Input

Input is given from Standard Input in the following format:

N P
S

Output

Print the number of non-empty (contiguous) substrings of S that are divisible by P when regarded as an integer written in base ten.

Sample Input 1

4 3
3543

Sample Output 1

6

Here S = 3543. There are ten non-empty (contiguous) substrings of S:

3: divisible by 3.

35: not divisible by 3.

354: divisible by 3.

3543: divisible by 3.

5: not divisible by 3.

54: divisible by 3.

543: divisible by 3.

4: not divisible by 3.

43: not divisible by 3.

3: divisible by 3.

Six of these are divisible by 3, so print 6.

Sample Input 2

4 2
2020

Sample Output 2

10

Here S = 2020. There are ten non-empty (contiguous) substrings of S, all of which are divisible by 2, so print 10.

Note that substrings beginning with a 0 also count.

Sample Input 3

20 11
33883322005544116655

Sample Output 3

68



Sample input:
4 3
3543


Sample output:
6

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n, p = LI()
    s = S()
    ans = 0
    if p == 2 or p == 5:
        for i in range(n):
            if int(s[i]) % p != 0:
                pass
            else:
                ans += i + 1
    else:
        tmp = 0
        d = defaultdict(int)
        d[0] = 1
        for i in range(n - 1, -1, -1):
            tmp = tmp * 10 + int(s[i])
            tmp %= p
            ans += d[tmp]
            d[tmp] += 1

    print(ans)
    return


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

Submission status: Wrong Answer

Solution code:
from collections import Counter

n, p = map(int, input().split(" "))
s = list(map(int, input()))
s = s[::-1]

ans = 0
if 10 % p == 0: # p = 2, 5
    for i, num in enumerate(s, 1):
        if num % p == 0:
            ans += i
    print(ans)
    exit()

power = 1
t = [0] * len(s)
t[0] = s[0] % p
for i in range(1, len(s)):
    power = power * 10 % p
    t[i] = (t[i-1] + s[i] * power) % p

counter = Counter(t)
for i in counter.values():
    ans += i * (i-1) // 2
ans += counter[0]
print(ans)

# count = [0] * p
# count[0] = 1
# for i in t:
#     ans += count[i]
#     count[i] += 1
# print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n, p = map(int, input().split(" "))
s = list(map(int, input()))
s = s[::-1]

ans = 0
if 10 % p == 0: # p = 2, 5
    for i, num in enumerate(s, 1):
        if num % p == 0:
            ans += i
    print(ans)
    exit()

power = 1
t = [0] * len(s)
t[0] = s[0] % p
for i in range(1, len(s)):
    power = power * 10 % p
    t[i] = (t[i-1] + s[i] * power) % p

# counter = Counter(t)
# for i in counter.values():
#     ans += i * (i-1) // 2
# ans += counter[0]
# print(ans)

count = [0] * p
count[0] = 1
for i in t:
    ans += count[i]
    count[i] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n, p = map(int, input().split(" "))
s = list(map(int, input()))
s = s[::-1]

ans = 0
if 10 % p == 0: # p = 2, 5
    for i, num in enumerate(s, 1):
        if num % p == 0:
            ans += i
    print(ans)
    exit()

power = 1
t = [0] * len(s)
t[0] = s[0] % p
for i in range(1, len(s)):
    power = power * 10 % p
    t[i] = (t[i-1] + s[i] * power) % p

# counter = Counter(t)
# for i in counter.values():
#     ans += i * (i-1) // 2
# ans += counter[0]
# print(ans)
# print(counter)
# print(t)
count = [0] * p
count[0] = 1
for i in t:
    print(count)
    ans += count[i]
    count[i] += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N, P = map(int, input().split())
S = input()

ans = 0

if P == 2 or P == 5:
    for i in range(N):
        if int(S[-1 - i]) % 2 == 0:
            ans += N - i
else:
    M = []
    cum = [0]

    for i in range(N):
        M.append(pow(10, i, P) * int(S[-1 - i]) % P)

    for i in range(N):
        cum.append((cum[-1] + M[i]) % P)

    C = Counter(cum)

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

print(ans)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = input()
U = [0]*P
ans = 0
if P == 2 or P == 5:
    for i in range(0, N):
        if int(S[i])%P == 0:
            ans += i+1
    print (ans)
else:
    t, s = 0, 1
    for i in range(0, N):
        t = (int(S[i])*s+t)%P
        U[t] += 1
        s = s*10%P
    for u in U:
        ans += u*(u-1)//2
    ans += U[0]
    print (ans)

Submission status: Wrong Answer

Solution code:
def e_divisible_substring():
    # 参考: https://atcoder.jp/contests/abc158/submissions/10611866
    from collections import Counter
    N, P = [int(i) for i in input().split()]
    S = [int(ch) for ch in input()]  # 数字を桁ごとにバラす

    def solve_specific(S, p):
        """p -> 2 または 5 のときは、連続部分文字列が p の倍数かどうかは
        1の位だけ見ればよい。つまり左から k 番目に 2 か 5 の倍数がある場合、
        k 個の連続部分文字列が p の倍数となる。"""
        return sum(k for k, s in enumerate(S, 1) if s % p == 0)

    if P in (2, 5):
        return solve_specific(S, P)

    s = S[::-1]  # 下の桁から見ていく
    # editorial の U_i mod P の計算
    u = [s % P for s in S]
    power = 1
    for i in range(1, N):
        power *= 10
        power %= P  # S の桁数は最大 20万 なので、この処理は必要
        u[i] = u[i - 1] + power * s[i]
        u[i] %= P
    # 配列 u における、値が等しいインデックス 2 つを選ぶと、そのインデックスが表す
    # 2 つの整数の差は P の倍数になる
    # 値が 0 のインデックスについては、それ単体が P の倍数である
    counter = Counter(u)
    return sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]

print(e_divisible_substring())

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = list(map(int, list(input())))[::-1]

if 10%p==0:
    result = 0
    for i in range(n):
        if s[i]%p==0:
            result += n-i+1
else:
    r = [0 for _ in range(p)]
    r[0] = 1
    t = 0
    for i in range(n):
        t += (s[i]*(10**i))%p
        t %= p
        r[t] += 1
    result = 0
    for i in r:
        result += i*(i-1)//2
print(result)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = list(map(int, list(input())))

if 10%p==0:
    r = 0
    for i in range(1,n+1):
        if s[-i]%p==0:
            r += n-i+1
    print(r)
else:
    si = [s[-1]%p]
    r = 0
    for i in range(1, n):
        si.append((si[-1]+(s[-i]*(10**(i-1)))%p)%p)
    for i in range(n):
        r += si[i+1:].count(si[i])+(si[i]==0)
    print(r)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, P, S):
    if P == 2 or P == 5:
        n = 0
        ans = 0
        for c in reversed(S):
            if int(c) % P == 0:
                n += 1
            ans += n
        return ans

    p = Counter()
    t = 1
    ans = 0
    c = 0
    for i in range(N):
        a = ((int(S[N-i-1]) * t) + c) % P
        c = a
        p[a] += 1
        ans += p[a]
        t = (t * 10) % P

    return ans


def main():
    N, P = read_int_n()
    S = read_str()
    print(slv(N, P, S))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = input()
U = [0]*P
ans = 0
for i in range(0, N):
    U[int(S[i:N])%P] += 1
for u in U:
    ans += u*(u-1)//2
ans += U[0]
print (ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, P = map(int,input().split())
S = list(map(int,input()))

ans = 0
if P == 2:
    for i,s in enumerate(S):
        if s % 2 == 0:
            ans += i + 1
elif P == 5:
    for i,s in enumerate(S):
        if s % 5 == 0:
            ans += i + 1
else:
    res = []
    n = 0
    for s in S[::-1]:
        n = (10*n + s) % P
        res.append(n)

    res.append(0) # right

    cnts = Counter(res)
    for ind, cnt in cnts.items():
        if cnt == 1:
            continue
        ans += cnt * (cnt - 1) // 2

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, P, S):
    if P == 2 or P == 5:
        n = 0
        for c in S:
            if int(c) % P == 0:
                n += 1
        return n * (n+1) // 2

    p = Counter()
    t = 1
    ans = 0
    c = 0
    for i in range(N):
        a = ((int(S[N-i-1]) * t) + c)% P
        c = a
        if a == 0:
            ans += 1
        ans += p[a]
        p[a] += 1
        t = (t * 10) % P

    return ans


def main():
    N, P = read_int_n()
    S = read_str()
    print(slv(N, P, S))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, P, S):
    if P == 2:
        n = 0
        for c in S:
            if int(c) % 2 == 0:
                n += 1
        return n * (n+1) // 2
    elif P == 5:
        n = 0
        for c in S:
            if int(c) == 5:
                n += 1
        return n * (n+1) // 2

    p = Counter()
    t = 1
    ans = 0
    c = 0
    for i in range(N):
        a = ((int(S[N-i-1]) * t) + c)% P
        c = a
        if a == 0:
            ans += 1
        ans += p[a]
        p[a] += 1
        t = (t * 10) % P

    return ans


def main():
    N, P = read_int_n()
    S = read_str()
    print(slv(N, P, S))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, p = map(int, input().split())
s = list(map(int, list(input())))
si = [s[-1]]
for i in range(2, n+1):
    si.append(si[-1]+s[-i]*(10**(i-1)))
si = [i%p for i in si]
si_counter = Counter(si).items()
r = 0
for num, count in si_counter:
    if count >= 2:
        r += (count*(count-1))//2
    if num == 0:
        r += count
print(r)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = input()
if P == 2:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['2', '4', '6', '8', '0']:
            counter += i + 1
    print(counter)
elif P == 5:
    counter = 0
    for i in range(len(S)):
        if S[i] in ['5', '0']:
            counter += i + 1
    print(counter)
else:
    list_a = [0] * P
    list_a[0] += 1
    counter = 0
    temp = int(S[N-1:]) % P
    for i in range(N):
        counter += list_a[temp]
        list_a[temp] += 1
        temp -= int(S[N-i-1])
        temp %= P
    print(counter)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, P = map(int,input().split())
S = list(map(int,input()))

ans = 0
if P == 2:
    for i,s in enumerate(S):
        if s % 2 == 0:
            ans += i + 1
elif P == 5:
    for i,s in enumerate(S):
        if s % 5 == 0:
            ans += i + 1
else:
    res = []
    n = 0
    for s in S[::-1]:
        n = (10*n + s) % P
        res.append(n)

    res.append(0) # right

    inds = np.unique(res)

    for ind in inds:
        cnt = np.count_nonzero(res == ind)
        if cnt == 1:
            continue
        ans += cnt * (cnt - 1) // 2
print(ans)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = list(map(int, list(input())))

u = [ 0 for i in range(n+1)]

d = 1
for i in range(n):
    u[n-(i+1)] = (u[n-i] + s[n-1-i] * d) % p
    d *= 10 * d % p

# print(u, d)

def solve(u, s):
    if p == 2 or p == 5:
        return solve1(s)
    else:
        return solve2(u)


def solve1(s):
    ans = 0
    for i in range(n):
        if s[i] % p == 0:
            ans += i+1
    return ans

def solve2(u):
    ans = 0
    cnt = [0 for i in range(p)]
    for i in range(n+1):
        cnt[u[i]] += 1
    for i in range(p):
        q = cnt[i]
        ans += (q * (q-1)) // 2
    return ans

print(solve(u, s))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, p = map(int, input().split())
s = list(map(int, list(input())))
s = [(s[-i]*(10**(i-1))) for i in range(1, n+1)]
si = [s[0]%p]
for i in range(1, n):
    si.append((si[-1]+s[i])%p)
si_counter = list(Counter(si).items())
r = 0
for num, count in si_counter:
    if count >= 2:
        r += (count*(count-1))//2
    if num == 0:
        r += count
print(r)

Submission status: Wrong Answer

Solution code:
import numpy as np
from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def main(inputs):
	n,p=getIntList(inputs[0])
	s=inputs[1][0]
	
	ans=0
	if p%2==0 or p%5==0:
		for i0 in range(len(s)-1,-1,-1):
			sub=int(s[i0:i0+1])
			if sub%p==0:
				ans+=i0+1
	else:
		numP0=np.zeros(p, int32)
		numP0[0]=1
		r=0
		modD=10%p
		for i0 in range(len(s)-1,-1,-1):
			sub=s[i0:i0+1]
			sub=int(sub)
# 			print("i0", i0)
# 			print("sub", sub)
			if i0==len(s)-1:
				sub=r+sub
			else:
				sub=r+sub*10*modD
# 			print("sub", sub, "r", r, "sub%p", sub%p)
			r=sub%p
			ans+=numP0[r]
# 			print(numP0, numP0[r])
			numP0[r]+=1
			modD=(modD*10)%p
# 			print(numP0)
# 			print()
	print(ans)
		

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Wrong Answer

Solution code:
import sys


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


n, p = map(int, input(). split())
s = tuple(map(int, input()[::1]))

cnt = 0
if 10 % p == 0:
    for i, c in enumerate(s):
        if int(c) % p == 0:
            cnt += n - i
else:
    accmod = [0] * p
    d = 1
    num = 0
    for i in range(n):
        num = (num + s[i] * d) % p
        accmod[num] += 1
        d = (d * 10) % p
    for v in accmod:
        if v > 1:
            cnt += v * (v - 1) // 2
    cnt += accmod[0]
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, p = map(int, input().split())
s = list(map(int, list(input())))
s = [(s[-i]*(10**(i-1)))%p for i in range(1, n+1)]
si = [s[0]]
for i in range(n):
    si.append((si[-1]+s[i])%p)
si_counter = list(Counter(si).items())
r = 0
for num, count in si_counter:
    if count >= 2:
        r += (count*(count-1))//2
print(r)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


n,p = m()

s = input().split()[0]

co = 0

mo = [0 for i in range(p)]

data = [0 for i in range(n)]

if p == 2:
    for i in range(n):
        if int(s[i]) % 2 == 0:
            co += i+1
elif p == 5:
    for i in range(n):
        if int(s[i]) % 5 == 0:
            co += i+1

else:
    s = s[::-1]
    data[0] = int(s[0]) % p
    for i in range(1,n):
        data[i] = (data[i-1] * 10 + int(s[i]))% p

    mo[0] = 1
    for i in range(n):
        co += mo[data[i]]
        mo[data[i]] += 1



print(co)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys


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


n, p = map(int, input(). split())
s = tuple(map(int, input()[::1]))

cnt = 0
if 10 % p == 0:
    for i, c in enumerate(s):
        if int(c) % p == 0:
            cnt += n - i
else:
    r = defaultdict(int)
    r[0] = 1
    num = 0
    for i in range(n):
        num = (num + pow(10, i, p) * s[i]) % p
        r[num] += 1
    for v in r.values():
        if v.bit_length() > 1:
            cnt += v * (v - 1) // 2
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, P = map(int, input().split())
S = list(map(int, list(input())))
# print(S)
S.reverse()

ans = 0
if P == 2 or P == 5:
    cnt = 0
    for i in range(N):
        if S[i] % P == 0:
            cnt += 1

    if cnt != 0:
        ans += cnt * (cnt + 1) // 2
else:
    cummod = [0] * P

    d = 1
    prev = 0
    for i in range(N):
        m = (S[i] * d) % P
        m += prev
        m %= P
        cummod[m] += 1
        d *= 10
        d %= P
        prev = m

    cummod[0] += 1

    for n in cummod:
        if n <= 1:
            continue
        ans += n * (n - 1) // 2

    #ans += cummod[0]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, P = map(int, input().split())
S = list(map(int, list(input())))
# print(S)
S.reverse()

ans = 0
if P == 2 or P == 5:
    cnt = 0
    for i in range(N):
        if S[i] % P == 0:
            cnt += 1

    if cnt != 0:
        ans += cnt * (cnt + 1) // 2
else:
    cummod = [0] * P

    d = 1
    prev = 0
    for i in range(N):
        m = (S[i] * d) % P + prev
        m %= P
        cummod[m] += 1
        d *= 10
        prev = m

    #cummod[0] += 1

    for n in cummod:
        if n <= 1:
            continue
        ans += n * (n - 1) // 2

    ans += cummod[0]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, P = map(int, input().split())
S = list(map(int, list(input())))
# print(S)
S.reverse()

ans = 0
if P == 2 or P == 5:
    cnt = 0
    for i in range(N):
        if S[i] % P == 0:
            cnt += 1

    if cnt != 0:
        ans += cnt * (cnt + 1) // 2
else:
    cummod = [0] * P

    d = 1
    prev = 0
    for i in range(N):
        m = (S[i] * d) % P + prev
        m %= P
        cummod[m] += 1
        d *= 10
        prev = m

    cummod[0] += 1

    for n in cummod:
        if n <= 1:
            continue
        ans += n * (n-1) // 2

print(ans)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = list(map(int,list(input())))
U = []


for i in range(N+1):
    tmp = 0
    for j in range(i,N):
        tmp += S[j] * (10 ** (N-1-j))
    U.append(tmp % P)
    
def check1(i,j,P,S):
    return S[i] % P == 0

def check2(i,j,P,U):
    num = U[i]-U[j+1]
    return num == 0

def check(i,j,P,U,S):
    if P == 2 or P == 5:
        return check1(i,j,P,S)
    else:
        return check2(i,j,P,U)

ans = 0
for i in range(N):
    for j in range(i,N):
        if check(i,j,P,U,S):
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin

def main():
    input=stdin.readline
    n, p = map(int, input().split())
    s = input()
    co = [0]*p
    
    c = 0
    num = 0
    
    if p == 2 or p == 5:
        for i in range(n):
            if int(s[i])%p == 0:
                c += i+1
    else:
        s = int(s)
        for i in range(n-1, -1, -1):
            num = s%10**(n-1-i)
            m = num%p
            if m == 0:
                c += 1
            c += co[m]
            co[m] += 1   
            
    print(c)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:


from collections import Counter
import sys


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


n, p = map(int, input(). split())
s = tuple(map(int, input()[::1]))

cnt = 0
if 10 % p == 0:
    for i, c in enumerate(s):
        if int(c) % p == 0:
            cnt += n - i
else:
    c = Counter([0])
    num = 0
    for i in range(n):
        num = (num + pow(10, i, p) * s[i]) % p
        c += Counter([num])
    for v in c.values():
        cnt += v * (v - 1) // 2

print(cnt)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = list(map(int,list(input())))
U = []


for i in range(N+1):
    tmp = 0
    for j in range(i,N):
        tmp += S[j] * (10 ** (N-1-j))
    U.append(tmp % P)
    
def check1(i,j,P,S):
    return S[i] % P == 0

def check2(i,j,P,U):
    num = U[i]-U[j+1]
    return num % P == 0

def check(i,j,P,U,S):
    if P == 2 or P == 5:
        return check1(i,j,P,S)
    else:
        return check2(i,j,P,U)


ans = 0
for i in range(N):
    for j in range(i,N):
        if check(i,j,P,U,S):
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,p = map(int,input().split())
s = input()

sur1 = [int(s[0]) % p]
sur2 = [int(s[-1]) % p]
sur10 = [1 % p]
for i in range(n-1):
    sur1 += [(sur1[i] * 10 + int(s[i+1])) % p]
    sur10 += [(sur10[i] * 10) % p]
    sur2 += [(sur2[i] + sur10[i+1] * int(s[-i-2])) % p]

d = defaultdict(int)
for x in sur2:
    d[x] += 1

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

Submission status: Wrong Answer

Solution code:
import sys

n,p = map(int, input().split())
s = input()

if p == 2 or p == 5:
  ans = 0
  for i in range(len(s)):
    if int(s) % p == 0:
      ans += i + 1
    
  print(ans)
  sys.exit(0)
  

last_mod = 0
keta_mod = 1
mod_array = [0] * p
mod_array[0] = 1



for i in reversed(range(len(s))):
  tmp = int(s[i]) * keta_mod
  last_mod = (last_mod + tmp) % p
  keta_mod = (keta_mod * 10) % p
  mod_array[last_mod] += 1
  
ans = 0
for v in mod_array:
  ans += v * (v-1) // 2
  
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
if __name__ == '__main__':
    lines = sys.stdin.readlines()
    line = [a.strip('\n').split(' ') for a in lines]
    for i,v in enumerate(line):
        if i == 0:
            n = int(v[0])
            p = v[1]
        else:
            numbers = list(v[0])
            # print(numbers)

    count = 0
    leng = len(list(p))
    p = int(p)
    # print(p)

    # print(numbers)
    numbers_int = [int(i) for i in numbers]
    # print(numbers)

    map_ = dict()
    for i in set(numbers_int):
        for j in range(n+1):
            map_[i,j] = (i * (10**j)) % p

    # print(map_)

    count = 0
    for i in range(n):
        for j in range(i,n):
            tar = numbers_int[i:j+1]
            leng = len(tar)
            su = 0 
            for k,v in enumerate(tar):
                su += map_[v,leng - k]
            if su % p == 0:
                count += 1
                # print(tar)

    print(count)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()

c = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i])%p == 0:
            c += i+1
        
print(c)

Submission status: Wrong Answer

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,p = inm()
acc = [0]*(n+1)
a = [0]*(n+1)
ss = ins()
s = ss[::-1]
q = 1
for i in range(n):
    x = int(s[i])
    r = q*x
    acc[i+1] = (acc[i]+r)%p
    q = (q*10)%p
ddprint(acc)
h = [0]*p
for i in range(n+1):
    h[acc[i]] += 1
ddprint(h)
sm = 0
for i in range(p):
    x = h[i]
    sm = (sm+x*(x-1)//2)
print(sm)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n, p = map(int, input(). split())
s = input()

cnt = 0
if 10 % p == 0:
    for i, c in enumerate(s, 1):
        if int(c) % p == 0:
            cnt += 1
else:
    rem_dic = defaultdict(int)
    rem_dic[0] = 1
    for i in range(1, n + 1):
        rem_dic[int(s[n - i:]) % p] += 1
    for rem_cnt in rem_dic.values():
        cnt += rem_cnt * (rem_cnt - 1) // 2

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n, p = map(int, input(). split())
s = input()

cnt = 0
if 10 % p == 0:
    for i, c in enumerate(s, 1):
        if int(c) % p == 0:
            cnt += 1
else:
    rem_dic = defaultdict(int)
    rem_dic[0] = 1
    for i in range(1, n + 1):
        rem_dic[int(s[n - 1:]) % p] += 1
    for rem_cnt in rem_dic.values():
        cnt += rem_cnt * (rem_cnt - 1) // 2

print(cnt)

Submission status: Wrong Answer

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,p = inm()
acc = [0]*(n+1)
a = [0]*(n+1)
ss = ins()
s = ss[::-1]
r = 0
q = 1
for i in range(n):
    x = int(s[i])
    r = q*x
    a[i] = r
    acc[i] = (acc[i-1]+r)%p
    q = (q*10)%p
ddprint(a)
ddprint(acc)
h = [0]*p
for i in range(n):
    h[acc[i]] += 1
sm = h[0]
for i in range(p):
    x = h[i]
    sm = (sm+x*(x-1)//2)
print(sm)

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = input()

count = [0] * P
count[0] = 1
ans = 0
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: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()
u = []
for i in range(n):
  u.append(int(s[i:])%p)
x = [1] + [0]*(p-1)
ans = 0
for i in range(n-1,-1,-1):
  ans += x[u[i]]
  x[u[i]] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,p = map(int, input().split())
s = input()

last_mod = 0
keta_mod = 1
mod_array = [0] * p
mod_array[0] = 1



for i in reversed(range(n)):
  tmp = int(s[i]) * keta_mod
  last_mod = (last_mod + tmp) % p
  keta_mod = (keta_mod * 10) % p
  mod_array[last_mod] += 1
  
ans = 0
for v in mod_array:
  ans += v * (v-1) // 2
  
print(ans)

Submission status: Wrong Answer

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,p = inm()
acc = [0]*(n+1)
a = [0]*(n+1)
ss = ins()
s = ss[::-1]
r = 0
q = 1
for i in range(n):
    x = int(s[i])
    r = q*x
    a[i] = r
    acc[i] = (acc[i-1]+r)%p
    q = (q*10)%p
ddprint(a)
ddprint(acc)
h = [0]*p
for i in range(n):
    h[acc[i]] += 1
sm = h[0]
for i in range(p):
    x = h[i]
    sm = (sm+x*(x-1)//2)%R
print(sm)

Submission status: Wrong Answer

Solution code:
import sys
import math
import copy
import queue
def LI(): return [int(x) for x in input().split()]
n,p = LI()
s = input()
cnt = 0
if p == 2 or p == 5:
    for i in range(n-1,-1,-1):
       if int(s[i]) % p == 0:
           cnt += (i+1)
else:
    num = 0
    p10 = 1
    p_cnt = [1] + [0 for _ in range(p-1)]
    for i in s:
        num = (num * 10 + int(i)) % p
        p_cnt[num] += 1
        #p10 = (p10 * 10) % p
    for i in range(p):
        cnt += p_cnt[i] * (p_cnt[i]-1) // 2
print (cnt)