何度もバグらせてしまったので，どうやればバグりにくいかを考える．
考え方
$N$以下で$k$桁のものの個数$\mathrm{cnt}[k]$がわかれば，\begin{aligned}
\sum_{k} \frac{\mathrm{cnt}[k] (\mathrm{cnt}[k] + 1)}{2}
\end{aligned}
が答えになる．$\mathrm{cnt}[k]$を，いかに間違えずに数えるかがポイント．最上位の桁は他の桁と数え方が変わる点も，バグりやすい．\sum_{k} \frac{\mathrm{cnt}[k] (\mathrm{cnt}[k] + 1)}{2}
\end{aligned}
以下のように考えるのは，正しいが間違いやすい．
- 1桁の個数：1,2,...,9の「9個」
- 2桁の個数：10, 11, ..., 99の「99 - 10 + 1 = 90個」
- ・・・
- n桁の個数：「$\overbrace{99\cdots 9}^{n} - 10^{n} +1 = \overbrace{99\cdots 9}^{n} - \overbrace{99\cdots 9}^{n - 1}= 9\times 10^{n-1}$個」
なるべく，単純な同じ処理にしたい．
問題の制約上，最高17桁なので，
- 各$i = 0,1,2,3,...,17$について
- $N$以下の正整数で$[10^{i}, 10^{i + 1})$に含まれる数をカウントする
回答例
$N$の桁より大きな桁では，topとbottomが逆転することに注意．N = int(input()) mod = 998244353 ans = 0 for i in range(18): top = min(10 ** (i + 1) - 1, N) bottom = 10 ** i if bottom <= top: cnt = top - bottom + 1 ans += ((cnt * (cnt + 1)) // 2) % mod ans %= mod print(ans)
