6338. Number of methods of monkey collision Weekly

6338. Number of methods of monkey collision

Thought：

纯math问题，that is$2^n - 2$。butnAt most$10^9$So big，Return directly to timeout。
所以用了Fast power算法，

使用Fast power算法来降低计算 2^n Time complexity。
it’s here，We use variables x To store 2^n，And in each cycle x square。when n When you are a miracle，We will take the result to take the result x。This can be calculated in each cycle2^n。
Before returning the result，We need to use(res-2)%mod Remove the border situation

Code：

class Solution:
    def monkeyMove(self, n: int) -> int:
        mod = 10**9 + 7
        res = 1
        x = 2
        while n > 0:
            if n % 2 == 1:
                res = (res * x) % mod
            x = (x * x) % mod
            n = n // 2
        return (res-2) % mod