結果
問題 | 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 |
コンパイル時間 | 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 |
ソースコード
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)