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:
import numpy as np
n, p = map(int, input().split())
s = list(map(int, input()))

mod = np.zeros(p)
mod[0] += 1
cnt = np.zeros(p)
cnt[0] += 1
swap = np.arange(p)


def mod_add(r):
    w = (swap * 10 + r) % p
    return cnt[w]


for a in s:
    r = a % p
    cnt = mod_add(r)
    mod += cnt
    cnt[0] += 1
print(int(mod[0]) - 1)

Submission status: Wrong Answer

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

# dp[i][j] = S[i:j+1] でみたときの答え
# 求めたいのは dp[0][N-1]
dp = [[0] * N for _ in range(N)]

# 初期値の設定
for i in range(N):
    dp[i][i] = (int(S[i]) % P == 0)  # S[i] が P の倍数なら 1, そうでないなら 0

# 値の更新
for k in range(1, N):
    for j in range(N-k):
        dp[j][j+k] = dp[j][j+k-1] + dp[j+1][j+k] + (int(S[j:j+k+1]) % P == 0)
        # 重複を防ぐために一度配ったらリセット
        dp[j+1][j+k] = 0

print(dp[0][N-1])

Submission status: Wrong Answer

Solution code:
N,P =20,11
S='33883322005544116655'
counter = 0
for i in range(1,int(N+1),1):
    for j in range(0,int(N-i+1),1):
        if int(S[j:j+i]) % P ==0:
            counter+=1

print(counter)

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

N,P=map(int,input().split())
S=input()
lst=[int(s)%P for s in S]

nlst=[0,lst[0]]
for i in range(1,N):
    nlst.append((nlst[-1]*10+int(S[i]))%P)
count=0
for i,n in Counter(nlst).most_common():
    if n>=2:
        count+=(n*(n-1))//2
print(count)

Submission status: Wrong Answer

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

answer=0
if N<=1000:
  for i in range(N):
    for j in range(i,N):
      si=int(S[i:j+1])
      if si%P==0:
        answer+=1
else:
  if P==2:
    for i in range(N):
      si=int(S[i])
      if si%2==0:
        answer+=i+1
  elif P==5:
    for i in range(N):
      si=int(S[i])
      if si%5==0:
        answer+=i+1    
  
print(answer)

Submission status: Wrong Answer

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

l = [[0,1]]
ans = 0

for i in range(n):
    m = int(s[i])
    for j in range(len(l)):
        k = (l[j][0] * 10 + m) % p
        if k == 0:
            ans += l[j][1]
            l[j][1] += 1
        l[j][0] = k

print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
l=list(input())
for i in range(n):
    l[i]=int(l[i])
w=0
wl=[]
po=pow(10,p-2,p)
if p==2 or p==5:
    ans=0
    for i in range(n):
        if l[i]%p==0:
            ans+=i+1
    print(ans)                    
for i in range(n):
    wl.append(w)
    #if w==0:
        #ans+=rr[n-1-i]
    w-=l[n-1-i]
    w*=po
    w%=p
wl.reverse()
r=[]
rt=0
for i in range(n):
    rt+=l[i]
    r.append(rt%p)
    rt*=10
#r.reverse()
d=[0]*p
ans=0
for i in range(n):
    d[r[i]]+=1
    ans+=d[wl[i]]  
print(ans)

Submission status: Wrong Answer

Solution code:
##mod M における　aの逆元を求めてくれる
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
#すなわちax==1(mod m)なる自然数xを返してくれる関数 動作時間:logM
def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

n,p=map(int,input().split())
s=list(input())
import collections
if p!=2 and p!=5:
    modlist=[0 for i in range(n+1)]
    
    modlist[1]=int(s[0])%p
    
    for i in range(2,n+1):
        modlist[i]=(10*modlist[i-1]+int(s[i-1]))%p
    K=pow(10,p-2,p)
    invlist=[0 for i in range(n+1)]
    invlist[0]=1
    invlist[1]=K
    for i in range(2,n+1):
        invlist[i]=(invlist[i-1]*K)%p
    uselist=[0 for i in range(n+1)]
    for i in range(n+1):
        uselist[i]=(modlist[i]*invlist[i])%p

    ANS=dict(collections.Counter(uselist))
    ans=0
    for some in ANS.values():
        ans+=some*(some-1)//2
    print(ans)
