// Evalúa recurrencias T(n) = a T(n/2) + f(n), con T(1) = 1, en las potencias de 2.
#pragma once

#include <cmath>
#include <vector>

// Devuelve T(2^k). f recibe k, de modo que f(k) es el valor de f en n = 2^k.
template <typename V, typename F>
V solve_power_of_two(int a, int k, F f) {
    V value = 1;
    for (int m = 1; m <= k; m++) {
        value = static_cast<V>(a) * value + f(m);
    }
    return value;
}

// El trabajo de cada nivel para n = 2^k. El nivel i tiene a^i subproblemas de tamaño 2^(k-i), y
// la última casilla son las hojas, cada una con T(1) = 1.
template <typename V, typename F>
std::vector<V> level_work(int a, int k, F f) {
    std::vector<V> levels;
    V nodes = 1;
    for (int i = 0; i < k; i++) {
        levels.push_back(nodes * f(k - i));
        nodes *= a;
    }
    levels.push_back(nodes);
    return levels;
}

// La f de cada recurrencia, en función de k = log n.
inline long double f_one(int) { return 1; }
inline long double f_n(int k) { return std::ldexp(1.0L, k); }
inline long double f_n2(int k) { return std::ldexp(1.0L, 2 * k); }
inline long double f_n_log_n(int k) { return k * std::ldexp(1.0L, k); }
inline long double f_n_over_log_n(int k) { return std::ldexp(1.0L, k) / k; }