-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

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

您甚至可以在 MIT Opencourseware Intro to Algorithms 课程或斯坦福的算法课程的视频讲座中找到它

于 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 回答
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 回答