elif p==2:
    ans=0
    q=0
    for i in range(n):
        if int(s[i])%2==0:
            q+=1
        ans+=q
    print(ans)
elif p==5:
    ans=0
    q=0
    for i in range(n):
        if int(s[i])%5==0:
            q+=1
        ans+=q
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

def main():
    N,P = mis()
    S = input()
    z_10 = 10 % P
    ms = deque([0] * P)
    ans = 0
    for s in S:
        n = int(s) % P
        ms[n] += 1
        ans += ms[0]
        ms.rotate(n)
        ms.rotate(-z_10)
    print(ans)

main()

Submission status: Wrong Answer

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

StringP = str (P)
kosu = 0
if N < len(StringP):
    print(0)
else:
    for lng in range(1, N+1):
        for i in range(0, N-lng+1):
            if int(S[i:i+lng]) % P ==0:
                kosu = kosu+1

print(kosu)

Submission status: Wrong Answer

Solution code:
def main():
    N, P = map( int ,input().split())
    S = [ int(s) for s in list(input())]
    L = [0]*P
    L[0] += 1
    t = 0
    for s in S:
        t = (t*10+s)%P
        L[t] += 1
    ans = 0
    for l in L:
        ans += l*(l-1)//2
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,p = mi()

s = input()
sample = [0]
s_num = int(s)

for i in range(1,100000):
    tmp = p*i
    sample.append(tmp)
    if(tmp > s_num):
        break    

ans = 0
for i in range(1,n+1):
    for j in range(n-i+1):
        s_tmp = int(s[j:j+i])
        if(s_tmp in sample):
            ans += 1
            # print(s_tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
def answer():
    n, p = map(int, input().split())
    s = input()
    m = [0] * p
    dp = [0]
    for i, a in enumerate(s):
        m = amari(m, int(a), p)
        print(m)
        dp.append(dp[i] + m[0])
    print(dp[-1])

def amari(m, a, p):
    mm = [0] * p
    for i, b in enumerate(m):
        if b == 0:
            continue
        mm[(i * 10 + a) % p] += b
    mm[a%p] += 1
    return mm

answer()

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = [int(s) for s in input()]
dp = [[-1 for _ in range(N)] for _ in range(N)]
dp[N - 1][N - 1] = S[N - 1] % P

mods = []
for i in range(10 ** 6):
    if i == 0:
        mods.append(1)
    else:
        mods.append((10 ** (i % (P - 1))) % P)

ans = 0
for r in range(N - 1, -1, -1):
    for l in range(r, -1, -1):
        if r == l:
            dp[l][r] = (S[l] * mods[r - l]) % P
        else:
            dp[l][r] = (S[l] * mods[r - l] + dp[l + 1][r]) % P
        if dp[l][r] == 0:
            ans += 1

print(ans)

Submission status: Wrong Answer

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


N, P = map(int, input().split())
S = list(input()[:-1])
S = list(map(int, S))

pow_table = []
now = 1

for i in range(N+100):
    pow_table.append(now%P)
    now *= 10
    now %= P
    
pre = [0]

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

suf = []
suf.append(0)

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

suf = suf[:-1]

ans = 0
cnt = defaultdict(int)
M = pre[-1]
suf = suf[::-1]

for i in range(N):
    cnt[pre[i]] += 1
    ans += cnt[(M-suf[i])%P]
    #print((M-suf[i])%P, ans)
    
print(ans)

Submission status: Wrong Answer

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

# dp[i][j] = S[i:j+1] でみたときの答え
# 求めたいのは dp[0][N-1]
dp = [[0 for _ in range(N)] for _ in range(N)]

# 初期値の設定
for i in range(N):
    dp[i][i] = (int(S[i]) % P == 0)  # S[i] が P の倍数なら 1, そうでないなら 0

# 値の更新
for k in range(1, N):
    for j in range(N-k):
        dp[j][j+k] = dp[j][j+k-1] + dp[j+1][j+k] + (int(S[j:j+k+1]) % P == 0)
        # 重複を防ぐために一度配ったらリセット
        dp[j+1][j+k] = 0

