結果
問題 | No.1407 Kindness |
ユーザー |
![]() |
提出日時 | 2021-02-26 22:56:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 156 ms / 2,000 ms |
コード長 | 527 bytes |
コンパイル時間 | 187 ms |
コンパイル使用メモリ | 82,856 KB |
実行使用メモリ | 99,900 KB |
最終ジャッジ日時 | 2024-10-02 15:41:37 |
合計ジャッジ時間 | 4,198 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
from itertools import productN = input()mod=10**9+7def count(a):n = len(a)dp=[[0] * 2 for i in range(n+1)]dp[0][0]=1for i, less in product(range(n), (0,1)):max_d = 9 if less else int(a[i])for d in range(max_d+1):less_ = less or d < max_ddp[i + 1][less_] = (dp[i + 1][less_] + dp[i][less]*d)%modreturn dpdp = count(N)ans = dp[-1][0]+dp[-1][1]dp = count('9'*(len(N)-1))for i in range(len(N)):ans = (ans+dp[i][0]+dp[i][1])%modprint((ans-1)%mod)