如何计算 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屋！