print(dp[0][N-1])

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 sur1:
    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:
#  --*-coding:utf-8-*--

def modPow(a, b, mod):
    x = 1
    
    while b > 0:
        if b & 1:
            x = (x*a)%mod

        a = (a**2)%mod
        b //= 2

    return x


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

x = 0
counts = [0]*P
a, b = 1, 0

for s in S:
    c = int(s)

    a, b = 10*a%P, (10*b+c)%P
    d = (c%P - b)*modPow(a, P-2, P)%P
    counts[d] += 1

    x += counts[b]

print(x)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split(' '))
s = input()
p_len = len(str(p))
ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
#
import sys
import math
#import numpy as np
import itertools
from collections import Counter
# いくつか入力
n,p = (int(i) for i in input().split())
# 空白区切りの数列をリストに代入
s = [int(i) for i in list(input())] 

answer = 0
#print(s)
q=0
x=[]
for i in range(n):
    q=(q*10+s[i])%p
    x.append(q)

counter = Counter(x)
#print(counter)

for k in counter:
#    print(k)
    if k==0:
        answer += counter[k] * (counter[k]+1) // 2
    else:
        answer += counter[k] * (counter[k]-1) // 2

print(answer)

Submission status: Wrong Answer

Solution code:
from collections import deque

import numpy as np

n, p = map(int, input().split())
d = deque(input())

ans = 0
if p == 2 or p == 5:
  for i in range(n):
    k = int(d.popleft())
    if n % p == 0:
      ans += i + 1
else:
  sub = [0 for i in range(n)]
  wk = 0
  for i in range(n):
    k = int(d.pop())
    wk = (wk + k * pow(10, i, p)) % p
    sub[i] = wk
  ans = 0
  dic = {}
  for i in range(n):
    if sub[i] == 0:
      ans += 1
    if sub[i] in dic.keys():
      ans += dic[sub[i]]
      dic[sub[i]] = dic[sub[i]] + 1
    else:
      dic[sub[i]] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,p=MI()
    s=SI()
    aa=[int(c) for c in s[::-1]]
    cc=[0]
    ten=1
    for a in aa:
        cc.append((cc[-1]+a*ten)%p)
        ten=ten*10%p
    cnt=Counter(cc)
    ans=0
    for v in cnt.values():
        ans+=v*(v-1)//2
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
l=list(input())
for i in range(n):
    l[i]=int(l[i])
w=0
wl=[]
po=pow(10,p-2,p)
for i in range(n):
    wl.append(w)
    #if w==0:
        #ans+=rr[n-1-i]
    w-=l[n-1-i]
    w*=po
    w%=p
wl.reverse()
r=[]
rt=0
for i in range(n):
    rt+=l[i]
    r.append(rt%p)
    rt*=10
#r.reverse()
d=[0]*p
ans=0
for i in range(n):
    d[r[i]]+=1
    ans+=d[wl[i]]  
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n,p = nm()
s = list(map(int, list(ns())))
g = [0]*(n+1)
d = [0]*p
d[0] = 1
ans = 0
t = 1
for i in range(n-1,-1,-1):
    g[i] = (g[i+1] + s[i]*t)%p
    ans += d[g[i]]
    d[g[i]] += 1
    t = (t*10)%p
print(ans)

Submission status: Wrong Answer

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

import sys
from itertools import accumulate
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, P = MAP()
S = list(map(int, input()))

acc = [0] * N
cur = S[-1] % P
acc[-1] = cur
k = 1
for i in range(N-2, -1, -1):
    cur += pow(10, k, P) * S[i]
    cur %= P
    acc[i] = cur
    k += 1
acc = [0] + acc

C = Counter(acc)
ans = 0
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()[:: -1]

dp1 = [0] * P
dp1[0] = 1
dp2 = [0] * P

ans = 0
now = 0
for i, s in enumerate(map(int, S)):
    now = (s * pow(10, i, P) + now) % P
    ans += dp2[now]
    dp2 = dp1.copy()
    dp1[now] += 1

print(ans)

Submission status: Wrong Answer

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

# dp[i][j] = S[i:j+1] でみたときの答え
# 求めたいのは dp[0][N-1]
dp = [[0 for _ in range(N)] for _ in range(N)]

