結果
問題 | No.189 SUPER HAPPY DAY |
ユーザー |
![]() |
提出日時 | 2015-05-11 00:19:10 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 1,461 ms / 5,000 ms |
コード長 | 1,056 bytes |
コンパイル時間 | 253 ms |
コンパイル使用メモリ | 6,912 KB |
実行使用メモリ | 60,324 KB |
最終ジャッジ日時 | 2024-07-05 22:11:01 |
合計ジャッジ時間 | 18,275 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
M,D=map(int,raw_input().split()) mod=1000000009 def getTable(M): dp1=[[[0 for i in range(2)] for j in range(1810)] for k in range(202)] 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(1809,-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,1809): #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