main.py

def mult(m1, m2):
    a = len(m1)
    b = len(m2)
    c = len(m2[0])

    result = [[0] * c for _ in range(a)]

    for i in range(a):
        for j in range(c):
            result[i][j] = 0
            for k in range(b):
                result[i][j] += m1[i][k] * m2[k][j]

    return result


def exp(m, exp):
    a = len(m)
    result = [[1 if x == y else 0 for x in range(a)] for y in range(a)]

    while exp > 0:
        if exp & 1:
            result = mult(result, m)

        m = mult(m, m)
        exp >>= 1

    return result


def sum_from_1_to_n(n):
    """calculates sum(i for i in range(n)). O(log(n))"""
    matrix = [
        [1, 0, 1],  # counter
        [1, 1, 0],  # total
        [0, 0, 1],  # one
    ]

    initial_state = [
        [0],
        [0],
        [1],
    ]

    result = mult(exp(matrix, n), initial_state)

    return result[1][0]