かしのブログ

競技プログラミングとか

AtCoder Beginner Contest 129 F - Takahashi's Basics in Education and Learning

AtCoder 繰り返し2乗法行列 runtime modint

問題

初項 $A$ 、公差 $B$ 、項数 $L$ の数列 $S$ がある。十進法で $s_0, s_1, \cdots, s_{L-1}$ を順に結合してできる数 $X$ を整数 $M$ で割ったあまりを求める。

考察

全ての要素が $k$ 桁の整数である公差 $B$ 、長さ $l$ の等比数列 $T_k$ について $X_k$ は、

$X_k = t_0 \cdot 10^{k(l-1)} + t_1 \cdot 10^{k(l-2)} + \cdots + t_{l-1} \cdot 10^0$

$= (((t_0 \cdot 10^k + t_1) \cdot 10^k + t_2) \cdot 10^k + \cdots + t_{l-2}) \cdot 10^k + t_{l-1}$

$Y_{n} = (t_0 \cdot 10^k + t_1) \cdot 10^k + \cdots + t_{n}$ とすると、 $Y_{n+1} = 10^kY_{n} + t_{n+1}$ 。また、 $t_{n+1} = t_n + B$ より、

で求められ、 $X_k = Y_{l-1}$ 。行列の塁上は繰り返し2乗法で求める。

制約より、 $k =1\sim 17$ まで、初項 $t_0$ と項数 $l$ が、 $A, B, L$ から得られる（その桁数の項がないなら0）。 $Y_0$ を、 $k-1$ 桁まで計算した結果として利用することで $X$ を求めることができる。ただし、 $k = 0$ のときは $Y_0 = 0$ 。

実装