0

重複の可能性:
Order(1) または (nlogn) の順序で、シーケンス 1,3,8,22,60 ,164 の n 番目の用語を生成したい

基本的に a[n]=2*(a[n-1]+a[n-2]); であるシーケンス 1,3,8,22,60... を生成しようとしています。ここで私の質問を参照してください。Order(1) または (nlogn) の順序で、シーケンス 1,3,8,22,60 ,164 の n 番目の用語を生成したい

これが私のc ++での実装です。しかし、遅すぎると思います。コードは最悪の場合で約5秒で実行されますが、1秒未満で実行したいのです。方法はlog nの順です。したがって、10^9 は 29 ステップしかかかりません。ここに私のコードがあります。それをスピードアップする方法や私がやっている間違いを提案してください

#include <iostream>
#define big long long unsigned int
#include<vector>
#include<stdio.h>
#define _SECURE_SCL 0
big m =1000000007;
using namespace std;
vector <vector <big> > vectin(vector<vector <big> > a)
{
    for(int i=0;i<2;i++)
    {
        vector <big> t;
        for(int j=0;j<2;j++)
        {
            t.push_back(0);
        }
        a.push_back(t);
    }
    return a;
}
vector <vector <big> > unit(vector<vector <big> > a)
{
    for(int i=0;i<2;i++)
    {
        vector <big> t;
        for(int j=0;j<2;j++)
        {   if(i!=j)
            t.push_back(0);
            else
            t.push_back(1);
        }
        a.push_back(t);
    }
    return a;
}
vector<vector <big> > multi(vector<vector <big> > a,vector<vector <big> >b )
{
    vector<vector <big> > c;
    c=vectin(c);
    for(big i=0;i<2;i++){

    for(big j=0;j<2;j++)
    {
        for(big k=0;k<2;k++)
            {
                c[i][j]+=((a[i][k])*(b[k][j]))%m;
            }
    }
}
return c;
}

big modexp_rl(big a,big b, big n)
{
    big r = 1;
    while (1){
        if (b&1)
            r = ((r )*(a) ) % n;
        b /= 2;
        if (!b )
            break;
        a = ((a )* (a) )% n;
    }
    return r;
}

vector <vector <big> > modexs (big b,vector <vector <big> > a )
{
    vector < vector <big > > r;
    r=unit(r);
    while(1)
    {  // cout<<b<<endl;
        if(b&1)
        r=multi(r,a);
        b/=2;

        if(!b)
        break;
        a=multi(a,a);
    }
    return r;
}

void displayvector(vector < vector <big> > s)
{
    for(big i=0;i<2;i++)
    {
        for(big j=0;j<2;j++)
        {
            cout<<s[i][j]<<"\t";
        }
    cout<<endl;
    }

}

vector <big> mul2( vector < vector <big> > a)
{
    vector <big> d;
    d.push_back(3*a[0][0]+1*a[0][1]);
    d.push_back(3*a[1][0]+1*a[1][1]);
return d;
}
int main()
{

  vector < vector <big> > a;
  vector <big> t1,t2;
  t1.push_back(2);
  t1.push_back(2);
  a.push_back(t1);
  t2.push_back(1);
  t2.push_back(0);
  a.push_back(t2);
  //dv(a);
  vector < vector <big> > ans;
  big t,n;
  //cin>>t;
  //scanf("%lld,&t);
  t=10000;
  while(t--){
  //cin>>n;
  //scanf("%lld",&n);
  n=1000000000;
  ans=modexs(n-1,a);
  vector <big> p;
  p=mul2(ans);
  //cout<<p[1]<<endl;
  printf("%lld\n",p[1]);
  //dv(ans);
  }
    return 0;
}
4

3 に答える 3

3

ベクトルに入る要素の数がわかっている場合はa、アルゴリズムを実行する前に、その数のスペースを予約する必要があります。これは、ベクターが動的にサイズ変更を行うときにデータのコピーを避けるためです。

于 2012-07-04T07:51:58.393 に答える
0

機能を強化する方法がない場合は、マルチコア プログラミングを研究して、その実装方法を学ぶことができます。これを参考にしてください。処理のパフォーマンスが向上します。ただし、リソースを消費します。お役に立てれば。

于 2012-07-04T07:37:16.000 に答える
0

級数の生成関数をWolfram Alphaにプラグインしたところ、n 番目の項は次のようになります。

[ (1 + Q)^(1+n) - (1 - Q)^(1+n) ] / (4Q) ,

どこでQ = sqrt(3)。

は1 - Q絶対値で 1 よりも小さいため、項全体は大きな に対して指数関数的に小さいことがわかりnます。つまり、大規模なn場合は、最初の項を計算して、次に大きな整数を取ることができます。

于 2012-07-04T19:26:21.783 に答える