-2

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

私が今していることは次のとおりです。

t1 = 1, t2 = 0,MOD = 1000000007;

for i = 1:n 

    t1_new = (2*(t1+t2)) % MOD;
    t2_new = t1;
    a[i] = (t1_new + t2_new) % MOD;   // where a[i] is the ith term mod p
    t1 = t1_new;
    t2 = t2_new;

return a[n]; // the required ans

しかし、これは O(n) ソリューションです。

解決策の複雑さを軽減できるように、ヒントだけを教えてください（解決策はありません）。

4

2 に答える 2

3

次の事実を使用できます。マトリックスを考えれば

    (0 1)
A = (2 2)

a n = A n-2 * (1, 3)[1] (ここで (1,3) はベクトル) および [1] はベクトルの 2 番目の座標を意味するという事実を使用できます。ここでは、行列に 2 進累乗を使用できます。n<=2 の場合を個別に検討してください。

于 2012-07-03T10:15:56.557 に答える
-1

これを達成するために配列はまったく必要ありません。

int n = 5;
int result = 0;

for (int i=0; i<n; ++i)
{
    int t1_new = (2*(t1+t2)) % MOD;
    int t2_new = t1;

    result = (t1_new + t2_new) % MOD;
    t1 = t1_new;
    t2 = t2_new;
}

int res = result;

そうすれば、n 番目の項が得られますが、n まですべての項が渡されるわけではありません。

于 2012-07-03T10:15:20.473 に答える