如何计算2 ^ n模1000000007，n = 10 ^ 9 [英] how to calculate 2^n modulo 1000000007 , n = 10^9

问题描述

什么是最快的计算方法，我看到有些人使用矩阵，当我在互联网上搜索时，他们谈论了特征值和特征向量(对这些东西一无所知).递归方程 f(n)=(2 * f(n-1))+ 2，并且f(1)= 1 n可能高达10 ^ 9 .... 我已经尝试使用DP，最多存储1000000个值并使用常见的快速幂运算方法，但都超时了 我通常在这些模数问题中比较弱，需要计算较大的值

what is the fastest method to calculate this, i saw some people using matrices and when i searched on the internet, they talked about eigen values and eigen vectors (no idea about this stuff)...there was a question which reduced to a recursive equation f(n) = (2*f(n-1)) + 2 , and f(1) = 1, n could be upto 10^9.... i already tried using DP, storing upto 1000000 values and using the common fast exponentiation method, it all timed out im generally weak in these modulo questions, which require computing large values

推荐答案

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

然后您可以在其中应用快速的模块化电源方法.

where you can then apply fast modular power methods.

这篇关于如何计算2 ^ n模1000000007，n = 10 ^ 9的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！