// Polinomios en una variable con coeficientes módulo p, y la prueba de identidad al azar:
// dos polinomios distintos de grado a lo sumo d coinciden en a lo sumo d puntos.
#pragma once

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

#include "freivalds.h"  // mul_mod

// Un polinomio por sus coeficientes: coefficients[i] es el de x^i, en {0, ..., p - 1}.
struct Polynomial {
    std::vector<std::uint64_t> coefficients;
};

// Un polinomio por sus factores: (x - roots[0])·(x - roots[1])···
struct Factored {
    std::vector<std::uint64_t> roots;
};

// Evalúa con la regla de Horner: d multiplicaciones para grado d.
inline std::uint64_t evaluate(const Polynomial& f, std::uint64_t x, std::uint64_t p) {
    std::uint64_t value = 0;
    for (std::size_t i = f.coefficients.size(); i > 0; i--) {
        value = (mul_mod(value, x, p) + f.coefficients[i - 1]) % p;
    }
    return value;
}

// Evalúa el producto factor por factor, sin desarrollarlo: d multiplicaciones.
inline std::uint64_t evaluate(const Factored& f, std::uint64_t x, std::uint64_t p) {
    std::uint64_t value = 1 % p;
    for (std::uint64_t root : f.roots) {
        value = mul_mod(value, (x + p - root % p) % p, p);
    }
    return value;
}

// Desarrolla el producto: multiplica por (x - raíz) una vez por cada factor.
inline Polynomial expand(const Factored& f, std::uint64_t p) {
    Polynomial result{{1 % p}};
    for (std::uint64_t root : f.roots) {
        const std::uint64_t minus_root = (p - root % p) % p;
        std::vector<std::uint64_t> next(result.coefficients.size() + 1, 0);
        for (std::size_t i = 0; i < result.coefficients.size(); i++) {
            next[i + 1] = (next[i + 1] + result.coefficients[i]) % p;
            next[i] = (next[i] + mul_mod(result.coefficients[i], minus_root, p)) % p;
        }
        result.coefficients = next;
    }
    return result;
}

// La prueba: evaluar los dos en un punto al azar de {0, ..., p - 1}.
// false: son distintos, con seguridad. true: coinciden en ese punto, y no se sabe más.
template <typename F, typename G>
bool agree_at_random_point(const F& f, const G& g, std::mt19937_64& rng, std::uint64_t p) {
    const std::uint64_t x = rng() % p;
    return evaluate(f, x, p) == evaluate(g, x, p);
}

// En cuántos de los p puntos coinciden. Solo para p pequeño.
template <typename F, typename G>
std::uint64_t count_agreements(const F& f, const G& g, std::uint64_t p) {
    std::uint64_t count = 0;
    for (std::uint64_t x = 0; x < p; x++) {
        count += evaluate(f, x, p) == evaluate(g, x, p) ? 1 : 0;
    }
    return count;
}

// Corre la prueba `runs` veces y cuenta cuántas responde "coinciden".
template <typename F, typename G>
int count_agree_answers(const F& f, const G& g, int runs, std::mt19937_64& rng, std::uint64_t p) {
    int count = 0;
    for (int run = 0; run < runs; run++) {
        count += agree_at_random_point(f, g, rng, p) ? 1 : 0;
    }
    return count;
}
