题目分析

题目要求计算矩阵求和式 (\sum\limits_{x=1}^LA^xB^{\left\lfloor\frac{Px+R}{Q}\right\rfloor})，其中 (A,B) 是 (N \times N) 矩阵。由于 (L) 可达到 (10^{18})，直接遍历计算不可行，需借助类欧几里得算法结合矩阵快速幂，将求和过程转化为递归分治问题。

解题思路

1. 矩阵封装：定义矩阵结构体，实现矩阵加法、乘法及快速幂，支持矩阵运算的基本操作。
2. 递归分治（类欧几里得）：通过类欧几里得算法的思想，将求和范围逐步缩小。每次递归中，根据 (\frac{Px+R}{Q}) 的取值特性，将问题分解为更小的子问题，并结合矩阵快速幂计算幂次项。
3. 状态封装：定义 Node 结构体封装矩阵状态（包括 (A,B) 的幂次及累加和），通过重载乘法实现状态的快速合并，减少递归中的重复计算。

代码实现（带注释）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128_t i128;
const int P = 998244353;

// 矩阵结构体，支持加法、乘法运算
struct Matrix {
    int n, m;  // 矩阵行数、列数
    ll a[25][25];  // 矩阵元素（最大N=20）

    // 空矩阵构造
    Matrix() : n(0), m(0) {
        memset(a, 0, sizeof(a));
    }

    // 单位矩阵构造（n阶）
    Matrix(int _n) : n(_n), m(_n) {
        memset(a, 0, sizeof(a));
        for (int i = 1; i <= n; i++)
            a[i][i] = 1;
    }

    // 自定义大小矩阵构造
    Matrix(int _n, int _m) : n(_n), m(_m) {
        memset(a, 0, sizeof(a));
    }

    // 重载[]运算符，修改矩阵元素
    ll *operator[](int x) {
        return a[x];
    }

    // 重载[]运算符，访问矩阵元素（只读）
    const ll *operator[](int x) const {
        return a[x];
    }

    // 矩阵加法
    friend Matrix operator+(const Matrix &a, const Matrix &b) {
        Matrix c(a.n, a.m);
        for (int i = 1; i <= a.n; i++)
            for (int j = 1; j <= a.m; j++)
                c[i][j] = (a[i][j] + b[i][j]) % P;
        return c;
    }

    // 矩阵乘法
    friend Matrix operator*(const Matrix &a, const Matrix &b) {
        Matrix c(a.n, b.m);
        for (int i = 1; i <= a.n; i++)
            for (int k = 1; k <= a.m; k++)
                for (int j = 1; j <= b.m; j++)
                    (c[i][j] += a[i][k] * b[k][j]) %= P;
        return c;
    }
};

int m;  // 矩阵维度N（全局变量，方便Node使用）

// 状态结构体：封装A^x、B^y及累加和s
struct Node {
    Matrix x, y, s;  // x=A^a, y=B^b, s=累加和

    // 初始化：x为单位矩阵，y为单位矩阵，s为空矩阵
    Node() : x(m), y(m), s(m, m) {}

    // 状态乘法：合并两个状态（对应递归中的子问题合并）
    friend Node operator*(const Node &l, const Node &r) {
        Node res;
        res.x = l.x * r.x;          // A的幂次相乘
        res.y = l.y * r.y;          // B的幂次相乘
        res.s = l.s + l.x * r.s * l.y;  // 累加和合并：l.s + l.x * r.s * l.y
        return res;
    }
};

// 状态快速幂：计算a^b（b为指数）
Node QPow(Node a, ll b) {
    Node res;  // 初始化为单位状态
    for (; b; b >>= 1, a = a * a)
        if (b & 1)
            res = res * a;
    return res;
}

// 类欧几里得递归函数：计算sum_{x=1}^n A^x B^{floor((a*x + b)/c)}
Node F(ll n, ll a, ll b, ll c, Node U, Node R) {
    if (!n) return Node();  // 边界：n=0时返回空状态

    // 情况1：b >= c，拆分B的幂次
    if (b >= c)
        return QPow(U, b / c) * F(n, a, b % c, c, U, R);

    // 情况2：a >= c，拆分A的幂次
    if (a >= c)
        return F(n, a % c, b, c, U, QPow(U, a / c) * R);

    ll m = ((i128)a * n + b) / c;  // 计算floor((a*n + b)/c)

    if (!m) return QPow(R, n);  // 边界：m=0时，B的幂次为0，直接计算R^n（R对应A^x）

    // 情况3：a < c且b < c，递归转化为对偶问题
    return QPow(R, (c - b - 1) / a) * U * 
           F(m - 1, c, (c - b - 1) % a, a, R, U) * 
           QPow(R, n - ((i128)c * m - b - 1) / a);
}

ll a, b, c, n;  // 对应题目中的P, R, Q, L

int main() {
    // 输入：P, Q, R, L, N
    scanf("%lld%lld%lld%lld%d", &a, &c, &b, &n, &m);

    Node U, R;  // U对应B的幂次状态，R对应A的幂次状态

    // 输入矩阵A，初始化R.x = A（R表示A^x）
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
            scanf("%lld", &R.x[i][j]), R.s[i][j] = R.x[i][j];  // R.s初始化为A（对应x=1时的项）

    // 输入矩阵B，初始化U.y = B（U表示B^y）
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
            scanf("%lld", &U.y[i][j]);

    // 调用递归函数计算结果
    Node ans = F(n, a, b, c, U, R);

    // 输出结果矩阵
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++)
            printf("%lld ", ans.s[i][j]);
        printf("\n");
    }

    return 0;
}

代码解释

1. 矩阵结构体：封装矩阵的基本运算（加法、乘法），支持单位矩阵初始化，满足矩阵幂次计算需求。
2. 状态结构体：通过 Node 封装 (A^x)、(B^y) 及累加和，重载乘法实现状态合并，适配递归分治中的子问题组合。
3. 类欧几里得递归：通过分解 (\left\lfloor\frac{Px+R}{Q}\right\rfloor) 的取值，将原问题转化为更小的子问题，结合矩阵快速幂高效计算幂次项。
4. 主函数：初始化矩阵 (A,B) 对应的状态，调用递归函数求解并输出结果。