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: Runtime Error

Solution code:
import sys
from itertools import combinations, permutations, product, combinations_with_replacement, accumulate
from heapq import heapify, heappop, heappush, heappushpop
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from math import sqrt, log, floor, ceil, factorial, cos, sin, pi, gcd
from collections import deque
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
INF = float('inf')
LINF = 2**63-1
NIL = -LINF
MOD = 10**9+7
MGN = 4
def II(): return int(input())
def IF(): return float(input())
def IS(): return input().replace('\n', '')
def ILCI(n: int): return [II() for _ in range(n)]
def ILCF(n: int): return [IF() for _ in range(n)]
def ILI(): return list(map(int, input().split()))
def ILLI(n: int): return [[int(j) for j in input().split()] for i in range(n)]
def ILF(): return list(map(float, input().split()))
def ILLF(n: int): return [[float(j) for j in input().split()] for i in range(n)]
def LTOS(lst: list, sep: str = ' '): return sep.join(map(str, lst))
def DEC(lst: list): return list(map(lambda x: x-1, lst))
def INC(lst: list): return list(map(lambda x: x+1, lst))


def stoli(s, sep = ''):
    """ 文字列と区切り文字(列)を受け取り、
    整数のリストにして返す """
    if sep == None or sep == '':
        return list(map(int, list(s)))

    ls = []
    for e in s.split(sep):
        if e == None or e == '':
            continue
        else:
            ls.append(e)

    return list(map(int, ls))


def main():
    N, P = ILI()
    S = IS()

    d = stoli(S)
    
    d.reverse()

    if 10%P == 0:
        ans = 0
        for l in range(N):
            if d[l] % P == 0:
                ans += N-l
        print(ans)
        return 0

    md = [0] * N
    ten = 1
    for i in range(N):
        md[i] = (d[i] * ten) % P
        ten *= 10
        ten %= P
    
    sum = [0] * N
    sum[0] = md[0]
    for i in range(1,N):
        sum[i] = (sum[i-1] + md[i]) % P

    ans = 0
    cnt = [0] * P
    for i in range(N):
        ans += cnt[sum[i]]
        cnt[sum[i]] += 1
    ans += cnt[0]

    print(ans)
    return 0


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from itertools import combinations, permutations, product, combinations_with_replacement, accumulate
from heapq import heapify, heappop, heappush, heappushpop
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from math import sqrt, log, floor, ceil, factorial, cos, sin, pi, gcd
from collections import deque
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
INF = float('inf')
LINF = 2**63-1
NIL = -LINF
MOD = 10**9+7
MGN = 4
def II(): return int(input())
def IF(): return float(input())
def IS(): return input().replace('\n', '')
def ILCI(n: int): return [II() for _ in range(n)]
def ILCF(n: int): return [IF() for _ in range(n)]
def ILI(): return list(map(int, input().split()))
def ILLI(n: int): return [[int(j) for j in input().split()] for i in range(n)]
def ILF(): return list(map(float, input().split()))
def ILLF(n: int): return [[float(j) for j in input().split()] for i in range(n)]
def LTOS(lst: list, sep: str = ' '): return sep.join(map(str, lst))
def DEC(lst: list): return list(map(lambda x: x-1, lst))
def INC(lst: list): return list(map(lambda x: x+1, lst))


def stoli(s: str, sep: str = '') -> list:
    """ 文字列と区切り文字(列)を受け取り、
    整数のリストにして返す """
    if sep == None or sep == '':
        return list(map(int, list(s)))

    ls = []
    for e in s.split(sep):
        if e == None or e == '':
            continue
        else:
            ls.append(e)

    return list(map(int, ls))


def main() -> int:
    N, P = ILI()
    S = IS()

    d = stoli(S)
    
    d.reverse()

    if 10%P == 0:
        ans = 0
        for l in range(N):
            if d[l] % P == 0:
                ans += N-l
        print(ans)
        return 0

    md = [0] * N
    ten = 1
    for i in range(N):
        md[i] = (d[i] * ten) % P
        ten *= 10
        ten %= P
    
    sum = [0] * N
    sum[0] = md[0]
    for i in range(1,N):
        sum[i] = (sum[i-1] + md[i]) % P

    ans = 0
    cnt = [0] * P
    for i in range(N):
        ans += cnt[sum[i]]
        cnt[sum[i]] += 1
    ans += cnt[0]

    print(ans)
    return 0


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
  int N, P;
  string S;
  cin >> N >> P >> S;

  vector<int> mod(P);
  long long ans = 0, m = 0;
  if (P != 2 && P != 5)
    for (int i = N - 1; i >= 0; --i)
      m = (m * 10 + S[i] - '0') % P, ++mod[m];
  else
    for (int i = N - 1; i >= 0; --i)
      if ((S[i] - '0') % P == 0)
        ans += i + 1;

  ans += mod[0];
  for (int i = 0; i < P; ++i)
    ans += mod[i] * (mod[i] - 1) / 2;

  cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