# 初期値の設定
for i in range(N):
    dp[i][i] = (int(S[i]) % P == 0)  # S[i] が P の倍数なら 1, そうでないなら 0

# 値の更新
for k in range(1, N):
    for j in range(N-k):
        dp[j][j+k] = dp[j][j+k-1] + dp[j+1][j+k] + (int(S[j:j+k+1]) % P == 0)
        # 重複を防ぐために一度配ったらリセット
        dp[j][j+k-1] = 0
        dp[j+1][j+k] = 0

print(dp[0][N-1])

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
 
n,p = na()
s = ns()
s = list(map(int, s))
ans = 0
 
seenRemainders = [[] for k in range(n)] #長さn
for i in range(n):
    remainder = 0
    prefixesFound = 0
    for j in range(i,n):
        remainder = (10 * remainder + s[j]) % p
        if remainder in seenRemainders[j]:
            break
        seenRemainders[j].append(remainder)
        if remainder == 0:
            prefixesFound+=1
    ans += prefixesFound * (prefixesFound + 1) // 2
 
print(ans)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split(' '))
s = input()
p_len = len(str(p))
ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

import numpy as np

n, p = map(int, input().split())
d = deque(input())

ans = 0
if p == 2 or p == 5:
  for i in range(n):
    k = int(d.popleft())
    if n % p == 0:
      ans += i + 1
else:
  sub = [0 for i in range(n)]
  wk = 0
  for i in range(n):
    k = int(d.pop())
    wk = (wk + k * pow(10, i, p)) % p
    sub[i] = wk
  print(sub)
  ans = 0
  dic = {}
  for i in range(n):
    if sub[i] == 0:
      ans += 1
    if sub[i] in dic.keys():
      ans += dic[sub[i]]
      dic[sub[i]] = dic[sub[i]] + 1
    else:
      dic[sub[i]] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, P = list(map(int, input().split()))
    S = map(int, input())
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    mod = P
    for i in range(2, P):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    H = [0] * N
    h = 0
    for i, s in enumerate(S):
        h = (h * 10 + s) % P
        H[i] = h
    K = [0] * P
    K[0] = 1
    shift = 1
    r = 0
    for i, h in enumerate(H):
        t = ((P-h) * inverse[shift]) % P
        r += K[t]
        K[(h * inverse[shift]) % P] += 1
        shift = (shift * 10) % P

    return r
   

