原题递推转换

考虑到有可能 $\gcd(M,A-1) \neq 1$，不能直接等比数列求和。

$f(x) = \Sigma_{i=0}^{X-1}{A^i}$

$= A^{X-1}+A^{X-2}+\dots + A^3+A^2+A^1+A^0$

$= (((1\times A+1)\times A+1)\times A+1)\dots$

可以转为为递推式：

• $f(1) = 1$
• $f(i) = f(i-1)\times A+1$

矩阵乘法替代递推

$$\begin{bmatrix} a & b \end{bmatrix} \begin{bmatrix} c & d \\ e & f \end{bmatrix} = \begin{bmatrix} ac+be & ad+bf \end{bmatrix}$$$$\begin{bmatrix} f_1 & 1 \end{bmatrix} \begin{bmatrix} A & 0 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} A\times f_1+1 & 1 \end{bmatrix}$$

答案的第 $i$ 行、第 $j$列，等于第一个矩阵的第 $i$ 行，依次乘以第二个矩阵的第 $j$ 列的每一项，然后求和。

暴力计算

#include <bits/stdc++.h>
#define int long long
using namespace std;
int A, X, M;
struct Mat
{
    int r, c;
    int m[2][2];
};
Mat mul(Mat A, Mat B)
{
    // A.c == B.r
    Mat C;
    C.r = A.r, C.c = B.c;
    for (int i = 0; i < C.r; i++)
        for (int j = 0; j < C.c; j++)
        {
            //  C[i][j] = A 的第 i 行依次乘以 B 的第 j 列的每一项求和
            C.m[i][j] = 0;
            for (int k = 0; k < A.c; k++)
                C.m[i][j] = (C.m[i][j] + A.m[i][k] * B.m[k][j]) % M;
        }
    return C;
}
Mat quick_pow(Mat A, int b)
{
    // A.r == A.c
    Mat res;
    res.c = res.r = A.r;
    for (int i = 0; i < res.c; i++)
        for (int j = 0; j < res.r; j++)
            res.m[i][j] = (i == j);
    for (int i = 1; i <= b; i++)
        res = mul(res, A);
    return res;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> A >> X >> M;
    // (f(1) 1)
    Mat a, b;
    a.r = 1, a.c = 2;
    a.m[0][0] = 1, a.m[0][1] = 1; // A^0 = 1
    b.r = 2, b.c = 2;
    b.m[0][0] = A, b.m[0][1] = 0;
    b.m[1][0] = 1, b.m[1][1] = 1;
    // 矩阵乘法代替递推
    Mat ans = mul(a, quick_pow(b, X - 1));
    cout << ans.m[0][0] << "\n";
    return 0;
}

加上快速幂，此时已能过绝大多数题目

快速幂熟练的同学也可以写倍增而不是递归的模式

Mat quick_pow(Mat A, int b)
{
    // A.r == A.c
    Mat res;
    res.c = res.r = A.r;
    for (int i = 0; i < res.c; i++)
        for (int j = 0; j < res.r; j++)
            res.m[i][j] = (i == j);
    // 快速幂
    if (b == 0)
        return res;
    Mat Ab2 = quick_pow(A, b / 2);
    if (b % 2 == 0)
        return mul(Ab2, Ab2);
    return mul(mul(Ab2, Ab2), A);
}

构造函数+重载运算符+各种优化之后的花里胡哨写法

#include <bits/stdc++.h>
#define int long long
using namespace std;
int A, X, M;
struct Mat
{
    int r, c;
    int m[2][2];
    // 构造函数
    Mat(int _r, int _c)
    {
        r = _r, c = _c;
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                m[i][j] = 0;
    }
    // 单位矩阵构造
    Mat(int _r)
    {
        r = c = _r;
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                m[i][j] = (i == j);
    }
};
Mat operator*(const Mat &A, const Mat &B)
{
    // A.c == B.r
    Mat C(A.r, B.c);
    //  C[i][j] =
    // A 的第 i 行依次  乘以
    // B 的第 j 列的每一项求和
    for (int i = 0; i < C.r; i++)
        for (int k = 0; k < A.c; k++) // 更改枚举顺序可以保证后续的连续访问
            for (int j = 0; j < C.c; j++)
                C.m[i][j] = (C.m[i][j] + A.m[i][k] * B.m[k][j]) % M;
    return C;
}
Mat operator^(const Mat &A, int b)
{
    // A.r == A.c
    // 快速幂
    if (b == 0)
        return Mat(A.r);
    Mat Ab2 = A ^ (b / 2);
    if (b % 2 == 0)
        return Ab2 * Ab2; //  operator*(Ab2, Ab2)
    return Ab2 * Ab2 * A;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> A >> X >> M;
    // (f(1) 1)
    Mat a(1, 2), b(2, 2);
    a.m[0][0] = 1, a.m[0][1] = 1; // A^0 = 1
    b.m[0][0] = A, b.m[0][1] = 0;
    b.m[1][0] = 1, b.m[1][1] = 1;
    // 矩阵乘法代替递推
    Mat ans = a * (b ^ (X - 1));
    cout << ans.m[0][0] << "\n";
    return 0;
}