how to calculate 2^n modulo 1000000007 , n = 10^9

2019-01-19 23:56发布

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

2条回答
爷的心禁止访问
2楼-- · 2019-01-20 00:28

Modular exponentiation by the square-and-multiply method:

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e%2 == 1
            x, e := (x*b)%m, e-1
        else b, e := (b*b)%m, e//2
    return x
查看更多
不美不萌又怎样
3楼-- · 2019-01-20 00:29
f(n) = (2*f(n-1)) + 2 with f(1)=1

is equivalent to

(f(n)+2) = 2 * (f(n-1)+2)
         = ...
         = 2^(n-1) * (f(1)+2) = 3 * 2^(n-1)

so that finally

f(n) = 3 * 2^(n-1) - 2

where you can then apply fast modular power methods.

查看更多
登录 后发表回答