计算这个最快的方法是什么,我看到一些人使用矩阵,当我在互联网上搜索时,他们谈到了特征值和特征向量(不知道这些东西)......有一个问题简化为递归方程
f(n) = (2*f(n-1)) + 2 和 f(1) = 1,
n 最高可达 10^9....
我已经尝试过使用 DP,最多存储 1000000 个值并使用常见的快速求幂方法,它都超时了
我在这些模数问题上通常很弱,这需要计算大的值
最佳答案
f(n) = (2*f(n-1)) + 2 with f(1)=1
相当于
(f(n)+2) = 2 * (f(n-1)+2)
= ...
= 2^(n-1) * (f(1)+2) = 3 * 2^(n-1)
所以最后
f(n) = 3 * 2^(n-1) - 2
然后您可以在其中应用快速模块化电源方法。
关于math - 如何计算 2^n 模 1000000007 , n = 10^9,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23846699/