$ 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} \r