結果

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

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

sys.set_int_max_str_digits(10**5)

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

mod=10**9+7
POW10=[1]
for i in range(10**5+2):
    POW10.append(POW10[-1]*10%24)

A-=1

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

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

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

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

        for i in range(2):
            for j in range(2):
                for k in range(24):
                    now=DP[i+j*2+k*4]
                    if now==0:
                        continue

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

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

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


                            NDP[i+(j|three)*2+(k+plus)%24*4]=(NDP[i+(j|three)*2+(k+plus)%24*4]+DP[i+j*2+k*4])%mod
                        
        DP=NDP

    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*2+k*4]
                else:
                    if k%3==0 and k%8!=0:
                        ANS+=DP[i+j*2+k*4]
                ANS%=mod
    return ANS

ANS=calc(A)
ANS2=calc(B)

print((ANS2-ANS)%mod)
0