思想:
纯数学问题,就是$2^n - 2$。但是n最多有$10^9$那么大,直接返回会超时。
所以用了快速幂算法,
使用快速幂算法来降低计算 2^n 的时间复杂度。
在这里,我们用变量 x 来存储 2^n,并在每次循环中将 x 平方。当 n 为奇数时,我们将结果乘以 x。这样可以在每次循环中计算出2^n。
在返回结果之前,我们需要用(res-2)%mod 去除边界情况
代码:
1 | class Solution: |
纯数学问题,就是$2^n - 2$。但是n最多有$10^9$那么大,直接返回会超时。
所以用了快速幂算法,
使用快速幂算法来降低计算 2^n 的时间复杂度。
在这里,我们用变量 x 来存储 2^n,并在每次循环中将 x 平方。当 n 为奇数时,我们将结果乘以 x。这样可以在每次循环中计算出2^n。
在返回结果之前,我们需要用(res-2)%mod 去除边界情况
1 | class Solution: |