Buggy python submission (verdict: Time Limit Exceeded):





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


"""
たとえばSが 123456789 だとすると
3456 = (3456789 - 789) // 1000
と表せる。
これがPで割り切れる場合、基本的には 3456789 と 789 がPで割り切れるとよい。
これはPと 10**x が互いに素の場合。
なので、10**x とPが互いに素の場合は、
・S[l:]をPで割った時余りがXXXになるものが何個、という情報を、Sの右端から集めていく。ただし、
・あるindexのlのS[l:]を見ているときに、その部分をPで割って余りがKになるなら、そのlに対してlより右にあるrについて、
　S[r:]をPで割った余りがKになるようにrを選んでS[l:r]を作ると、Pで割り切れる数字が得られる。その時点でのmod P = Kの個数に対応する。
　ただし、rに何も選ばない場合（lから端までを数字にする場合）もあるので、これも考慮に入れる。

Pが10と互いに素でない場合は、2と5がありうる。
これについて、それぞれ末尾が2の倍数か5の倍数であれば割り切れるので、
Sを左から見ていって、その数字が見つかれば、そのindexをふくむ左の位置で数字を作ればPで割れる数字ができる
"""

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

else:
    mod_P = [0] * P
    mod_P[0] += 1

    curr = 0
    for i in range(N):
        curr += int(S[N-1-i]) * 10**i
        ans += mod_P[curr % P]
        mod_P[curr % P] += 1

print(ans)

Fixed submission:



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

ans = 0
mod_P = [0] * P
mod_P[0] += 1
# P が 10と互いに素でないなら、U_i - U_jのうちのU_jがPで割り切れるだけでよい
if P in [2,5]:
    
    for i in range(N):
            """
            今見ているiかそれより左側にある物をU_iとして選択する場合に割り切れるようになるので、
            いまのiを含む左にあるものの個数を足す
            """
            if int(S[i]) % P == 0:
                ans += i+1
    
    print(ans)

else:
    """
    右端から見て、
    ([右端からi番目までの数字] - [右端からj番目までの数字]) % Pが0になるならOK
    [右端からi番目までの数字] % P = X となるなら、[右端からj番目までの数字] % P = X であれば割り切れる
    なので、i番目までを見ているときに、そこより右側で、余りがi番目までをPで割った時と同じになる個数が分かればよい。

    毎回律義にi番目までを数値化して、mod P をとってるとTLEになるので、
    右からi番目の数字 10 ** i + それまで
    の形で積み重ねていく。
    また、余りの問題なので、余りの世界で現在値を保存しておく(今回みたいな大きな値について毎回modをとるとめちゃくちゃ遅い)

    例１の3543と3のときのように、
    うしろから最後まで見切って3543について考えるとする。
    このとき、、
    ・端までとるU_5：U=3543
    ・右端の3だけのU_4：U=354
    ・543のU_1：U=3
    の３パターンで余りを0にしうる
    みたいなかたち
    """
    curr = 0
    for i in range(N):
        curr = int(S[N-1-i]) * pow(10, i, P) + curr
        curr %= P
        ans += mod_P[curr]
        mod_P[curr] += 1
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):


def main():

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


    d = {}


    ans = 0
    for l in range(N):
        for r in range(l,N):
            if l == r:
                if int(S[l]) in d:
                    if d[int(S[l])] == 0:
                        ans += 1 
                else:
                    d[int(S[l])] = int(S[l]) % P
                    if d[int(S[l])] == 0:
                        ans += 1 
            else:
                if int(S[l:r+1]) in d:
                    if d[int(S[l:r+1])] == 0:
                        ans += 1 
                else:
                    d[int(S[l:r+1])] = int(S[l:r+1]) % P
                    if d[int(S[l:r+1])] == 0:
                        ans += 1 

    print(ans)


if __name__ == "__main__":
    main()

Fixed submission:



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

ans = 0
mod_P = [0] * P
mod_P[0] += 1
# P が 10と互いに素でないなら、U_i - U_jのうちのU_jがPで割り切れるだけでよい
if P in [2,5]:
    
    for i in range(N):
            """
            今見ているiかそれより左側にある物をU_iとして選択する場合に割り切れるようになるので、
            いまのiを含む左にあるものの個数を足す
            """
            if int(S[i]) % P == 0:
                ans += i+1
    
    print(ans)

else:
    """
    右端から見て、
    ([右端からi番目までの数字] - [右端からj番目までの数字]) % Pが0になるならOK
    [右端からi番目までの数字] % P = X となるなら、[右端からj番目までの数字] % P = X であれば割り切れる
    なので、i番目までを見ているときに、そこより右側で、余りがi番目までをPで割った時と同じになる個数が分かればよい。

    毎回律義にi番目までを数値化して、mod P をとってるとTLEになるので、
    右からi番目の数字 10 ** i + それまで
    の形で積み重ねていく。
    また、余りの問題なので、余りの世界で現在値を保存しておく(今回みたいな大きな値について毎回modをとるとめちゃくちゃ遅い)

    例１の3543と3のときのように、
    うしろから最後まで見切って3543について考えるとする。
    このとき、、
    ・端までとるU_5：U=3543
    ・右端の3だけのU_4：U=354
    ・543のU_1：U=3
    の３パターンで余りを0にしうる
    みたいなかたち
    """
    curr = 0
    for i in range(N):
        curr = int(S[N-1-i]) * pow(10, i, P) + curr
        curr %= P
        ans += mod_P[curr]
        mod_P[curr] += 1
    print(ans)