可能重复:
我想以 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) 的解决方案。
请只给我提示(请没有解决方案),以便我可以降低解决方案的复杂性。