結果

問題 No.315 世界のなんとか3.5
コンテスト
ユーザー titia
提出日時 2026-06-30 07:36:24
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,329 ms / 2,000 ms
コード長 4,272 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,667 ms
コンパイル使用メモリ 84,992 KB
実行使用メモリ 120,536 KB
最終ジャッジ日時 2026-06-30 07:36:48
合計ジャッジ時間 19,707 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

sys.set_int_max_str_digits(10**6)

mod=10**9+7

A,B,P=list(map(int,input().split()))
A-=1

A=list(map(int,list(str(A))))
B=list(map(int,list(str(B))))

DP=[[[0]*3 for i in range(2)] for j in range(2)]

# DP[i][j][k]で桁が一致, 3が既に登場, 3で割った余り

DP[1][0][0]=1

THREE=[0]*(10**5)
for i in range(10**5):
    if "3" in str(i):
        THREE[i]=1

for i in range(len(A)-5):
    NDP=[[[0]*3 for i in range(2)] for j in range(2)]

    a=A[i]

    for i in range(2):
        for j in range(2):
            for k in range(3):
                if i==1:
                    for to in range(a+1):
                        if to==a:
                            if to==3:
                                NDP[1][1][(k+to)%3]=(NDP[1][1][(k+to)%3]+DP[i][j][k])%mod
                            else:
                                NDP[1][j][(k+to)%3]=(NDP[1][j][(k+to)%3]+DP[i][j][k])%mod

                        else:
                            if to==3:
                                NDP[0][1][(k+to)%3]=(NDP[0][1][(k+to)%3]+DP[i][j][k])%mod
                            else:
                                NDP[0][j][(k+to)%3]=(NDP[0][j][(k+to)%3]+DP[i][j][k])%mod
                else:
                    for to in range(10):
                        if to==3:
                            NDP[0][1][(k+to)%3]=(NDP[0][1][(k+to)%3]+DP[i][j][k])%mod
                        else:
                            NDP[0][j][(k+to)%3]=(NDP[0][j][(k+to)%3]+DP[i][j][k])%mod

    DP=NDP

limit=0

c=1
for i in range(5):
    if len(A)-1-i>=0:
        limit+=A[len(A)-1-i]*c
    c*=10
    
ANS=0
for i in range(2):
    for j in range(2):
        for k in range(3):
            if i==1:
                for l in range(limit+1):
                    if l%P==0:
                        continue
                    else:
                        if j==1 or (k+l)%3==0 or THREE[l]==1:
                            ANS=(ANS+DP[i][j][k])%mod
            else:
                for l in range(10**5):
                    if l%P==0:
                        continue
                    else:
                        if j==1 or (k+l)%3==0 or THREE[l]==1:
                            ANS=(ANS+DP[i][j][k])%mod

#print(DP,ANS)
ANS0=ANS

DP=[[[0]*3 for i in range(2)] for j in range(2)]
DP[1][0][0]=1

for i in range(len(B)-5):
    NDP=[[[0]*3 for i in range(2)] for j in range(2)]

    a=B[i]

    for i in range(2):
        for j in range(2):
            for k in range(3):
                if i==1:
                    for to in range(a+1):
                        if to==a:
                            if to==3:
                                NDP[1][1][(k+to)%3]=(NDP[1][1][(k+to)%3]+DP[i][j][k])%mod
                            else:
                                NDP[1][j][(k+to)%3]=(NDP[1][j][(k+to)%3]+DP[i][j][k])%mod

                        else:
                            if to==3:
                                NDP[0][1][(k+to)%3]=(NDP[0][1][(k+to)%3]+DP[i][j][k])%mod
                            else:
                                NDP[0][j][(k+to)%3]=(NDP[0][j][(k+to)%3]+DP[i][j][k])%mod
                else:
                    for to in range(10):
                        if to==3:
                            NDP[0][1][(k+to)%3]=(NDP[0][1][(k+to)%3]+DP[i][j][k])%mod
                        else:
                            NDP[0][j][(k+to)%3]=(NDP[0][j][(k+to)%3]+DP[i][j][k])%mod

    DP=NDP


limit=0

c=1
for i in range(5):
    if len(B)-1-i>=0:
        limit+=B[len(B)-1-i]*c
    c*=10
    
ANS=0
for i in range(2):
    for j in range(2):
        for k in range(3):
            if i==1:
                for l in range(limit+1):
                    if l%P==0:
                        continue
                    else:
                        if j==1 or (k+l)%3==0 or THREE[l]==1:
                            ANS=(ANS+DP[i][j][k])%mod
            else:
                for l in range(10**5):
                    if l%P==0:
                        continue
                    else:
                        if j==1 or (k+l)%3==0 or THREE[l]==1:
                            ANS=(ANS+DP[i][j][k])%mod
                
                    

print((-ANS0+ANS)%mod)
0