// Matrices módulo p y el algoritmo de Freivalds: comprobar si A·B = C sin multiplicar A por B.
// Todo se calcula módulo p. Las entradas de las matrices están en {0, ..., p - 1}.
#pragma once

#include <cassert>
#include <cstddef>
#include <cstdint>
#include <random>
#include <vector>

using Vector = std::vector<std::uint64_t>;
using Matrix = std::vector<Vector>;

// El primo de la semana: 10^9 + 7. Es menor que 2^30.
constexpr std::uint64_t kPrime = 1'000'000'007;

// a·b módulo p. Con a, b < p < 2^32, el producto es menor que 2^64 y cabe en 64 bits sin signo.
// En 32 bits no cabe: (p - 1)·(p - 1) tiene unas 18 cifras.
inline std::uint64_t mul_mod(std::uint64_t a, std::uint64_t b, std::uint64_t p) {
    assert(p < (std::uint64_t{1} << 32) && a < p && b < p);
    return a * b % p;
}

// El producto de una matriz de n×n por un vector: n² multiplicaciones.
inline Vector times(const Matrix& m, const Vector& x, std::uint64_t p) {
    Vector y(m.size(), 0);
    for (std::size_t i = 0; i < m.size(); i++) {
        for (std::size_t j = 0; j < x.size(); j++) {
            y[i] = (y[i] + mul_mod(m[i][j], x[j], p)) % p;
        }
    }
    return y;
}

// El producto exacto de dos matrices de n×n, por la definición: n³ multiplicaciones.
inline Matrix multiply(const Matrix& a, const Matrix& b, std::uint64_t p) {
    const std::size_t n = a.size();
    Matrix c(n, Vector(n, 0));
    for (std::size_t i = 0; i < n; i++) {
        for (std::size_t j = 0; j < n; j++) {
            for (std::size_t k = 0; k < n; k++) {
                c[i][j] = (c[i][j] + mul_mod(a[i][k], b[k][j], p)) % p;
            }
        }
    }
    return c;
}

// Una ronda con el vector r: ¿A·(B·r) = C·r? Son tres productos de matriz por vector.
// Si devuelve false, es seguro que A·B ≠ C. Si devuelve true, no se sabe.
inline bool freivalds_round(const Matrix& a, const Matrix& b, const Matrix& c, const Vector& r,
                            std::uint64_t p) {
    return times(a, times(b, r, p), p) == times(c, r, p);
}

// Un vector de n ceros y unos, cada uno con una moneda independiente: el bit más alto de un
// número de 64 bits del generador.
inline Vector random_bits(std::size_t n, std::mt19937_64& rng) {
    Vector r(n);
    for (std::uint64_t& bit : r) {
        bit = rng() >> 63;
    }
    return r;
}

// Freivalds con k rondas. Devuelve false ("distintos") apenas una ronda encuentra una diferencia,
// y true ("iguales") si ninguna la encuentra. Solo se puede equivocar al responder true.
inline bool freivalds(const Matrix& a, const Matrix& b, const Matrix& c, int k, std::mt19937_64& rng,
                      std::uint64_t p) {
    for (int round = 0; round < k; round++) {
        if (!freivalds_round(a, b, c, random_bits(a.size(), rng), p)) {
            return false;
        }
    }
    return true;
}

// Corre Freivalds con k rondas `runs` veces y cuenta cuántas responde "iguales".
// Si A·B ≠ C, ese número es la cantidad de fallos.
inline int count_equal_answers(const Matrix& a, const Matrix& b, const Matrix& c, int k, int runs,
                               std::mt19937_64& rng, std::uint64_t p) {
    int count = 0;
    for (int run = 0; run < runs; run++) {
        count += freivalds(a, b, c, k, rng, p) ? 1 : 0;
    }
    return count;
}

// Cuántos de los 2^n vectores de ceros y unos detectan que A·B ≠ C. Solo para n pequeño.
inline int count_detecting_vectors(const Matrix& a, const Matrix& b, const Matrix& c, std::uint64_t p) {
    const std::size_t n = a.size();
    assert(n < 20);
    int detected = 0;
    for (unsigned mask = 0; mask < (1u << n); mask++) {
        Vector r(n);
        for (std::size_t j = 0; j < n; j++) {
            r[j] = (mask >> (n - 1 - j)) & 1u;
        }
        detected += freivalds_round(a, b, c, r, p) ? 0 : 1;
    }
    return detected;
}

// Una matriz de n×n con entradas al azar en {0, ..., p - 1}.
// rng() % p no es exactamente uniforme, pero el sesgo es menor que 2^-33 y aquí no importa.
inline Matrix random_matrix(std::size_t n, std::mt19937_64& rng, std::uint64_t p) {
    Matrix m(n, Vector(n));
    for (Vector& row : m) {
        for (std::uint64_t& x : row) {
            x = rng() % p;
        }
    }
    return m;
}
