結果
問題 | No.1407 Kindness |
ユーザー |
👑 ![]() |
提出日時 | 2021-02-26 21:32:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 572 bytes |
コンパイル時間 | 207 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 72,448 KB |
最終ジャッジ日時 | 2024-10-02 14:05:11 |
合計ジャッジ時間 | 2,836 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
"""桁dpdp[v][flag] = v桁目まで見て、状態がflagの場合の数flag = 0 ←Nと密接しているflag = 1 ←Nから離れているのが確定している"""N = input()dp = [[0]*2 for i in range(len(N))]mod = 10**9+7for i in range(len(N)):nv = int(N[i])if i == 0:dp[0][0] = nvfor j in range(nv):dp[0][1] += jelse:dp[i][0] = (dp[i-1][0] * nv) % modnsum = nv * (nv-1)//2dp[i][1] = ( dp[i-1][0] * nsum + dp[i-1][1] * 45 + 45 ) % mod#print (dp)print (sum(dp[-1]) % mod)