input1 = input().split(" ")
N = int(input1[0])
P = int(input1[1])
S = input()

#print(N,P)
# 素数PでSで作れる数字を割る
cand_list = []

for i in range(N):
  for j in range(N-i):
    #print(S[i:(i+j+1)])
    cand_list.append(S[i:(i+j+1)])

cnt = 0
for c in cand_list:
  if int(c)%P==0:
    cnt = cnt + 1

print(cnt)

Submission status: Runtime Error

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

if P == 2 or P == 5:
    import sys
    sys.exit(1)
    ans = 0
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i+1
    print(ans)

val = int(S)
order = 10 ** N
suf_nums = [-1] * N
s = -1
for i in range(N):
    if s != -1:
        val -= s * order
    suf_nums[i] = val
    s = int(S[i])
    order //= 10

surpluses = [0] * P
ans = 0
suf_nums.reverse()
for num in suf_nums:
    surplus = num % P
    surpluses[surplus] += 1
    if surplus == 0:
        ans += surpluses[0]
    else:
        ans += surpluses[surplus] - 1

print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
import sys
if sys.platform == 'ios' or 'darwin':
    sys.stdin = open('input_file.txt')

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: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <array>
#include <map>
#include <cmath>
#include <memory>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (long long int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define DEFOR(LoopVariable,numberOFbegin,numberOFend) for (long long int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--)
#define REP(LoopVariable,numberOFend) for(long long int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

constexpr long long int linf = numeric_limits<long long int>::max()-5;
constexpr int inf= numeric_limits<int>::max()-5;
constexpr long long int mod = 1000000007;

int main(){
    long long int n, p;
    cin>>n>>p;
    long long int result = 0;
    long long int tmp;
    string s;
    cin >> s;
    
    if(p==2||p==5){
        long long int tmp2=1;
        REP(i,n){

            tmp = (long long int)(s[i] - '0');
            if(tmp%p==0){        
                result += tmp2;
                tmp2++;
            }
          //  cout << result << endl;
        }

        cout << result << endl;
    }else{
        int c[100000];
        c[0] = 1LL;
        long long  ans = 0;
        int num = 0;
        int pot = 1;
        for (int i = n - 1; i >= 0; i--)
        {
            num = (num + pot * (s[i] - '0')) % p;
            pot = (pot * 10) % p;
            ans += c[num];
            c[num]++;
    
        }
        cout << ans << endl;
    }

    return 0;
}

Submission status: Runtime Error

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:
    for _ in range(0, N):
        U[int(S)%P] += 1
        S = S.lstrip(S[0])
    for u in U:
        ans += u*(u-1)//2
    ans += U[0]
    print (ans)

Submission status: Runtime Error

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 = 0
    power = 1
    for i in range(N):
        temp += pow(10, i, mod=P) * int(S[N-i-1])
        temp %= P
        counter += list_a[temp]
        list_a[temp] += 1
    print(counter)

Submission status: Runtime Error

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

Submission status: Runtime Error

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, cnts = np.unique(res, return_counts=True)

    for cnt in cnts:
        if cnt == 1:
            continue
        ans += cnt * (cnt - 1) // 2
print(ans)

Submission status: Runtime Error

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()

ms = []
m = 0

res = 0
if p == 2:
    for i, t in reversed(s):
        t = int(t)
        if t%2 == 0:
            res += n-i

    print(res)
    exit()

if p == 5:
    for i, t in reversed(s):
        t = int(t)
        if t == 0 or t == 5:
            res += n-i

    print(res)
    exit()


for i, t in enumerate(s[::-1]):
    t = int(t)
    if t == 0:
        t = p
    m += t*(10**i)
    ms.append(m)
    c[m%p] += 1

for k, v in c.items():
    res += v*(v-1)//2
print(res + c[0])

