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

  • Z时代
  • 2024-01-10
  • 分类：问答

我现在要做的是：

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）解决方案。

请只给我提示（请没有解决方案），这样我可以减少解决方案的复杂性。

回答：

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

    (0 1)
A = (2 2)

您可以使用以下事实：n = A n-2

*（1，3）[1]（此处（1,3）是向量），[1]表示向量的第二坐标。在这里，您可以对矩阵使用二进制幂运算。分别考虑n <= 2的情况。

以上是 计算序列1,3,8,22,60,164,448,1224的第n个项...？ 的全部内容， 来源链接： utcz.com/qa/397901.html

回到顶部