数列 \((a_n)\) を \(a_n = \displaystyle\sum_{i=0}^{n-1} A^i\) で定めると、\(a_0 = 0\)、\(a_{n+1} = Aa_n + 1\) を満たします。求めるべきものは \(a_X \bmod M\) です。

ここで、上の漸化式より行列を用いて \(\begin{pmatrix} a_{n+1} \\ 1 \end{pmatrix} = \begin{pmatrix} A & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} a_n \\ 1 \end{pmatrix}\) と表すことができます。

\(a_0 = 0\) であったため、\(\begin{pmatrix} a_X \\ 1 \end{pmatrix} = \begin{pmatrix} A & 1 \\ 0 & 1 \end{pmatrix}^X \begin{pmatrix} 0 \\ 1 \end{pmatrix}\) です。

\(\begin{pmatrix} A & 1 \\ 0 & 1 \end{pmatrix}^X\) の各成分を \(M\) で割った余りは繰り返し二乗法を用いて \(O(\log X)\) で求めることができます（整数の \(X\) 乗を \(M\) で割った余りを求めるのと同様の要領です）。

よってこの問題を \(O(\log X)\) で解くことができました。

なお、\(\displaystyle\sum_{i=0}^{X-1} A^i = \frac{A^X-1}{A-1}\) ですが、これを利用して解こうとする場合 \(\text{mod } M\) における \(A-1\) の逆元が存在するとは限らないことに注意してください。

実装例

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

vector<vector<ll>> mat_mul(vector<vector<ll>> a, vector<vector<ll>> b, ll mod) {
	// 行列乗算
	int n = a.size();
	vector<vector<ll>> res(n, vector<ll>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				res[i][j] += a[i][k] * b[k][j];
				res[i][j] %= mod;
			}
		}
	}
	return res;
}

vector<vector<ll>> mat_pow(vector<vector<ll>> a, ll b, ll mod) {
	// 行列累乗
	int n = a.size();
	vector<vector<ll>> res(n, vector<ll>(n));
	for (int i = 0; i < n; i++) res[i][i] = 1;
	while (b) {
		if (b & 1) res = mat_mul(res, a, mod);
		a = mat_mul(a, a, mod);
		b >>= 1;
	}
	return res;
}

int main() {
	ll a, x, m;
	cin >> a >> x >> m;
	vector<vector<ll>> f = { {a,1},{0,1} };
	vector<vector<ll>> g = mat_pow(f, x, m);
	cout << g[0][1] << '\n';
}