题解 | 小红的二叉树| 高效的mod指数函数

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    if (n==1) {
        cout << 0;
        return 0;
    }

    auto ExpMod = [](long long base, long long exp, long long mod){
        long long result = 1;
        if (base > mod) base=base%mod;
        while(exp>0){
            if (exp%2==1){
                result *= base;
                result %= mod;
                exp -= 1;
            }
            base = (base*base) % mod;
            exp /= 2;
        }
        return result;
    };

    // 2^0 
    long long num = 1; // root
    long long mod = 1e9+7;
    // non-leaf, 2^1 ... 2^(n-2)
    for(int i=1;i<=n-2;i++){
        num = ( num + (3 * ExpMod(2, i, mod))% mod ) % mod;
    }

    cout << num;

}
// 64 位输出请用 printf("%lld")