盆栽をサボっていたので怒られた問題。

問題

正整数 $x$ に対して、$x$ の桁を逆順にして leading zero を除いたものを $f(x)$ とする。入力 $n, m$ に対し、$\sum_{x=1}^{10^N-1} f(x)^m \mathrm{mod}\ 998244353$ を求める。

問題リンク

https://atcoder.jp/contests/KeioPC2025/tasks/KeioPC2025_e

解法

適当に実験をすると、結局は$\sum_{x=1}^{10^n - 1} x^m \mathrm{mod}\ 998244353$ を求めればよいことが分かる。

$S(m, k) := 1^m + 2^m + ... + (10^k)^m = \sum_{i=1}^{10^k} i^m$ として、$S(m, n)$ を求めることを考える。 $n \leq 10^9$ なので愚直には求められないが、$m \leq 10^6$ なので、これを利用して解きたい。$S(m, k)$ は Faulhaber's formula を用いて求めることを考えると、Bernoulli Number が分かればよくて、これは二項係数と畳み込みを適切に用いることで $O(m \log{m})$ で求まる。(cf. Bernoulli Number - Library Checker)

観察

$n = 2$ の場合で観察すると、$1^m, 2^m, ..., 10^m, 11^m, ..., 20^m, ..., 50^m, ..., 99^m$ の総和を求めることになる。便宜上 $100^m$ まで足すことを考える。

これらのうち、実際には足されない数は $10$ の倍数であるもので、$10^m, 20^m, 30^m, 40^m, 50^m, 60^m, 70^m, 80^m, 90^m, 100^m$ である。これらの和は、

より $S(m, 1)$ が求まればよいことが分かる。

$x = 10, 20, ..., 90$ の時に実際に足されるのは $1, 2, ..., 9$ であり、これはそれぞれの値を $10$ で割ったものに等しい。また、$x = 100$ の時は実際は $1$ が足されるが、一旦は $10$ が足されるということにしておく。すると、$S(m, 2) - 10^m S(m, 1) + S(m, 1) = S(m, 2) - (10^m - 1) S(m, 1)$ が求められればよい。

現時点で足されているのは $1^m, 2^m, ..., 9^m, 1^m, 11^m, ..., 2^m, 21^m, ..., 99^m, 10^m$ である。このうち、実際には足されない数は $10^m$ であり、これについて同様に考えると、$(10^m - 1) S(m, 0)$ が求められればよい。

よって、この時の答えは

結論 (一般解)

以上より、求める答えは $S(m, n) - (10^m - 1) \sum_{k = 0}^{n - 1} S(m, k)$ である。以降、$\sum_{k=0}^{n-1} S(m, k)$ を高速に求める方法を考える。

をとりあえず畳み込みの形にすると、

であるから、

このままだと計算量に $n$ がかかってしまうので、これをなんとかしたい。

数式をいじいじすると、シグマの順番が交換出来て、

あとは等比数列の和の公式を使えば、

となり、$\sum_{k=0}^{n-1}$ を消去できた。この値は $O(m \log{m} + m \log{n})$ で計算できそうなので、計算量の問題は解決した。

$S(m, n), 10^m - 1$ も高速に求められるので、結果として答えを得られる。

感想

ライブラリ盆栽をサボっていなかったら自前のライブラリでなんとかできたと思うので、ライブラリをちゃんと整えたい。終了後に Nyaan's Library からそのままコピペして提出したら AC 出ました。Nyaan さんいつもありがとうございます。

おわり

おわりです。