我想生成序列的第n项1,3,8,22,60,164在顺序（1）或顺序（nlogn） [英] I want to generate the nth term of the sequence 1,3,8,22,60 ,164 in Order(1) or order of (nlogn)

问题描述

此序列满足
a（n + 2）= 2 a（n + 1）+ 2 a（n）。

ba（n）= [（1 + sqrt（3））^（n + 2） - （1-sqrt（3））^（n + 2）] /（4sqrt（3））。
$ b

我使用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< 你好，世界！ << 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]）+ 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个项。有很快的计算模数小数的权力的技巧？
对于更快生成此序列有什么建议吗？

请帮助

方案

您可以使用矩阵方法计算O（log n）步中线性递归关系的序列值。在这种情况下，递归矩阵为

  2 2 
 1 0 
  

然后通过将<$ c $> $

这个循环立即转换为

  | 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 |。 
  

要获得某个数值的模数，请计算该数的乘方矩阵的幂。

This sequence satisfies a(n+2) = 2 a(n+1) + 2 a(n).

and also a(n)=[(1+sqrt(3))^(n+2)-(1-sqrt(3))^(n+2)]/(4sqrt(3)).

I am using C++ for me n can vary from 1 to 10^ 9. I need the answers modulo (10^9)+7 But speed here is very important

My code with formula1 is slow for numbers > 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;
}

I want a faster method. How can I compute the nth term using the second formula.Is there any trick to calculate modular powers of decimals very quickly? Do you have any suggestions for faster generation of this sequence?

Please help

解决方案

You can calculate values of sequences with a linear recurrence relation in O(log n) steps using the matrix method. In this case, the recurrence matrix is

2 2
1 0

The n-th term of the sequence is then obtained by multiplying the n-th power of that matrix with the two initial values.

The recurrence immediately translates to

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

thus

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

In this case the initial conditions give, x_1 = 1, x_2 = 3 lead to x_0 = 0.5, a non-integer value, hence the calculation should rather be

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

To get the value modulo some number, calculate the power of the matrix modulo that number.

这篇关于我想生成序列的第n项1,3,8,22,60,164在顺序（1）或顺序（nlogn）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！