Submission status: Runtime Error

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]
if p in [2,5]:
    x = 0
    for i in range(n):
        if int(s[i])%p==0:
            x += n-i
    print(x)
    exit()

q = 1
for i in range(n):
    x = int(s[i])
    r = q*x
    acc[i+1] = (acc[i]+r)%p
    ddprint(f"i {i} x {x} r {r} q {q} ai {acc[i+1]}")
    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: Runtime Error

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

Submission status: Runtime Error

Solution code:
import collections

s = input()
q = int(input())
rev = 0
ans = collections.deque(['S'])

for _ in range(q):
  query = list(input().split())
  if int(query[0]) == 1:
    rev += 1
  else:
    if int(query[1]) == 1:      # 先頭
      if rev%2 == 0:
        ans.appendleft(query[2])
      else:
        ans.append(query[2])
    else:                       # 末尾
      if rev%2 == 0:
        ans.append(query[2])
      else:
        ans.appendleft(query[2])

ans = ''.join(ans)
mes = ans.replace("S", s)
if rev%2 == 0:
  print(mes)
else:
  print(mes[::-1])

Submission status: Runtime Error

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

s = input()

if 10 % p == 0:
    ans = sum(i + 1 for i, x in enumerate(s) if int(x) % p == 0)
    print(ans)
else:
    li = [0] * (n + 1)
    counter = {}
    for i, x in enumerate(s[::-1]):
        li[i+1] = (li[i] + (int(x) * (10**(i+1)) % p)) % p
        counter[li[i+1]] = counter.get(li[i+1], 0) + 1
    ans = 0
    ans = sum(v * (v - 1) for v in counter.values()) // 2
    ans += counter[0]
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

s = input()

if 10 % p == 0:
    ans = sum(i + 1 for i, x in enumerate(s) if x % p == 0)
    print(ans)
else:
    li = [0] * (n + 1)
    for i, x in enumerate(s[::-1]):
        li[i+1] = (li[i] + (int(x) * (10**(i+1)) % p)) % p

    ans = 0
    c = Counter(li[1:])
    ans = sum(v * (v - 1) for v in c.values()) // 2
    ans += c[0]
    print(ans)

Submission status: Runtime Error

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

res = 0
if P == 2 or P == 5:
    for i in range(N):
        if int(S[i]) % P == 0:
            res += i + 1
else:
    mp = [0]*len(S)
    mp[0] = 1
    cur = 0
    p10 = 1
    for c in S[::-1]:
        cur = (cur + int(c)*p10) % P
        res += mp[cur]
        mp[cur] += 1
        p10 *= 10
        p10 %= P

print(res)

Submission status: Runtime Error

Solution code:
import numpy as np
nandp=list(map(int, input().split()))
sstr=input()
s=[]
p=nandp[1]
for i in range(nandp[0]):
    s.append(int(sstr[i]))
answer=np.zeros((nandp[0],nandp[0]))
counter=0
for kk in range(nandp[0]):
    answer[0][kk]=s[kk]%p
    if(answer[0][kk]==0):
        counter+=1
for j in range(1,nandp[0]):
    for k in range(0,nandp[0]-j):
        answer[j][k]=(answer[j-1][k]*10+answer[0][j+k])%p
        if(answer[j][k]==0):
            counter+=1
            #print(j)
            #print(k)
print(counter)

Submission status: Runtime Error

Solution code:
p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(s, 1) if int(x) % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t = 0
  for x in reversed(s):
    t = (t + int(x) * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) for i in d) // 2
print(r)

Submission status: Runtime Error

Solution code:
p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(s, 1) if int(x) % p == 0)
else:
  d = [1] + [0] * (p - 1)
  s, y = 0, 1
  for x in reversed(s):
    t = (t + int(x) * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Submission status: Runtime Error

Solution code:
p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(s, 1) if int(x) % p == 0)
else:
  d = [1] + [0] * (p - 1)
  s, y = 0, 1
  for x in reversed(s):
    s = (s + int(x) * y) % p
    d[s] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Submission status: Runtime Error

Solution code:
# li = [[0] * 4 for i in range(3)]

# A = list.map(int, input().split())

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

S = input()


memo = {}


def dfs(n):
    # print(n)
    if n in memo:
        return memo[n]

    i = n + 1
    while i <= N:
        temp_int = int(S[n:i])
        # print(temp_int)
        if temp_int % P == 0:
            memo[n] = 1 + dfs(i)
            return memo[n]

        i += 1
    return 0


