Implementation: Inversions and Fast Power

The recursion depth is about log2 n, far below Python's recursion limit.

Fast modular power in Python

def power(base, exp, mod):
    """base^exp % mod for exp >= 0, recursive divide and conquer."""
    if exp == 0:
        return 1 % mod
    half = power(base, exp // 2, mod)
    result = half * half % mod
    if exp % 2 == 1:
        result = result * base % mod
    return result


def power_iter(base, exp, mod):
    """The same result without recursion: read the bits of exp."""
    result = 1 % mod
    base %= mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

print(power(3, 200, 1_000_000_007), power_iter(3, 200, 1_000_000_007))  # 136318165 136318165

• exp == 0 is the base case. 1 % mod gives 0 when mod == 1, which is the correct answer for any power modulo 1.
• power(base, exp // 2, mod) is the only recursive call: there is exactly one subproblem.
• Squaring half gives base^(2 * (exp // 2)); an odd exponent needs one more factor of base.
• Reducing with % mod after every multiplication keeps the numbers small.

The iterative version reads the bits of exp from lowest to highest. base takes the values b^1, b^2, b^4, ... and is multiplied into result whenever the current bit is 1. This loop form is the one usually ported to other languages; in everyday Python, call the built-in pow(base, exp, mod).

Test both on random inputs against a brute-force double loop and the built-in pow.

C++

C++ has no built-in big integers, so the product of two residues must fit in 64 bits: keep mod below 2^32.

#include <cstdint>
#include <iostream>

// Assumes 1 <= mod < 2^32 so that every product fits in 64 bits.
std::uint64_t mod_pow(std::uint64_t base, std::uint64_t exp, std::uint64_t mod) {
    std::uint64_t result = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    std::cout << mod_pow(3, 200, 1000000007) << '\n';  // 136318165
}

Java

Java's long is a signed 64-bit integer. With mod below 2^31 (for example 1_000_000_007), every product stays below 2^62. Java's % can return a negative value for a negative base, so it is corrected first.

public final class ModPow {
    // Assumes 1 <= mod < 2^31 so that every product fits in a long.
    static long modPow(long base, long exp, long mod) {
        long result = 1 % mod;
        base %= mod;
        if (base < 0) base += mod;
        while (exp > 0) {
            if ((exp & 1) == 1) result = result * base % mod;
            base = base * base % mod;
            exp >>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(modPow(3, 200, 1_000_000_007L));  // 136318165
    }
}

TypeScript

A JavaScript number is a double and loses precision above 2^53, so even 1_000_000_006 * 1_000_000_006 would come out wrong. bigint keeps the arithmetic exact.

export function modPow(base: bigint, exp: bigint, mod: bigint): bigint {
  let result = 1n % mod;
  base = ((base % mod) + mod) % mod;
  while (exp > 0n) {
    if (exp & 1n) result = (result * base) % mod;
    base = (base * base) % mod;
    exp >>= 1n;
  }
  return result;
}

console.log(modPow(3n, 200n, 1_000_000_007n)); // 136318165n

All three agree with Python's pow(3, 200, 1_000_000_007).

Summary

• Counting inversions is merge sort plus one line: add mid - i whenever the right side wins.
• A shared scratch buffer avoids the copying cost of slicing at every level.
• Fast power has one subproblem; the iterative bit-by-bit form is the easiest to port.
• In C++ and Java, keep mod small enough that products fit in 64 bits; in TypeScript, use bigint.