6

このシリーズのn番目の用語を見つける必要がありますhttp://oeis.org/A028859

n <= 1000000000

答えは1000000007を法とする必要があります

コードを書いたのですが、naが膨大な数になると制限時間を超えてしまいます。

#include<iostream>
using namespace std

int main()
{
    long long int n;
    cin>>n;

    long long int a,b,c;
    a=1;
    b=3;

    int i;
    for(i=3;i<=n;i++)
    {
        c=(2ll*(a+b))%1000000007;
        a=b;
        b=c; 
    }

    cout<<c;
}
4

2 に答える 2

9

このタイプの問題を解決するための標準的な手法は、行列の乗算として書き直してから、二乗による指数を使用して行列の累乗を効率的に計算することです。

この場合：

a(n+2) = 2 a(n+1) + 2 a(n)
a(n+1) = a(n+1)

(a(n+2)) = (2  2) * ( a(n+1) )
(a(n+1))   (1  0)   ( a(n)   )

したがって、行列A=[2,2;を定義すると 1,0]の場合、n番目の項を次のように計算できます。

[1,0] * A^(n-2) * [3;1]

これらの操作はすべて1000000007を法として実行できるため、大きな数のライブラリは必要ありません。

A ^ Nを計算するにはO（log（n））2 * 2行列の乗算が必要なので、全体としてこのメ​​ソッドはO（log（n））ですが、元のメソッドはO（n）でした。

編集

これは、このメソッドの適切な説明とC++実装です。

于 2012-07-01T21:19:28.680 に答える
0

十分でない場合long longは、bignumライブラリを使用することをお勧めします。たとえば、GNUMP。

于 2012-07-01T20:56:58.007 に答える