print(main())

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
def main():
    n,p = tuple([int(t)for t in input().split()])

    s = input()[::-1]
    subs = [0]*p
    counter =0
    for i in range(0,n):
        subs[int(s[0:i+1])%p] +=1

    print(subs)

    counter+=subs[0]

    for i in range(p//2):
        counter+= subs[i]*subs[-i-1]


    counter+=subs[0]*(subs[0]-1)//2

    print(counter)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import math
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#############
# Main Code #
#############

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


mods = [0 for _ in range(P)]
count = 0

for digit in S:
  oldmods = mods
  mods = [0 for _ in range(P)]
  digit = int(digit)
  for i in range(P):
    mods[i] = oldmods[((i-digit)*pow(10, P-2, P))%P]
  mods[digit%P] += 1  
  count += mods[0]

print(count)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
l=list(input())
for i in range(n):
    l[i]=int(l[i])
w=0
wl=[]
po=pow(10,p-2,p)
for i in range(n):
    wl.append(w)
    #if w==0:
        #ans+=rr[n-1-i]
    w-=l[n-1-i]
    w*=po
    w%=p
wl.reverse()
exit()
r=[]
rt=0
for i in range(n):
    rt+=l[n-1-i]*(10**i)
    r.append(rt%p)
r.reverse()
d=[0]*p
ans=0
exit()
for i in range(n):
    d[r[i]]+=1
    ans+=d[wl[i]]  
print(ans)

Submission status: Wrong Answer

Solution code:
N, P = map(int,input().split()) 
S =  input()
count=0
for i in range(N):
    for j in range(i+1,N+1):
        tmp = int(S[i:j])
        print(tmp,tmp%P==0)
        if tmp%P==0:
            count+=1
print(count)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
a=0
l=[]
for i in range(10):
    p=pow(10,i,P)
    if not p in l:
        l.append(p)
le=len(l)
for i in range(-1,-le-1,-1):
    t=0
    c=[0]*P
    for k in range(i,-N-1,-1):
        if (i-k)%le==0:
            c[t]+=1
        t=(t+int(S[k])*l[(i-k)%le])%P
        a+=c[t]
print(a)

Submission status: Wrong Answer

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

rem=[0]*p
remls=[0]*n
remnow=0
for i in range(n-1,-1,-1):
    remnow = (remnow+int(s[i])*pow(10, n-1-i, p))%p
    rem[remnow]+=1
    remls[i]=remnow

ans=0
remnow2=0
remdiff=1
for i in range(n-1,-1,-1):
    remdiff2=(remdiff-remnow2)%p
    idx=-remnow2*pow(remdiff2,p-2,p)%p
    ans+=rem[idx]
    remnow2-=int(s[i])
    remnow2%=p
    remnow2*=pow(10,p-2,p)
    remnow2%=p
    remdiff-=int(s[i])
    remdiff%=p
    remdiff*=pow(10,p-2,p)
    remdiff%=p
    rem[remls[i]]-=1

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import chain

n, p = map(int, input().split())
S = input().strip()

d = {}
for x in chain.from_iterable((''.join(S[i:j]) for j in range(i+1, n+1)) for i in range(n)):
    if x not in d:
        d[x] = 1 if int(x) % p == 0 else 0
    else:
        d[x] += d[x]
print(sum(d.values()))

Submission status: Wrong Answer

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

pre = 0
ans = 0

d = {i:0 for i in range(p)}
d[0] = 1

ap = 1
for si in s[::-1]:
    si = int(si)
    a = (si * ap + pre) % p
    ans += d[a]
    d[a] += 1
    pre = a
    ap = (ap * 10) % p
print(ans)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def inverse_mod(a, m):  # mod mでのaの逆元
    b=m
    u=1
    v=0
    while b:
        t=a // b
        a -= t * b
        a, b=b, a
        u -= t * v
        u, v=v, u
    u %= m
    return u
def main():
    N,P=MI()
    S=ST()
    before = 0
    ans = 0
    d = defaultdict(int)
    d[0] += 1
    for i in range(N):
        x = int(S[i])
        before += x
        before %= P
        ans += d[(before*(inverse_mod(10,P)**i))%P]
        d[before] += 1
        before *= 10

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

Submission status: Wrong Answer

Solution code:
N, P = map(int, input().split())
S = input()
numMultiples = 0
seenRemainders = [set() for _ in range(N+1)]
for i in range(N):
    remainder = 0
    prefixesFound = 0
    for j in range(i, N):
        remainder = (10 * remainder + int(S[j])) % P
        if remainder in seenRemainders[j]:
            break
        seenRemainders[j].add(remainder)
        if remainder == 0:
            prefixesFound += 1
    numMultiples += prefixesFound * (prefixesFound + 1) // 2
print(numMultiples)

Submission status: Wrong Answer

Solution code:
import collections

N, P = map(int, input().split())
S = input()[::-1]

a, temp = [int(S[0]) % P], 1
for i in range(1, N):
    temp *= 10
    temp %= P
    a.append((a[-1] + (int(S[i]) % P * temp) % P) % P)

ans = 0
c = collections.Counter(a)
if 0 in c:
    ans += c[0]
    ans += c[0] * (c[0] - 1) // 2
    del c[0]
for x in c.keys():
    ans += c[x] * (c[x]-1) // 2 
print(ans)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
l=list(input())
for i in range(n):
    l[i]=int(l[i])
w=0
wl=[]
po=pow(10,p-2,p)
if p==2 or p==5:
    po=0
for i in range(n):
    wl.append(w)
    #if w==0:
        #ans+=rr[n-1-i]
    w-=l[n-1-i]
    w*=po
    w%=p
wl.reverse()
r=[]
rt=0
for i in range(n):
    rt+=l[n-1-i]*(10**i)
    r.append(rt%p)
r.reverse()
d=[0]*p
ans=0
for i in range(n):
    d[r[i]]+=1
    ans+=d[wl[i]]  
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n,p = l_in()
s = s_in()

from collections import Counter

c = Counter()

for i in range(n):
    m = int(s[i:])
    c[m%p] += 1

res = 0

for i in range(n):
    m = int(s[i:])
    res += c[m%p]-1
print(res//2 + c[0])

Submission status: Wrong Answer

Solution code:
from collections import Counter

N,P = map(int,input().split())
S = list(reversed(input()[0:N]))
A = [0]*N

h = 1

for _ in range(N):
    A[_] = int(S[_]) * h
    A[_] %= P
    h *= 10
    h %= P

B = [0]*(N+1)

for _ in range(N):
    B[_+1] = (A[_] + B[_])%P

#print(''.join(map(str,S)))
#print(B)

su = 0

for k,v in Counter(B).items():
    if v != 1:
        su += v * (v - 1) // 2

print(su)

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s = input()
m = [0 for i in range(p)]
l = 0
for i in range(1, n+1):
    l = int(s[-i:]) % p
    m[l] += 1
a = m[0]
for i in range(0, p):
    t = m[i]
    if t > 1:
        a += t * (t - 1) // 2
print(a)

Submission status: Wrong Answer

Solution code:
N, P = map(int,input().split())
S = input()
counter = 0
for i in range(1,int(N+1),1):
    for j in range(0,int(N-i+1),1):
        if float(S[j:j+i]) % P ==0:
            counter+=1

print(counter)

Submission status: Wrong Answer

Solution code:
n,p=map(int,input().split())
l=list(input())
for i in range(n):
    l[i]=int(l[i])
w=0
wl=[]
po=pow(10,p-2,p)
for i in range(n):
    wl.append(w)
    #if w==0:
        #ans+=rr[n-1-i]
    w-=l[n-1-i]
    w*=po
    w%=p
wl.reverse()
r=[]
rt=0
for i in range(n):
    rt+=l[n-1-i]*(10**i)
    r.append(rt%p)
r.reverse()
d=[0]*p
ans=0
exit()
for i in range(n):
    d[r[i]]+=1
    ans+=d[wl[i]]  
print(ans)

Submission status: Wrong Answer

Solution code:
N,P=map(int,input().split())
S=input()
A=[0]
tmp=0
for i in range(0,N):
    tmp+=(int(S[N-i-1])*(10**i))%P
    A.append(tmp%P)
    tmp%=P
A.sort()
ans=0
from bisect import bisect_left,bisect_right
for i in range(0,P):
    x=bisect_right(A,i)-bisect_left(A,i)
    if x>1:
        ans+=(x-1)*x//2
print(ans)

Submission status: Wrong Answer

Solution code:
n, p = [int(x) for x in input().split()]
s = input()

m = int(s) // p + 1

result = 0
for i in range(m):
  target = p * (i+1)
  result += s.count(str(target))
print(result)

Submission status: Wrong Answer

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

dp = [0] * P

ans = 0
now = 0
for i, s in enumerate(map(int, S)):
    now = (s * pow(10, i, P) + now) % P
    ans += dp[now]
    dp[now] += 1

print(ans + dp[0])

Submission status: Wrong Answer

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

sum(int(s[i:j+1])%p==0 for i in range(n) for j in range(i,n))

Submission status: Wrong Answer

Solution code:
n, p = map(int, input().split())
s =list(str(input()))
s = [int(c) for c in s]
s.reverse()

#print(s)

#s = [0] + s
#from itertools import accumulate
#cum =list(accumulate(s))
#cum = [c%p for c in cum]
temp = 0
cum = [0]*n
for i in range(n):
    temp += s[i]*10**i
    cum[i] = temp

cum = [0]+cum

#print(cum)

for i in range(n+1):
    cum[i] = cum[i]%p

d = {}
ans = 0
for i in range(n+1):
  if cum[i] not in d:
    d[cum[i]] = 1
  else:
    ans += d[cum[i]]
    d[cum[i]] += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, P = input().split()
p_len = len(P)
N = int(N)
P = int(P)

S = input()


cnt = sum([1 for i in range(N) if S[i] == '0'])
for l in range(p_len, N+1):
    for i in range(N+1-l):
        if int(S[i:i+l]) % P == 0:
            cnt += 1
print(cnt)