0

このシーケンスは、a(n+2) = 2 a(n+1) + 2 a(n) を満たします。

また、a(n)=[(1+sqrt(3))^(n+2)-(1-sqrt(3))^(n+2)]/(4sqrt(3))。

私は C++ を使用しています n は 1 から 10^9 まで変化します。モジュロ (10^9)+7 の答えが必要ですが、ここでの速度は非常に重要です。

formula1 を使用した私のコードは、10^7 を超える数値では遅い

#include <iostream>
#define big unsigned long long int
#include<stdlib.h>
int ans[100000001]={0};

big m  =1000000007;
using namespace std;
int main()
{
    //cout << "Hello world!" << endl;
    big t,n;
    cin>>t;
    big a,b,c;
    a=1;
    b=3;
    c=8;
    ans[0]=0;
    ans[1]=1;
    ans[2]=3;
    ans[3]=8;
    for(big i=3;i<=100000000;i++)
        {
            ans[i]=(((((ans[i-2])+(ans[i-1])))%m)<<1)%m;

        }

//    while(t--)
//    {
//        int f=0;
//        cin>>n;
//        if(n==1){
//        cout<<1<<endl;f++;}
//        if(n==2){
//        cout<<3<<endl;
//        f++;
//        }
//        if(!f){
//        a=1;
//        b=3;
//        c=8;
//        for(big i=3;i<=n;i++)
//        {
//            c=(((((a)+(b
//                         )))%m)<<1)%m;
//            a=b%m ;
//            b=c%m;
//        }
//        cout<<ans[n]<<endl;
//        }
//    }
while(t--)
{
    cin>>n;
    if(n<=100000000)
    cout<<ans[n]<<endl;
    else
    cout<<rand()%m;
}
    return 0;
}

より速い方法が欲しい。2 番目の式を使用して n 番目の項を計算するにはどうすればよいですか? このシーケンスの生成を高速化するための提案はありますか?

助けてください

4

2 に答える 2

10

行列法を使用して、O(log n) ステップで線形回帰関係を持つシーケンスの値を計算できます。この場合、再帰行列は

2 2
1 0

次に、その行列の - 乗に 2 つの初期値をn掛けることによって、シーケンスの - 番目の項が得られます。n

再発はすぐに次のように変換されます。

|x_n    |   |2 2|   |x_(n-1)|
|x_(n-1)| = |1 0| * |x_(n-2)|

したがって

|x_(n+1)|   |2 2|^n   |x_1|
|x_n    | = |1 0|   * |x_0|.

この場合、初期条件は非整数値を与えるため、計算はむしろ次のようにする必要がありますx_1 = 1, x_2 = 3。x_0 = 0.5

|x_(n+1)|   |2 2|^(n-1)   |x_2|
|x_n    | = |1 0|       * |x_1|.

ある数値を法とする値を取得するには、その数値を法とする行列の累乗を計算します。

于 2012-07-02T22:33:14.967 に答える
0

アルゴリズム パズルの解法を探求する楽しさを台無しにしたくないので、最初のヒントを示します。ここにあるものは、基本的に、いくつかの紛らわしい要素を持つフィボナッチ数列です。

于 2012-07-02T22:41:29.427 に答える