結果

問題 No.189 SUPER HAPPY DAY
ユーザー yaoshimaxyaoshimax
提出日時 2015-05-11 00:13:22
言語 Python2
(2.7.18)
結果
RE  
実行時間 -
コード長 1,056 bytes
コンパイル時間 606 ms
コンパイル使用メモリ 6,520 KB
実行使用メモリ 59,332 KB
最終ジャッジ日時 2023-09-20 01:50:35
合計ジャッジ時間 19,933 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 445 ms
54,900 KB
testcase_01 AC 460 ms
54,880 KB
testcase_02 AC 452 ms
54,708 KB
testcase_03 AC 455 ms
54,712 KB
testcase_04 AC 454 ms
54,840 KB
testcase_05 AC 459 ms
54,892 KB
testcase_06 AC 458 ms
54,704 KB
testcase_07 AC 466 ms
54,892 KB
testcase_08 AC 467 ms
54,780 KB
testcase_09 AC 475 ms
54,736 KB
testcase_10 AC 466 ms
54,784 KB
testcase_11 AC 470 ms
54,896 KB
testcase_12 AC 455 ms
54,900 KB
testcase_13 AC 754 ms
56,652 KB
testcase_14 AC 869 ms
56,880 KB
testcase_15 AC 929 ms
58,572 KB
testcase_16 AC 996 ms
59,132 KB
testcase_17 AC 1,019 ms
58,836 KB
testcase_18 AC 882 ms
58,140 KB
testcase_19 AC 1,075 ms
57,624 KB
testcase_20 AC 623 ms
56,252 KB
testcase_21 AC 611 ms
55,832 KB
testcase_22 AC 494 ms
54,936 KB
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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