import time


def add_matrix(a, b):
    return [[a[i][j] + b[i][j] for j in range(len(a))] for i in range(len(a))]


def sub_matrix(a, b):
    return [[a[i][j] - b[i][j] for j in range(len(a))] for i in range(len(a))]


# Standard multiplication: O(n^3) time and O(n^2) space.
def standard_matrix_multiply(a, b):
    n = len(a)
    if len(b) != n or any(len(row) != n for row in a + b):
        raise ValueError("Both matrices must be square and have the same size.")

    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                result[i][j] += a[i][k] * b[k][j]
    return result


# Strassen multiplication: O(n^log2(7)) time and O(n^2) space.
def strassen_matrix_multiply(a, b, leaf_size=2):
    n = len(a)
    if n == 0 or n & (n - 1):
        raise ValueError("Matrix size must be a positive power of 2.")
    if leaf_size < 1:
        raise ValueError("Leaf size must be positive.")
    if len(b) != n or any(len(row) != n for row in a + b):
        raise ValueError("Both matrices must be square and have the same size.")
    if n <= leaf_size:
        return standard_matrix_multiply(a, b)

    mid = n // 2
    a11, a12 = [row[:mid] for row in a[:mid]], [row[mid:] for row in a[:mid]]
    a21, a22 = [row[:mid] for row in a[mid:]], [row[mid:] for row in a[mid:]]
    b11, b12 = [row[:mid] for row in b[:mid]], [row[mid:] for row in b[:mid]]
    b21, b22 = [row[:mid] for row in b[mid:]], [row[mid:] for row in b[mid:]]

    m1 = strassen_matrix_multiply(add_matrix(a11, a22), add_matrix(b11, b22), leaf_size)
    m2 = strassen_matrix_multiply(add_matrix(a21, a22), b11, leaf_size)
    m3 = strassen_matrix_multiply(a11, sub_matrix(b12, b22), leaf_size)
    m4 = strassen_matrix_multiply(a22, sub_matrix(b21, b11), leaf_size)
    m5 = strassen_matrix_multiply(add_matrix(a11, a12), b22, leaf_size)
    m6 = strassen_matrix_multiply(sub_matrix(a21, a11), add_matrix(b11, b12), leaf_size)
    m7 = strassen_matrix_multiply(sub_matrix(a12, a22), add_matrix(b21, b22), leaf_size)

    c11 = add_matrix(sub_matrix(add_matrix(m1, m4), m5), m7)
    c12 = add_matrix(m3, m5)
    c21 = add_matrix(m2, m4)
    c22 = add_matrix(add_matrix(sub_matrix(m1, m2), m3), m6)
    result = [[0] * n for _ in range(n)]

    for i in range(mid):
        for j in range(mid):
            result[i][j] = c11[i][j]
            result[i][j + mid] = c12[i][j]
            result[i + mid][j] = c21[i][j]
            result[i + mid][j + mid] = c22[i][j]

    return result


def get_matrix_input(name, n):
    matrix = []
    for i in range(n):
        while True:
            try:
                row = [int(value) for value in input(f"Matrix {name}, row {i + 1}: ").split()]
            except ValueError:
                print(f"Enter {n} integers.")
                continue
            if len(row) == n:
                matrix.append(row)
                break
            print(f"Enter {n} integers.")
    return matrix


def print_matrix(matrix):
    for row in matrix:
        print(*row)


if __name__ == "__main__":
    while True:
        try:
            n = int(input("Enter a positive power-of-2 matrix dimension: "))
        except ValueError:
            print("Enter a positive power of 2.")
            continue
        if n > 0 and n & (n - 1) == 0:
            break
        print("Enter a positive power of 2.")

    a = get_matrix_input("A", n)
    b = get_matrix_input("B", n)

    start = time.perf_counter()
    standard = standard_matrix_multiply(a, b)
    standard_time = time.perf_counter() - start

    start = time.perf_counter()
    strassen = strassen_matrix_multiply(a, b, leaf_size=1)
    strassen_time = time.perf_counter() - start

    print("Standard multiplication:")
    print_matrix(standard)
    print("Strassen multiplication:")
    print_matrix(strassen)
    print(f"Standard time: {standard_time * 1000:.4f} ms")
    print(f"Strassen time: {strassen_time * 1000:.4f} ms")
