// Multiplicación de enteros no negativos de muchos dígitos.
// Un número es un vector de dígitos en base 10, del menos significativo al más significativo,
// sin ceros a la izquierda. El cero es el vector vacío.
#ifndef KARATSUBA_H
#define KARATSUBA_H

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <string>
#include <vector>

using Digits = std::vector<int>;

inline void trim(Digits& a) {
    while (!a.empty() && a.back() == 0) {
        a.pop_back();
    }
}

inline Digits from_string(const std::string& text) {
    Digits a;
    for (auto it = text.rbegin(); it != text.rend(); ++it) {
        a.push_back(*it - '0');
    }
    trim(a);
    return a;
}

inline std::string to_string(const Digits& a) {
    if (a.empty()) {
        return "0";
    }
    std::string text;
    for (auto it = a.rbegin(); it != a.rend(); ++it) {
        text.push_back(static_cast<char>('0' + *it));
    }
    return text;
}

inline Digits add(const Digits& a, const Digits& b) {
    Digits sum;
    sum.reserve(std::max(a.size(), b.size()) + 1);
    int carry = 0;
    for (std::size_t i = 0; i < a.size() || i < b.size() || carry != 0; i++) {
        int value = carry;
        if (i < a.size()) {
            value += a[i];
        }
        if (i < b.size()) {
            value += b[i];
        }
        sum.push_back(value % 10);
        carry = value / 10;
    }
    return sum;
}

// Resta a - b. Requiere a >= b.
inline Digits subtract(const Digits& a, const Digits& b) {
    Digits result = a;
    int borrow = 0;
    for (std::size_t i = 0; i < a.size(); i++) {
        int value = a[i] - borrow - (i < b.size() ? b[i] : 0);
        borrow = value < 0 ? 1 : 0;
        result[i] = value + 10 * borrow;
    }
    assert(borrow == 0);
    trim(result);
    return result;
}

// Multiplica por 10^positions.
inline Digits shifted(const Digits& a, std::size_t positions) {
    if (a.empty()) {
        return a;
    }
    Digits result(positions, 0);
    result.insert(result.end(), a.begin(), a.end());
    return result;
}

// Los dígitos desde `start` hasta antes de `stop`, sin ceros a la izquierda.
inline Digits slice(const Digits& a, std::size_t start, std::size_t stop) {
    start = std::min(start, a.size());
    stop = std::min(stop, a.size());
    Digits part(a.begin() + static_cast<long>(start), a.begin() + static_cast<long>(stop));
    trim(part);
    return part;
}

// La multiplicación de la escuela: cada dígito de a con cada dígito de b.
// `digit_products` cuenta los productos de un dígito por un dígito.
inline Digits school_multiply(const Digits& a, const Digits& b, long long& digit_products) {
    if (a.empty() || b.empty()) {
        return {};
    }
    std::vector<long long> cells(a.size() + b.size(), 0);
    for (std::size_t i = 0; i < a.size(); i++) {
        for (std::size_t j = 0; j < b.size(); j++) {
            cells[i + j] += a[i] * b[j];
        }
    }
    digit_products += static_cast<long long>(a.size()) * static_cast<long long>(b.size());
    Digits result(cells.size());
    long long carry = 0;
    for (std::size_t i = 0; i < cells.size(); i++) {
        long long value = cells[i] + carry;
        result[i] = static_cast<int>(value % 10);
        carry = value / 10;
    }
    trim(result);
    return result;
}

// Karatsuba: x = a·10^m + b, y = c·10^m + d, y tres productos en vez de cuatro.
// Con n <= threshold usa la multiplicación de la escuela. threshold debe ser al menos 3: a + b
// puede tener un dígito más que sus partes, y solo con n >= 4 los subproblemas son más cortos que n.
inline Digits karatsuba(const Digits& x, const Digits& y, std::size_t threshold, long long& digit_products) {
    assert(threshold >= 3);
    std::size_t n = std::max(x.size(), y.size());
    if (x.empty() || y.empty()) {
        return {};
    }
    if (n <= threshold) {
        return school_multiply(x, y, digit_products);
    }
    std::size_t m = n / 2;
    Digits b = slice(x, 0, m);
    Digits a = slice(x, m, x.size());
    Digits d = slice(y, 0, m);
    Digits c = slice(y, m, y.size());

    Digits ac = karatsuba(a, c, threshold, digit_products);
    Digits bd = karatsuba(b, d, threshold, digit_products);
    Digits sums = karatsuba(add(a, b), add(c, d), threshold, digit_products);
    Digits middle = subtract(subtract(sums, ac), bd);  // ad + bc

    Digits result = add(add(shifted(ac, 2 * m), shifted(middle, m)), bd);
    trim(result);
    return result;
}

#endif