Teile und herrsche

divide_and_conquer.py

def sort_count(a):
    """Return (sorted list, number of inversions) using merge sort."""
    if len(a) <= 1:
        return list(a), 0
    mid = len(a) // 2
    left, x = sort_count(a[:mid])
    right, y = sort_count(a[mid:])
    merged, i, j, cross = [], 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            cross += len(left) - i    # right[j] is smaller than every left[i:]
    merged += left[i:] + right[j:]
    return merged, x + y + cross


def power(base, exp, mod):
    """base ** exp % mod with O(log exp) multiplications."""
    if exp == 0:
        return 1 % mod
    half = power(base, exp // 2, mod)
    result = half * half % mod
    return result * base % mod if exp % 2 else result


if __name__ == "__main__":
    print(sort_count([5, 2, 4, 7, 1, 3, 2, 6]))  # ([1, 2, 2, 3, 4, 5, 6, 7], 14)
    print(power(3, 200, 1_000_000_007))          # 136318165

python divide_and_conquer.py