結果

問題 No.260 世界のなんとか3
コンテスト
ユーザー titia
提出日時 2025-12-28 04:48:23
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 3,380 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 331 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 19,752 KB
最終ジャッジ日時 2025-12-28 04:48:28
合計ジャッジ時間 4,132 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

sys.set_int_max_str_digits(10**6)

A,B=map(int,input().split())

mod=10**9+7

A-=1

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

DP=[[[0]*24 for i in range(2)] for j in range(2)]
# DP[i][j][k] i=0で一致、i=1で不一致
# j=0で3を含まない。j=1で3を含む
# k:24で割った余り

DP[0][0][0]=1
LEN=len(A)

for keta in range(len(A)):
    x=A[keta]
    NDP=[[[0]*24 for i in range(2)] for j in range(2)]

    for i in range(2):
        for j in range(2):
            for k in range(24):
                now=DP[i][j][k]

                if i==0:
                    for l in range(x+1):
                        if l==3:
                            three=1
                        else:
                            three=0
                        plus=l*pow(10,LEN-keta-1,24)%24

                        if l==x:
                            ic=0
                        else:
                            ic=1

                        NDP[ic][j|three][(k+plus)%24]=(NDP[ic][j|three][(k+plus)%24]+DP[i][j][k])%mod
                else:
                    for l in range(10):
                        if l==3:
                            three=1
                        else:
                            three=0
                        plus=l*pow(10,LEN-keta-1,24)%24


                        NDP[i][j|three][(k+plus)%24]=(NDP[i][j|three][(k+plus)%24]+DP[i][j][k])%mod
                    
    DP=NDP
    #print(DP)

ANS=0
for i in range(2):
    for j in range(2):
        for k in range(24):
            if j==1 and k%8!=0:
                ANS+=DP[i][j][k]
            else:
                if k%3==0 and k%8!=0:
                    ANS+=DP[i][j][k]

#print(ANS)

DP=[[[0]*24 for i in range(2)] for j in range(2)]
# DP[i][j][k] i=0で一致、i=1で不一致
# j=0で3を含まない。j=1で3を含む
# k:24で割った余り

DP[0][0][0]=1
LEN=len(B)

for keta in range(len(B)):
    x=B[keta]
    NDP=[[[0]*24 for i in range(2)] for j in range(2)]

    for i in range(2):
        for j in range(2):
            for k in range(24):
                now=DP[i][j][k]

                if i==0:
                    for l in range(x+1):
                        if l==3:
                            three=1
                        else:
                            three=0
                        plus=l*pow(10,LEN-keta-1,24)%24

                        if l==x:
                            ic=0
                        else:
                            ic=1

                        NDP[ic][j|three][(k+plus)%24]=(NDP[ic][j|three][(k+plus)%24]+DP[i][j][k])%mod
                else:
                    for l in range(10):
                        if l==3:
                            three=1
                        else:
                            three=0
                        plus=l*pow(10,LEN-keta-1,24)%24


                        NDP[i][j|three][(k+plus)%24]=(NDP[i][j|three][(k+plus)%24]+DP[i][j][k])%mod
                    
    DP=NDP
    #print(DP)

ANS2=0
for i in range(2):
    for j in range(2):
        for k in range(24):
            if j==1 and k%8!=0:
                ANS2+=DP[i][j][k]
            else:
                if k%3==0 and k%8!=0:
                    ANS2+=DP[i][j][k]

print((ANS2-ANS)%mod)
0