123456789

1. 答えの桁数と候補の絞り込み

区間 $T[l, r]$ の長さを $L = r - l + 1$ とします。これを $M$ 個の非空な連続部分文字列に分割するとき、分割された各文字列の長さを平均化すると、基本となる長さは $x = \lfloor L / M \rfloor$ となります。余りである $L \pmod M$ 個の文字列については、長さを $x + 1$ にすることができます。スコア（最小値）を最大化するためには、すべての文字列の長さを $x$ 以上にするのが最適です。したがって、答えとなる文字列の長さは基本的に $x$ であると決め打つことができます。 ここで、文字列 $T$ は 123456789 の繰り返しであるため、長さ $x$ の文字列は「周期 9 のうち、どの数字（開始位置）から始まるか」によって 9 種類しか存在しません。これにより、答えとなる「スコアの最大値」の候補は、この 9 種類の文字列のいずれかに絞られます。したがって、これら 9 種類の候補を辞書順（数値順）に大きい方から試し、「その文字列を最小値とする $M$ 分割が可能か？」という判定問題を解くことに帰着できます。

2. ダブリングによる判定問題の高速化

ある開始位置（数字）から始まる長さ $x$ の文字列を閾値 $X$ としたとき、$T[l, r]$ を $M$ 分割してすべてのピースを $X$ 以上にできるかを判定します。左端から貪欲に切り出すことを考えます。ある開始位置 $p \pmod 9$ から長さ $x$ を切り出したとき、その文字列が $X$ 以上であればコスト 0（消費文字数 $x$）で条件を満たします。もし $X$ 未満になってしまう場合は、1 文字余分に切り出して長さ $x+1$ にすれば、桁数が増えるため確実に $X$ より大きくなります（コスト 1、消費文字数 $x+1$）。この操作を $M$ 回繰り返し、追加で消費したコストの合計が、全体で許容される余り文字数 $L - M \times x$ 以下に収まるならば分割可能です。 このシミュレーションをクエリごとに $M$ 回（最大 $10^{18}$ 回）行うと TLE（実行時間超過）となるため、ダブリングを用います。状態として dp[i][j][k][dc] を、「閾値の開始位置が $i$、基本の長さ $x \pmod 9$ が $j$、現在の開始位置 $k \pmod 9$ から出発して、$2^{dc}$ 個の区間を切り出したときに必要な追加コストの合計」と定義します。同時に、遷移先の開始位置は $(k + 2^{dc-1} \times j + \text{前半のコスト}) \pmod 9$ のように計算できます。これを前計算しておくことで、各クエリの判定を $O(\log M)$ で行うことができます。

3. 値の復元と高速な剰余計算

ダブリングによって条件を満たす最大の閾値 $X$（開始位置と長さ $x$）が特定できたら、その文字列が表す数値を $\pmod{998244353}$ で求めます。$x$ が非常に大きいため、愚直なループでは計算できません。 文字列 $T$ の 9 桁分のブロックの値を $B$ とします。長さ $x$ の文字列は、このブロック $B$ が $n = \lfloor x / 9 \rfloor$ 回繰り返され、最後に余りの $rem = x \pmod 9$ 桁がくっついた形になります。繰り返されるブロック部分は、$B \times 10^{9(n-1)} + B \times 10^{9(n-2)} + \dots + B \times 10^0$ という等比数列の和として表せます。この和は公式により $B \times \frac{10^{9n} - 1}{10^9 - 1}$ と計算できます。除算については、$10^9 - 1$ の法 $998244353$ における逆元を前計算しておくことで、各クエリ $O(\log x)$（または $O(1)$）で高速に求めることができます。最後に、この結果を $10^{rem}$ 倍して左にシフトし、末尾の端数部分の数値を足し合わせれば、最終的な答えが得られます。

4. 計算量

前計算（ダブリングのテーブル構築）には $O(9^3 \times \log M_{max}) \approx O(1)$ の時間しかかかりません。各クエリにおいては、9 つの候補に対してダブリングを用いて判定を行うため、1 クエリあたりの計算量は $O(9 \times \log M)$ となります。値の復元にかかる計算量も繰り返し二乗法を用いれば $O(\log x)$ です。全体として時間計算量は $O(Q \log M)$ となり、制限時間内に十分に間に合います。また、定数倍の重い入出力処理（std::endl によるフラッシュなど）を避け、逆元を事前計算しておくことが重要です。

実装例 (C++)