c++ - 有什么办法可以降低找到这个矩阵的 n 次幂的时间复杂度吗？

Question

我正在研究一个问题，我应该找到 4x4 矩阵的 n 次方，其中 n 可以和 10^15 并且由于 answer 中的值可能非常大，我可以使用 modulo 10^9+7 。给定的矩阵是-

   2  1 -2 -1
A= 1  0  0  0
   0  1  0  0
   0  0  1  0 

我为此编写了一段代码，但它的运行时间超过了预期的时间。所以任何人都请帮助我减少时间复杂度。

#define FOR(k,a,b) for(typeof(a) k=(a); k < (b); ++k)
typedef long long ll;
#define dim 4
struct matrix {
    long long a[dim][dim];
};
#define MOD 1000000007
matrix mul(matrix x, matrix y)
{
    matrix res;
    FOR(a, 0, dim) FOR(b, 0, dim) res.a[a][b] = 0;
    FOR(a, 0, dim) FOR(b, 0, dim) FOR(c, 0, dim) {
    ll temp = x.a[a][b] * y.a[b][c];
    if (temp <= -MOD || temp >= MOD)
        temp %= MOD;
    res.a[a][c] += temp;
    if (res.a[a][c] <= -MOD || res.a[a][c] >= MOD)
        res.a[a][c] %= MOD;
    }
    return res;
}

matrix power(matrix m, ll n)
{
    if (n == 1)
        return m;
    matrix u = mul(m, m);
    u = power(u, n / 2);
    if (n & 1)
        u = mul(u, m);
    return u;
}

matrix M, RP;
int main()
{
    FOR(a, 0, dim) FOR(b, 0, dim) M.a[a][b] = 0;
    M.a[0][0] = 2;
    M.a[0][1] = 1;
    M.a[0][2] = -2;
    M.a[0][3] = -1;
    M.a[1][0] = 1;
    M.a[2][1] = 1;
    M.a[3][2] = 1;
    int nt;
    scanf("%d", &nt);
    while (nt--) {
    ll n;
    scanf("%lld", &n);
    RP = power(M, n);
    FOR(a, 0, dim)
        FOR(b, 0, dim)
        printf("%lld\n", RP.a[a][b]);
    }
    return 0;
}

Answer 1

[评论者表示此答案不完整。答案保留在这里供引用，但不想再点赞了。评论者会自行决定添加更完整的答案吗？]

是的。众所周知，一种完全按照您的意愿行事的绝妙方法。您必须对角化矩阵。

对角化需要一些编程。理论解释here,昆虫。 14.6.幸运的是，现有的矩阵代数库(如 LAPACK)已经包含对角化例程。

@Haile 正确而有趣地观察到并非所有矩阵都可对角化，存在退化情况。我对这种情况没有太多的实践经验。有 Schur 分解(参见先前链接源的第 14.10 节)，但我通常看到 Schur 仅用于提出理论观点，而不用于进行实际计算。不过，我相信 Schur 会奏效。我怀疑要实现它需要付出很多努力，但即使在严格不可对角化矩阵的情况下，它也会起作用。