\(k\) 桁の正整数全てに対する \(f(x)\) は、\(k\) 桁以下かつ \(\bmod\ 10\) で \(0\) でない正整数を \(1\) 回ずつ取ります。よって、求めるものは

\[ \sum_{k=1}^{N} \left(\sum_{i = 1}^{10^k-1} i^M - \sum_{i=1}^{10^{k-1}-1} (10i)^M \right) \]

です。

部分点解法

上の式について、\(M = 1\) を代入して式変形をすると

\[ \sum_{k=1}^{N} \frac{10^k(10^k-10^{k-1})}{2} = \sum_{k=1}^{N} 45 \times 10^{k-1}\]

が答えの値となります。あとはこの値を等比数列の和として計算すればよいです。計算量は \(\mathrm{O}(\log N)\) となります。

満点解法

\(g(x) = \sum_{i=0}^{M+1} g_ix^i\) を \(g(n) = \sum_{i=1}^{n-1} i^M\) を満たすように取ります。このような \(g\) は Faulhaber の公式を用いて \(\mathrm{O}(M \log M)\) で計算できます。

\[ \begin{aligned} &\sum_{k=1}^{N} \left(\sum_{i = 1}^{10^k-1} i^M - \sum_{i=1}^{10^{k-1}-1} (10i)^M \right) \\ &= \sum_{k=1}^{N} g(10^k) - \sum_{k=1}^{N-1} 10^Mg(10^k) \\ &= \sum_{k=1}^{N} \sum_{i=0}^{M+1} g_i 10^{ki} - \sum_{k=1}^{N-1} \sum_{i=0}^{M+1} g_i 10^{ki+M}\\ &= \sum_{i=0}^{M+1} \sum_{k=1}^{N} g_i 10^{ki} - \sum_{i=0}^{M+1}\sum_{k=1}^{N-1} g_i 10^{ki+M} \end{aligned} \]

最後の式において等比数列の和を計算することで全体で \(\mathrm{O}(M \log (N+M))\) でこの問題を解くことが出来ます。