ABC 129 F - Takahashi's Basics in Education and Learning

• 問題
• AC

${\mathcal O}(n)$では無理だし、実は${\mathcal O}(1)$になるみたいな性質も思いつかないので、うまく式を立てて繰り返し二乗法っぽく計算するしかないという気持ちになる。

整数$s_i$の桁数はあまり変化しない（最大で18桁までしか増えない）ので、桁数が等しい部分列ごとに連結して余りを計算するのがいちばん良さそうと思った。

$(s_i)$の部分列も公差$B$の等差数列になるが、初項は異なるので、とりあえず初項$\alpha$、公差$B$の数列$s'_0, s'_1, ...$について考える。また、すべての$s'_i$が$d$桁の数であるとする。$s'_0, s'_1, ..., s'_{k-1}$を問題の通りに連結してできた数を$f(k)$とするとき、

$\begin{aligned} f(k) & = s'_0 \cdot 10^{(k-1)d} + s'_1 \cdot 10^{(k-2)d} + ... + s'_{k-2}\cdot 10^d+ s'_{k-1} \\ & = \alpha \cdot 10^{(k-1)d} + (\alpha + B) \cdot 10^{(k-2)d} + ... + \alpha + (k-1)B \end{aligned}$

と書ける。$f$がダブリングで計算できるか試してみる:

$f(k+1) = f(k)10^d + \alpha + kB$
$\begin{aligned} f(2k) & = \alpha \cdot 10^{(2k-1)d} + (\alpha + B) \cdot 10^{(2k-2)d} + ... + \alpha + (2k-1)B \\ & = \bigl( \alpha \cdot 10^{(2k-1)d} + (\alpha + B) \cdot 10^{(2k-2)d} + ... + (\alpha + (k-1)B)\cdot 10^{kd} \bigr) \\ & \qquad + \bigl( (\alpha + kB) \cdot 10^{(k-1)d} + (\alpha + (k+1)B) \cdot 10^{(k-2)d} + ... + \alpha + (2k-1)B \bigr) \\ & = 10^{kd} \bigl( \alpha \cdot 10^{(k-1)d} + (\alpha + B)10^{(k-2)d} + ... + \alpha + (k-1)B \bigr) \\ & \qquad +\alpha \cdot 10^{(k-1)d} + (\alpha + B)10^{(k-2)d} + ... + \alpha + (k-1)B\\ & \qquad +kB(10^{(k-1)d} + ... + 10^d + 1) \\ & = (10^{kd} + 1)f(k) + kB(10^{(k-1)d} + ... + 10^d + 1) \end{aligned}$

やはりこれで計算できそうなのだが、最後の式が問題である。求めたいのは$\mod M$の値だったが、$10^{(k-1)d} + ... + 10^d + 1 = (10^{kd}-1)/(10^d-1)$という普通の変形では、分母と$M$が互いに素でないケースを扱えない。

kirika_compさんの整数論テクニック集に等比数列の和をダブリングで求める方法が載っている。$g(k) = 10^{(k-1)d} + ... + 10^d + 1$とするとき、

$g(0) = 0$
$g(k+1) = 1+ 10^d g(k)$
$g(2k) = (1+10^{kd})g(k)$

で求まる。$f(2k) = (10^{kd}+1)f(k) +kBg(k)$だから、これで$f$を計算できる。

あとは、$(s_i)$の1, 2, …, 18桁の部分だけ抜き出して連結した数を上のように（$\mod M$で）計算し、それらをさらに連結すれば答えになる。

---

A mod B problemに似てはいるが、細部を詰めるのがずっと難しい。50分とかで解けるようになるのはだいぶ先の話に思える。

というか、A mod B problemでやったダブリングは実質的には等比数列の和を求める操作だったのだけど、そういう自覚がなかったな。少し理解が進んだということにしておく。

---

解説は行列で計算してるけど、行列が自然に思い浮かばなければ実装する意味もないので保留……

→ 単に$f(k+1) = f(k)10^d + \alpha + kB$を行列に直せばいいのか。

$\left( \begin{array}{c} f(k+1) \\ k+1 \\ 1 \end{array} \right) = \left( \begin{array}{ccc} 10^d & B & \alpha \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{array} \right) \left( \begin{array}{c} f(k) \\ k \\ 1 \end{array} \right)$

となる。通した。漸化式を見て行列で書けそうという発想にさえなれば、50分で解くのも現実的に思えてきた。