ans = 0
for i in range(N):
    temp = dfs(i)
    ans += temp

print(ans)

Submission status: Runtime Error

Solution code:
p = int(input().split()[1])
s = input()
#if 10 % p:
#  s = reversed(s)
a = enumerate(s, 1)
if 10 % p == 0:
  r = sum(i for i, x in a if x % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for i, x in a:
    t = (t + x * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Submission status: Runtime Error

Solution code:
p = int(input().split()[1])
s = input()
if 10 % p:
  s = reversed(s)
a = enumerate(s, 1)
if 10 % p == 0:
  r = sum(i for i, x in a if x % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for i, x in a:
    t = (t + x * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Submission status: Runtime Error

Solution code:
p = int(input().split()[1])
a = list(map(int, input())
if 10 % p == 0:
  r = sum(i for i, x in enumerate(a, 1) if x % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for i, x in enumerate(reversed(a), 1):
    t = (t + x * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Submission status: Runtime Error

Solution code:
I = lambda s:map(int, s)

p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(I(s), 1) if x % p == 0)
else:
  d = [1] + [0] * 9
  t, y = 0, 1
  for i, x in enumerate(I(reversed(s)), 1):
    t = (t + x * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
from collections import Counter

p = int(input().split()[1])
a = list(map(int, input())
if 10 % p == 0:
  r = sum(i for i, x in enumerate(a, 1) if x % p == 0)
else:
  a = accumulate(x * pow(10, i, p) for i, x in enumerate(reversed(a), 1))
  c = Counter(x % p for x in a) 
  c[0] += 1
  r = sum(i * (i - 1) // 2 for i in c.values())
print(r)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
from collections import Counter

p = int(input().split()[1])
a = map(int, input())
if 10 % p == 0:
  r = sum(i for i, x in enumerate(a, 1) if x % p == 0)
else:
  a = accumulate(x * pow(10, i, p) for i, x in enumerate(reversed(a), 1))
  c = Counter(x % p for x in a) 
  c[0] += 1
  r = sum(i * (i - 1) // 2 for i in c.values())
print(r)

Submission status: Runtime Error

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

if P!=2 and P!=5:
    for i in range(0,N):
        chec=S[i]
        j=0
        while i+j<N:
          　　　chec%=P
                if chec==0:
                    count+=1
                j+=1
                if i+j<N:
                    chec=chec*10+S[i+j]
if P==2:
    for i in range(N):
        if S[i]%2==0:
            count+=i+1
if P==5:
    for i in range(N):
        if S[i]==0 or S[i]==5:
            count+=i+1
print(count)

Submission status: Runtime Error

Solution code:
N, P = map(int, input().split())
S = input()
ans = 0
rui = [0] * (N + 1)
if 10 % P == 0:
    for i in range(len(S)):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    exit()

t = 1
for i in reversed(range(N)):
    tmp = int(S[i]) * t % P
    rui[i] = (rui[i + 1] + tmp) % P
    t *= 10
    t %= P

cnt = [0] * (N + 1)
for i in reversed(range(N + 1)):
    ans += cnt[rui[i]]
    cnt[rui[i]] += 1
print(ans)

Submission status: Runtime Error

Solution code:
N, P = map(int, input().split())
S = input()
ans = 0
rui = [0] * (N + 1)
if 10 % P == 0:
    for i in range(len(S)):
        if int(S[i]) % P == 0:
            ans += i + 1
    print(ans)
    exit()

t = 1
for i in reversed(range(N)):
    tmp = int(S[i]) * t % P
    rui[i] = (rui[i + 1] + tmp) % P
    t *= 10
    t %= P

cnt = [0] * N
for i in reversed(range(N + 1)):
    ans += cnt[rui[i]]
    cnt[rui[i]] += 1
print(ans)

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    (n, p) = map(int, input().split())
    s = input()
    a = []
    for i in range(len(s)):
        for j in range(len(s)):
            if s[i:j+1] != '': a.append(s[i:j+1])
    print(len([e for e in a if int(e) % p == 0]))

Submission status: Runtime Error

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

ans = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
  	mod = [-1 for i in range(p)]
	mod[0] = 0
    mp = 0
    m10 = 1
    for i in range(n-1, -1, -1):
        mp = (mp + int(s[i]) * m10) % p
        mod[mp] += 1
        m10 = (10 * m10) % p

    for m in mod:
        ans += m*(m+1)//2

print(ans)

Submission status: Runtime Error

Solution code:
n,p=map(int,input().split())
s=input()
if p==2 or p==5:
  while(true):

Submission status: Runtime Error

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

count=0
if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            count+=i+1
elif p==5:
    for i in range(n):
        if int(s[i])%5==0:
            count+=i+1
else:
    u=[]
    num=0
    for i in range(n):
        u.append(int(s[i:n]%p))
    u.append(0)
    for i in range(n):
        for j in range(i,n):
            if (u[i]-u[j+1])%p==0:
                count+=1
print(count)

Submission status: Runtime Error

Solution code:
N,P = map(int,input().split())
S = list(map(int,list(input())))
S=S[::-1]
ans = 0
from collections import Counter
if P==2:
  l = [0,2,4,6,8]
  for i,s in enumerate(S):
    if s in l:
      ans+=N-i
elif P==5:
  l=[0,5]
  for i,s in enumerate(S):
    if s in l:
      ans+=N-i

else:
  l = [0]*(N+2)
  for i in range(N):
    l[i+1]=l[i]
    l[i+1]+=(S[i]*10**i)%P
    l[i+1]%=P
    
  c = Counter(l)
  l = list(c.values())
  l = sorted(l)
  for i in l:
    if l==1:
      continue
    else:
      ans+=c*(c-1)//2
      
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
n,p= map(int,input().split())
s = input()
ans = 0
if p == 2 or p == 5:#右端を固定すれば2,5で割り切れるならそれ以降は全部いけるのでn-iをたす
    for i in range(n):
        if int(s[-1-i]) % p == 0:
            ans += n-i
    print(ans)
    exit()
else:
  s = s[::-1]#反転させてしたからみる
  cnt = [0]*p # pで割った時のあまり
  cnt[0] = 1 # 0の時はなにも取らない時全体も入るので+1する
  for i,c in enumerate(map(int,s)):#enumerateでiterator i , s[i]の値cを同時に取得
    k += (c*pow(10,i,p) + cnt[i-1])%p
    cnt[k] += 1
  for i in range(p):
    ans += cnt[i]*(cnt[i]-1) //2
  print(ans)

Submission status: Runtime Error

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

r_circ = []
v = 1
while True:
    r = v % P
    if r in r_circ:
        break
    r_circ.append(r)
    v *= 10

ans = 0
if P in (2, 5):
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i+1
else:
    pr = 0
    rcntmap = [0] * P
    rcntmap[0] = 1  # r - 0 patten
    for i in reversed(range(len(S))):
        d = int(S[i])
        r = (d * r_circ[(len(S)-1-i) % len(r_circ)] + pr) % P
        #r = int(S[i:]) % P
        ans += rcntmap[r]
    
        rcntmap[r] += 1
        pr = r

print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
n,p= map(int,input().split())
s = input()
ans = 0
if p == 2 or p == 5:#右端を固定すれば2,5で割り切れるならそれ以降は全部いけるのでn-iをたす
    for i in range(n):
        if int(s[-1-i]) % p == 0:
            ans += n-i
    print(ans)
    exit()
else:
  s = s[::-1]#反転させてしたからみる
  cnt = [0]*p # pで割った時のあまり
  cnt[0] = 1 # 0の時はなにも取らない時全体も入るので+1する
  for i,c in enumerate(map(int,s)):#enumerateでiterator i , s[i]の値cを同時に取得
    k = c*pow(10,i) + cnt[i-1]
    k = k % p
  for i in range(p):
    ans += cnt[i]*(cnt[i]-1) //2
  print(ans)

Submission status: Runtime Error

Solution code:
import sys


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return [int(x) for x in sys.stdin.readline().strip().split()]


def main():
    n, p = _ia()
    u = [1 if i == 0 else 0 for i in range(p)]
    s = _i()
    cnt = 0
    if p == 2 or p == 5:
        for i, c in enumerate(s):
            if int(c) % p == 0:
                cnt += i + 1
        return cnt

    m = 10
    for _ in range(n):
        ui = (s % m) % p
        cnt += u[ui]
        u[ui] += 1
        m *= 10

    return cnt


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

Submission status: Runtime Error

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

def make_num(s):
    num = []
    for i in range(1,n+1): #桁数を指定
        num_bef = []
        for j in range(n-i): #先頭の要素を指定
            for k in range(j,j + i):
                num_bef.append(s[k])
            num_bef1 = ''.join(num_bef)
            num.append(num_bef1)
        print(num)
    return num

if __name__ == '__main__':
    count = 0
    num_list = set(make_num(s))
    for a_num in num_list:
        if int(a_num) % p == 0:
            print(a_num)
            count += 1
    print(count)

Submission status: Runtime Error

Solution code:
n,p=map(int,input().split())
s=input()
def U(x):
    return int(s[x:])
if p in [2,5]:
    keta=0
    ans=0
    for i in range(n):
        keta+=1
        if int(s[i])%p==0:
            ans+=keta
    print(ans)
    exit()


ikeru=[0 for i in range(p)
for i in range(n):
    a=U(i) % p
    ikeru[a]+=1
ans=0
for t in ikeru:
    if t in [0,1]:continue
    ans+= t*(t-1)//2
print(ans)

Submission status: Runtime Error

Solution code:
from scipy.special import comb
from collections import defaultdict

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

if p == 2 or p == 5:
    count = 0
    digits = '02468' if p == 2 else '05'
    for i, x in enumerate(S, 1):
        if x in digits:
            count += i
    print(count)
else:
    counter = [0]*p
    for i in range(n-1, -1, -1):
        counter[int(S[i:]) % p] += 1
    print(counter[0] + sum(int(comb(i, 2)) for i in counter))

Submission status: Runtime Error

Solution code:
n,p=map(int,input().split())
s=input()
def U(x):
    return int(s[x:])
if p in [2,5]:
    keta=0
    ans=0
    for i in range(n):
        keta+=1
        if int(s[i])%p==0:
            ans+=keta
    print(ans)
    exit()

ans=0
ikeru=[0 for i in range(n)]
for i in range(n):
    a=U(i) % p
    if a==0:ans+=1
    ikeru[a]+=1

for t in ikeru:
    if t in [0,1]:continue
    ans+= t*(t-1)//2
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from math import gcd

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

if gcd(10, P) > 1:
    ans = 0
    for i in range(len(S)):
        s = int(S[i])
        if s % P == 0:
            ans += (i+1)
    print(ans)
else:
    h = defaultdict(int)
    ans = 0
    for i in range(len(S)-1, -1, -1):
        s = int(S[i:])
        m = s % P
        if m == 0:
            h[m] += 1
            ans += h[m]
        else:
            ans += h[m]
            h[m] += 1

    print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8

S = input()
Q = int(input())

query = []

for i in range(Q):
    query.append(input().split())


bool = True
pre =''
suf =''

for i in query:
    if len(i) == 1:
        bool = not bool

    else:
        if i[1]=="1":
            if bool:
                pre = i[2]+pre
            else:
                suf += i[2]
        else:
            if bool:
                suf += i[2]
            else:
                pre = i[2]+pre

S = pre+ S +suf
print(S) if bool else print(S[::-1])

Submission status: Runtime Error

Solution code:
import numpy as np
N, P = map(int, input().split())
S = input()
n = []
for i in range(N+1):
    n+=[S[i:j] for j in range(i, N+1) if i!=j]
n = np.array(n).astype('int64')
n = n%P
print(np.count_nonzero(n == 0))

Submission status: Runtime Error

Solution code:
def main():
    n, p = map(int, input().split())
    s = input()
    l = []
    for i in range(0,n):
        tmp = s[i]
        l.append(tmp)
        for j in range(1, n - i):
            tmp = tmp + s[i+j]
            l.append(tmp)
    li = [int(i) % p for i in l]

    print(li.count(0))
main()

Submission status: Runtime Error

Solution code:
n, p = map(int, input().split())
s = input()
count = 0
if p == 2 or p == 5:
  for i in s:
    if int(i) % p == 0:
      count += i + 1
  print(count)
else:
  mod = [0] * p
  mod[0] = 1
  tmp = 0
  ten = 1
  for i in s[::-1]:
    ten = ten * 10 % p
    tmp = (tmp + int(i) * ten) % p
    mod[tmp] += 1
  for m in mod:
    count += m * (m - 1) // 2
  print(count)

Submission status: Runtime Error

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

if p == 2 or p == 5:
    ans = 0
    s = map(int, s)
    for i, c in enumerate(s):
        if c % p == 0:
            ans += i + 1
    print(ans)
else:
    s = s[::-1]
    cnt = [0] * p
    k = 0
    cnt[k] = 1
    for i, c in enumerate(map(int(s))):
        k = (c * (10**i) + k) % p
        cnt[k] += 1

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