問題の言い換え

以下が成立します。ただし、\(d\) 桁の \(10\) 冪とは整数 \(10^{d-1}\) のことです。

整数 \(n\) について、\(n\) が \(N\) 個の \(M\) 桁以下の repunit の和で表せる \(\iff\) \(\frac{9n + N}{10}\) が \(N\) 個の \(M\) 桁以下の \(10\) 冪の和で表せる

このことは、\(d\) 桁の repunit と \(d\) 桁の \(10\) 冪を対応させることで \(\implies\) も \(\impliedby\) も簡単に示すことができます。

したがって、本問題は以下の問題に帰着されます。

\(N\) 個の \(M\) 桁以下の \(10\) 冪の和で表せる整数の個数を \(998244353\) で割った余りを求めよ。

以下、帰着後の問題を扱います。

判定問題

整数 \(n\) が与えられたとき、\(n\) が \(N\) 個の \(M\) 桁以下の \(10\) 冪の和で表すことができるかという問題を考えます。

まずは \(n\) を \(M\) 桁以下の \(10\) 冪の和で表すときの \(10\) 冪の個数の最小化について考えます。以下のような貪欲法が正当です。

\(i = M - 1, M - 2, \ldots, 1, 0\) の順に以下のような操作を行う。

• \(n\) を \(10^i\) で割ったときの商を \(Q\)、余りを \(R\) とする。\(Q\) 個の \(10^i\) を用いることとして、\(n\) を \(R\) に置き換える。

\(f(n)\) を \(n\) を \(M\) 桁以下の \(10\) 冪の和で表すために必要な \(10\) 冪の個数の最小値とします。結論から述べると、\(n\) が \(N\) 個の \(M\) 桁以下の \(10\) 冪で表される必要十分条件は、以下の \(3\) つがすべて満たされることです。

• \(n \geq N\)
• \(f(n) \leq N\)
• \(f(n) \equiv N \pmod 9\)

必要性については、\(1\) つ目の条件は \(10\) 冪が正整数であること、\(2\) つ目の条件は \(f(n)\) の定義、\(3\) つ目の条件は和を \(9\) で割った余りの条件から従います。十分性については、\(10^{d_1} + 10^{d_2} \ldots + 10^{d_{f(n)}} = n\) として、\(d_i > 0\) であるような \(i\) を選び \(10^{d_i}\) を \(10\) 個の \(10^{d_i - 1}\) に置き換えるという操作を \(\frac{N - f(n)}{9}\) 回行うことで \(n\) を \(N\) 個の\(M\) 桁以下の \(10\) 冪の和で表す表示が得られることから従います。\(n \geq N\) から一連の操作の過程ですべての \(i\) について \(d_i = 0\) となることはないことに注意してください。

数え上げ

\(n < N\) であるものは最後に答えから引くことにして、\(1\) つ目の条件を外し、単に \(n\) は非負整数であるとします。なお、\(n \leq N\) のとき \(f(n) \leq N\) であることから、このような非負整数 \(n\) の個数は \(\lfloor \frac{N}{9} \rfloor\) 個です。

ここで、上で解説した \(f(n)\) を求めるための貪欲法アルゴリズムの挙動について考えると、\(n\) を \(10^{M - 1}\) で割ったときの商を \(Q\)、余りを \(R\) として \(f(n) = Q + (R の桁和)\) が成立します。

したがって、本問題は以下のような問題に帰着されました。

以下の条件を満たす非負整数の組 \((A_0, A_1, \ldots, A_{M - 1})\) の個数を \(998244353\) で割った余りを求めよ。

• \(i = 0, 1, \ldots, M - 2\) に対して \(0 \leq A_i \leq 9\)（\(A_{M - 1}\) には条件がないことに注意してください）
• \(S = \sum A_i\) として、\(S \leq N\) かつ \(S \equiv N \pmod 9\)

\(1\) つ目の条件を満たし、\(\sum A_i = n\) であるような非負整数の組の個数を \(f_n\) として \(f = \sum f_nx^n\) とすると、\(f = \frac{(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9)^{M-1}}{1-x}\) です。この形式的冪級数（の \(N\) 次以下の項）は様々な方法で計算することができます。\(1 - x\) で割ることは係数列の累積和を取ることに対応しているので \({(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9)^{M-1}}\) を計算できればよいですが、これは有名問題で、以下のような方法が知られています。

• 微分方程式を立式し、低次の累乗であることを利用して係数を順に計算していく（参考 : Library checker）
• fps の log, exp を用いて fps pow を計算する（参考 : Library checker）
• fft による畳み込み + 繰り返し二乗法により fps のべき乗を計算する

計算量オーダーは上から \(O(N), O(N \log N), O(N \log N \log M)\) であり、いずれも定数倍が十分よければ AC するためには高速です。

その他にも、\(2\) つ目の条件も同時に考えることにより求めるべき値が \([x^N] \frac{(1-x^{10})^{M-1}}{(1-x)^M(1-x^9)}\) であることを利用するなど、様々な計算方法があります。