結果

問題 No.189 SUPER HAPPY DAY
コンテスト
ユーザー sasa8uyauya
提出日時 2024-11-17 13:22:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,657 ms / 5,000 ms
コード長 848 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 388 ms
コンパイル使用メモリ 81,964 KB
実行使用メモリ 87,888 KB
最終ジャッジ日時 2024-11-17 13:23:24
合計ジャッジ時間 53,765 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

s,t=input().split()
M=10**9+9
L=202
s=s.zfill(L)
t=t.zfill(L)
q=[[[0]*(L*20+1) for j in range(2)] for i in range(2)]
q[0][0][0]=1
for p in range(L):
  c1=int(s[p])
  c2=int(t[p])
  nq=[[[0]*(L*20+1) for j in range(2)] for i in range(2)]
  for d in range(-L*10,L*10+1):
    for q1 in range(10):
      for q2 in range(10):
        if q[0][0][d]!=0:
          if q1<=c1 and q2<=c2:
            nq[q1<c1][q2<c2][d+q1-q2]+=q[0][0][d]
        if q[0][1][d]!=0:
          if q1<=c1:
            nq[q1<c1][1][d+q1-q2]+=q[0][1][d]
        if q[1][0][d]!=0:
          if q2<=c2:
            nq[1][q2<c2][d+q1-q2]+=q[1][0][d]
        if q[1][1][d]!=0:
          nq[1][1][d+q1-q2]+=q[1][1][d]
  q=nq
  for d in range(-L*10,L*10+1):
    q[0][0][d]%=M
    q[0][1][d]%=M
    q[1][0][d]%=M
    q[1][1][d]%=M
print((q[0][0][0]+q[0][1][0]+q[1][0][0]+q[1][1][0]-1)%M)
0