2

我正在研究一个问题，我应该找到nth一个4x4矩阵的幂，它n可以和我一样大10^15，因为答案中的值可能非常大，我可以使用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;
}
4

3 回答 3

2

[评论者表明这个答案是不完整的。答案保留在这里以供参考，但不想再投票了。评论者会自行决定添加更完整的答案吗？]

是的。一个很好的方式来做你想做的事是众所周知的。您必须对矩阵进行对角化。

对角化将需要一些编程。该理论在此处进行了解释。14.6。幸运的是，现有的矩阵代数库（如 LAPACK）已经包含对角化例程。

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

于 2012-09-04T17:55:53.973 回答
2

您可以利用多个测试用例来减少总计算量。

请注意，每次调用 power 时，您都在重新计算原始矩阵 2 的所有幂。因此，对于像 10^15（大约 2^50）这样的数字，您最终将对矩阵进行 50 次平方，并计算该数字中每个非零位的乘法（可能是 25 次）。

如果您只是预先计算 2 的 50 次幂，那么每个测试用例平均只需要 25 次乘法而不是 75 次。

您可以将这个想法更进一步，并为您的求幂使用不同的基础。这将导致更多的预计算，但每个测试值的最终矩阵乘法更少。

例如，您可以预先计算 [M^1,M^2,M^3],[M^4,M^8,M^12，而不是预先计算 M^2, M^4, M^8, M^16 ],[M^16,M^32,M^48] 所以 M^51 将是 (M^3)*(M^48) 而不是 M*M^2*M^16*M^32

于 2012-09-04T20:41:39.960 回答
0

这并不是关于更快地对矩阵求幂的想法，而是关于加快整个程序的想法。

如果您被要求执行 10^4 次幂运算，这并不意味着它们应该独立完成。您可以对请求进行排序并为每个下一个计算重用先前的结果。

您还可以存储先前计算的中间结果。

于 2012-09-04T20:34:47.170 回答