2550.猴子碰撞的方法数

链接：2550.猴子碰撞的方法数
难度：Medium
标签：递归、数学
简介：返回猴子至少发生 一次碰撞 的移动方法数。由于答案可能非常大，请返回对 109+7 取余后的结果。

题解 1 - cpp

• 编辑时间：2023-01-29
• 执行用时：4ms
• 内存消耗：6.3MB
• 编程语言：cpp
• 解法介绍：贪心， 只有在都顺和都逆才不相撞, 快速幂。

typedef long long ll;
int mod = 1e9 + 7;
ll quick_pow(ll a, ll b) {
    ll ans = 1, tmp = a;
    for (; b; b >>= 1) {
        if (b & 1) ans = (ans * tmp) % mod;
        tmp = (tmp * tmp) % mod;
    }
    return ans;
}
class Solution {
public:
    int monkeyMove(int n) {
        return (quick_pow(2, n) + mod - 2) % mod;
    }
};

题解 2 - python

• 编辑时间：2023-01-29
• 执行用时：32ms
• 内存消耗：14.8MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def monkeyMove(self, n: int) -> int:
        mod = 10 ** 9 + 7
        return (pow(2, n, mod) + mod - 2) % mod

题解 3 - rust

• 编辑时间：2023-01-29
• 内存消耗：2MB
• 编程语言：rust
• 解法介绍：同上。

fn pow(base: i64, exp: i64, mod_num: i64) -> i64 {
    let mut exp = exp;
    let mut tmp = base;
    let mut ans = 1;
    while exp != 0 {
        if exp % 2 == 1 {
            ans = (ans * tmp) % mod_num;
        }
        tmp = (tmp * tmp) % mod_num;
        exp >>= 1
    }
    ans
}
impl Solution {
    pub fn monkey_move(n: i32) -> i32 {
        let mod_num = 1000000007;
        ((pow(2, n as i64, mod_num) + mod_num - 2) % mod_num) as i32
    }
}