問題

$m$ を $1$ 以上の整数とします。$x \in \mathbb{Z}/m\mathbb{Z}, n \in \mathbb{Z}_{\ge 0}$ が与えられるので、

$$ \sum_{i = 0}^{n - 1} x ^ i \pmod m $$

を計算してください。

出題例

ABC 429 G - Sum of Pow of Mod of Linear
（ちょっとかなり全然違うけど）ABC 129 F - Takahashi's Basics in Education and Learning

解法 1: 行列累乗

次の式を二分累乗すればよいです。

$$ \begin{pmatrix} 1 & 1 \\ 0 & x \end{pmatrix}^ n \begin{pmatrix} 0 \\ 1 \end{pmatrix}= \begin{pmatrix} \sum_{i = 0}^{n-1}x^ i \\ x^ n \end{pmatrix} $$

二分累乗一般のテクなのですが、$n \ne 0$ の場合を特別視することで、無駄な $A ← A^ 2$ を一回減らすことができます。（参考: Rust 標準ライブラリの {int}.pow() の実装）

\begin{algorithm}
\caption{GeomSum1}
\begin{algorithmic}
\PROCEDURE{GeomSum1}{$x \in \mathbb{Z}/m \mathbb{Z}, n$}

\IF {$n = 0$} \RETURN $0$ \ENDIF

\STATE
$A = \begin{pmatrix} 1 & 1 \\ 0 & x \end{pmatrix},
b = \begin{pmatrix} 0 \\ 1 \end{pmatrix}$

\WHILE{$n \ne 1$}
    \IF{$n \in 2\mathbb{Z}+1$} \STATE $b ← Ab$ \ENDIF
    \STATE $A ← A^ 2$
    \STATE $n ← \lfloor n / 2 \rfloor$
\ENDWHILE

\STATE $b ← Ab$
\RETURN $b_1$
\ENDPROCEDURE \end{algorithmic} \end{algorithm}

なおループの第 $k$ 回目（$0$ 始まりで数える）の最初における $A, b$ の値は

$$ \begin{align} A &= \begin{pmatrix} 1 & 1 \\ 0 & x \end{pmatrix} ^ {2^ k} = \begin{pmatrix} 1 & \sum_{i = 0}^{2^ k-1}x^ i \\ 0 & x^ {2^ k} \end{pmatrix} \\ B &= \begin{pmatrix} 1 & 1 \\ 0 & x \end{pmatrix} ^ {{2^ k} \mathop{\mathrm{rem}} 2^ k} \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} \sum _ {i = 0} ^ { n _ k -1} x ^ i \\ x ^ { n _ k } \end{pmatrix} \end{align} $$

（ただし、$n _k = n \mathop{\mathrm{rem}}2^ k$）となります。

解法 2: 変数を 3 つ管理する。

解法 1 をよく見ると、次の 3 つの値を管理すれば十分なことがわかります。

$$ \begin{align} p = x^ {2^ k}, \, q = \sum _ {i=0} ^ {2^ k - 1} x^ i, \, \mathtt{ans} = \sum _ {i=0} ^ {n_ k - 1} x^ i \end{align} $$

\begin{algorithm}
\caption{GeomSum2}
\begin{algorithmic}
\PROCEDURE{GeomSum2}{$x \in \mathbb{Z}/m \mathbb{Z}, n$}

\IF {$n = 0$} \RETURN $0$ \ENDIF

\STATE
$p = x, q = 1, \mathtt{ans} = 0$

\WHILE{$n \ne 1$}
    \IF{$n \in 2\mathbb{Z}+1$} \STATE $\mathtt{ans} ← q + p \cdot \mathtt{ans}$ \ENDIF
    \STATE $q ← q \cdot (1 + p)$
    \STATE $p ← p^ 2$
    \STATE $n ← \lfloor n / 2 \rfloor$
\ENDWHILE

\STATE $\mathtt{ans} ← q + p \cdot \mathtt{ans}$
\RETURN $\mathtt{ans}$
\ENDPROCEDURE \end{algorithmic} \end{algorithm}