ABC293 E - Geometric Progression (500)
$ B_n = \sum_{i=0}^{n-1} A_iとすると、$ B_n = A B_{n-1}+1
愚直に計算すると$ \mathcal{O}(X)なので行列累乗で高速化すると
$ \left( \begin{matrix} B_n \\ 1 \end{matrix} \right) = \left( \begin{matrix} A & 1 \\ 0 & 1 \end{matrix} \right) \left( \begin{matrix} B_{n-1} \\ 1 \end{matrix} \right) = \left( \begin{matrix} A & 1 \\ 0 & 1 \end{matrix} \right)^{n-1} \left( \begin{matrix} B_{1} \\ 1 \end{matrix} \right)