結果
問題 | No.1407 Kindness |
ユーザー |
|
提出日時 | 2022-09-27 07:28:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 441 ms / 2,000 ms |
コード長 | 812 bytes |
コンパイル時間 | 282 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 171,384 KB |
最終ジャッジ日時 | 2024-12-22 16:29:44 |
合計ジャッジ時間 | 9,174 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
N = list(map(int, list(input())))n = len(N)mod = 10**9 + 7DP = [[[0, 0] for _ in range(10)] for _ in range(n)]for i in range(N[0]):DP[0][i][1] = iDP[0][N[0]][0] = N[0]for i in range(n - 1):for j in range(1, 10):for k in range(1, 10):if j == N[i]:if k == N[i + 1]:DP[i + 1][k][0] += DP[i][j][0] * kDP[i + 1][k][0] %= modelif k < N[i + 1]:DP[i + 1][k][1] += DP[i][j][0] * kDP[i + 1][k][1] % modDP[i + 1][k][1] += DP[i][j][1] * kDP[i + 1][k][1] %= modfor k in range(1, 10):DP[i + 1][k][1] += kans = 0for i in range(10):ans += DP[n - 1][i][0]ans %= modans += DP[n - 1][i][1]ans %= modprint(ans)