c++ - 计算序列1,3,8,22,60,164,448,1224...的第n项？

Question

可能重复：
我想以 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) 的解决方案。

请只给我提示（请没有解决方案），以便我可以降低解决方案的复杂性。

Answer 1

您可以使用以下事实。如果考虑矩阵

    (0 1)
A = (2 2)

您可以使用 a _n = A ^n-2 * (1, 3)[1] （这里 (1,3) 是向量）和 [1] 表示向量的第二个坐标的事实。在这里，您可以对矩阵使用二进制求幂。分别考虑 n<=2 的情况。

Answer 2

你根本不需要数组来实现这一点。

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 之前的全部。