結果

問題 No.189 SUPER HAPPY DAY
コンテスト
ユーザー yaoshimax
提出日時 2015-05-11 00:13:22
言語 PyPy2
(7.3.15)
結果
RE  
実行時間 -
コード長 1,056 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 157 ms
コンパイル使用メモリ 77,436 KB
最終ジャッジ日時 2025-12-03 15:06:49
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 RE * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

M,D=map(int,raw_input().split())
mod=1000000009

def getTable(M):
    dp1=[[[0 for i in range(2)] for j in range(1800)] for k in range(201)]
    Mb=1
    dp1[0][0][0]=1
    while Mb*10<=M:
        Mb*=10
    ind=0
    while Mb>0:
        b=M/Mb
        for s in range(1799,-1,-1):
            if dp1[ind][s][0]>0:
                for i in range(b):
                    dp1[ind+1][s+i][1]+=dp1[ind][s][0]
                    dp1[ind+1][s+i][1]%=mod
                dp1[ind+1][s+b][0]+=dp1[ind][s][0]
                dp1[ind+1][s+b][0]%=mod
            if dp1[ind][s][1]>0:
                for i in range(10):
                    dp1[ind+1][s+i][1]+=dp1[ind][s][1]
                    dp1[ind+1][s+i][1]%=mod
        ind+=1
        M%=Mb
        Mb/=10
    return dp1[ind]

dpM=getTable(M)
dpD=getTable(D)
ans=0
for i in range(1,1800):
    #if dpM[i][0]!=0 or dpM[i][1]!=0 or dpD[i][0]!=0 or dpD[i][1]!=0:
    #    print  i,":",dpM[i][0],"+",dpM[i][1],"...",dpD[i][0],"+",dpD[i][1]
    ans+=(dpM[i][0]+dpM[i][1])*(dpD[i][0]+dpD[i][1])
    ans%=mod
print ans
0