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 的答案，但这里的速度非常重要

对于 > 10^7 的数字，我的公式 1 代码很慢

#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;
}

我想要一个更快的方法。如何使用第二个公式计算第 n 项。是否有任何技巧可以快速计算小数的模幂？你对更快地生成这个序列有什么建议吗？

请帮忙

4

2 回答 2

10

您可以使用矩阵方法以 O(log n) 步计算具有线性递归关系的序列值。在这种情况下，递归矩阵是

2 2
1 0

n然后通过n将该矩阵的 -th 次方与两个初始值相乘来获得序列的-th 项。

重复立即转化为

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