-1 
#include <vector>
#include<iostream>
#include<stdio.h>
#define REP(i,n) for (ll i = 1; i <= n; i++)
using namespace std;

typedef unsigned long long int ll;
typedef vector<vector<ll> > matrix;
ll MOD = 1000000007;
const ll K = 2;

// computes A * B
matrix mul(matrix A, matrix B)
{
    matrix C(K+1, vector<ll>(K+1));
    REP(i, K) REP(j, K) REP(k, K)
        C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}

// computes A ^ p
matrix pow(matrix A, ll p)
{
    if (p == 1)
        return A;
    if (p & 1)
        return mul(A, pow(A, p-1));
    matrix X = pow(A, p>>1);
    return mul(X, X);
}

// returns the N-th term of Fibonacci sequence
ll fib(ll N)
{
    // create vector F1
    vector<ll> F1(K+1);
    F1[1] = 1;
    F1[2] = 3;

    // create matrix T
    matrix T(K+1, vector<ll>(K+1));
    T[1][1] = 0, T[1][2] = 1;
    T[2][1] = 2, T[2][2] = 2;

    // raise T to the (N-1)th power
    if (N == 1)
        return 1;
    T = pow(T, N-1);

    // the answer is the first row of T . F1
    ll res = 0;
    REP(i, K)
        res = (res + ((T[1][i] )* (F1[i]))) %MOD;
    return res;
}
ll fib2(ll n)
{
    if(n==1)
    return 1;
    ll a=1;ll b=3;ll c;
    for(ll i=3;i<=n;i++)
    {
        c=(2*a+2*b)%MOD;
        a=b;
        b=c;
    }
    return c;
}
int main()
{
    ll t;
    scanf("%llu",&t);
   // t=10000;
    ll n=1;
    while(t--)
    {
        scanf("%llu",&n);
        //n=1;
       // n++;
     //  n=1000000000;
        printf("%llu\n",fib(n));
    }
    return 0;
}

1,3,8,22,60,164 a[n]=2*(a[n-1]+a[n-2]) mod 10^9+7 を生成するコードを書いています。剰余累乗を使用しています。およびこのシーケンスを生成するための行列乗算方法。最悪の場合、つまり n=10^9 の時間を 2.3 秒から改善するにはどうすればよいですか。10000回～0.5秒～1秒くらい？このコードの速度を改善するための提案をお願いします。

4

3 に答える 3

0

ここでの主な犯人だと思いvectorます-動的割り当てと数値的なものはうまく混ざりません。
2x2 行列は小さすぎて、手の込んだアルゴリズムで影響を与えることができません。空想のオーバーヘッドのために、実際にはもっと悪いだろうという予感があります。

ループをアンロールして、動的割り当てを破棄しようとしましたか?

これが正しいことを願っています：

void mul(ll A[][2], ll B[][2], ll C[][2])
{
    C[0][0] = (A[0][0] * B[0][0]) % MOD;
    C[0][0] = (C[0][0] + A[0][1] * B[1][0]) % MOD;

    C[0][1] = (A[0][0] * B[0][1]) % MOD;
    C[0][1] = (C[0][1] + A[0][1] * B[1][1]) % MOD;

    C[1][0] = (A[1][0] * B[0][0]) % MOD;
    C[1][0] = (C[1][0] + A[1][1] * B[1][0]) % MOD;

    C[1][1] = (A[1][0] * B[0][1]) % MOD;
    C[1][1] = (C[1][1] + A[1][1] * B[1][1]) % MOD;
}

void pow(ll A[][2], ll p, ll out[][2])
{
    if (p == 1)
    {
        out[0][0] = A[0][0];
        out[0][1] = A[0][1];
        out[1][0] = A[1][0];
        out[1][1] = A[1][1];
        return;
    }
    if (p & 1)
    {
        ll B[2][2] = {{0}};
        pow(A, p - 1, B);
        mul(A, B, out);
    }
    else
    {
        ll X[2][2] = {{0}};
        pow(A, p >> 1, X);
        mul(X, X, out);
    }
}

ll fibv(ll N)
{
    ll T[2][2] =
    {
        {2, 2},
        {1, 0}
    };

    if (N == 1)
        return 1;
    ll RM[2][2] = {{0}};
    pow(T, N-1, RM);
    ll res = RM[0][1] % MOD;
    res = (res + RM[0][0] * 3) % MOD;
    return res;
}
于 2012-07-10T09:17:05.163 に答える
0

https://en.wikipedia.org/wiki/Strassen_algorithm

MIT Opencourseware Intro to Algorithms course または Stanford's Algorithms course のビデオ レクチャーでも見つけることができます。

于 2012-07-10T08:10:46.630 に答える
0

2x2 行列に特化すると、大幅な高速化が得られます。

struct matrix {
  ll a, b, c, d ;
  void Square() ;
  void Mul (const matrix& M) ;
  } ;
于 2012-07-10T09:15:25.733 に答える