2

私は、答えの値が非常に大きくなる可能性があるので、使用できるのと同じくらい大きくなる可能性のある行列nthの累乗を見つけることになっている問題に取り組んでいます。与えられたマトリックスは-4x4n10^15modulo 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

複数のテストケースを利用して、合計の計算を減らすことができます。

powerを呼び出すたびに、元の行列の2のすべての累乗を再計算していることに注意してください。したがって、10 ^ 15（約2 ^ 50）のような数値の場合、行列を50回二乗し、数値の非ゼロビットごとに乗算を計算することになります（おそらく25回）。

2の50乗を単純に事前計算すると、各テストケースは75ではなく平均25の乗算のみを必要とします。

このアイデアをもう少し進めて、べき乗に別のベースを使用できます。これにより、事前計算は増えますが、各テスト値の最終的な行列の乗算は少なくなります。

たとえば、M ^ 2、M ^ 4、M ^ 8、M ^ 16を事前計算する代わりに、[M ^ 1、M ^ 2、M ^ 3]、[M ^ 4、M ^ 8、M^12を事前計算できます。 ]、[M ^ 16、M ^ 32、M ^ 48]なので、M ^51はM*M ^ 2 * M ^ 16 * M ^ 32ではなく（M ^ 3）*（M ^ 48）になります。

于 2012-09-04T20:41:39.960 に答える
2

[コメント投稿者は、この回答が不完全であることを示しています。回答は参照用にここに保持されますが、これ以上の賛成票は必要ありません。コメント投稿者は、彼らの裁量で、より完全な回答を追加しますか?]

はい。やりたいことを正確に行うための優れた方法が知られています。行列を対角化する必要があります。

対角化にはプログラミングが必要です。理論はセクションで説明されています。14.6. 幸いなことに、LAPACK などの既存の行列代数ライブラリには、対角化ルーチンが既に含まれています。

@Haileは、すべての行列が対角化できるわけではなく、退化したケースが存在することを正しく興味深いことに観察しています。私はそのような場合の実務経験があまりありません。Schur分解があります（以前にリンクされたソースのセクション14.10を参照）が、私は通常、Schurが実際の計算を行うためではなく、理論的なポイントを作成するためだけに使用されるのを見てきました. それでも、シュアはうまくいくと信じています。それを実装するには多大な労力がかかると思いますが、厳密に非対角化可能な行列の場合でも機能します。

于 2012-09-04T17:55:53.973 に答える
0

これは実際には、行列の累乗を高速化するという考えではなく、プログラム全体を高速化するという考えです。

10^4 のべき乗を実行するように求められた場合、これは、それらを個別に実行する必要があるという意味ではありません。リクエストを並べ替えて、次の計算ごとに前の結果を再利用できます。

また、以前の計算の中間結果を保存することもできます。

于 2012-09-04T20:34:47.170 に答える