Considerando que um polinômio de grau (k) pode ser determinado por (k+1) pontos, podemos definir: [p(x) = c_0 + c_1x + c_2x^2 + \dots + c_{n-1}x^{n-1} ]Montamos o sistema de equações: [\begin{cases}c_0 + c_1x_1 + c_2x_1^2 + \dots + c_{n-1}x_1^{n-1} = y_1\c_0 + c_1x_2 + c_2x_2^2 + \dots + c_{n-1}x_2^{n-1} = y_2\\dots\c_0 + c_1x_n + c_2x_n^2 + \dots + c_{n-1}x_n^{n-1} = y_n \end{cases} ]Este sistema pode ser resolvido por eliminação gaussiana com complexidade (O(n^3)). Fórmula de Interpolação de Lagrange

A fórmula direta de Lagrenge é: [p(x) = \sum_{i=1}^{n} y_i \prod_{j \neq i} \frac{x - x_j}{x_i - x_j} ]Implementação Básica

Aqui está uma implementação do método: ``` #include #include using namespace std;

const int MOD = 998244353;

long long potencia_mod(long long base, long long expoente, long long modulo) { long long resultado = 1; while (expoente > 0) { if (expoente & 1) resultado = resultado * base % modulo; base = base * base % modulo; expoente >>= 1; } return resultado; }

long long interpolacao_lagrange(vector& x, vector& y, long long ponto) { int n = x.size(); long long valor = 0;

for (int i = 0; i < n; i++) {
    long long termo = y[i];
    for (int j = 0; j < n; j++) {
        if (i != j) {
            long long numerador = (ponto - x[j] + MOD) % MOD;
            long long denominador = (x[i] - x[j] + MOD) % MOD;
            termo = termo * numerador % MOD;
            termo = termo * potencia_mod(denominador, MOD-2, MOD) % MOD;
        }
    }
    valor = (valor + termo) % MOD;
}
return valor;

}

Otimização para Pontos Equidistantes
------------------------------------

Quendo os pontos são equiidstantes, podemos otimizar o cálculo usando fatoriais: ```
#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000000007;
const int MAXN = 1000005;

long long fatorial[MAXN], inverso_fatorial[MAXN];

void precalcular_fatoriais(int limite) {
    fatorial[0] = 1;
    for (int i = 1; i <= limite; i++) {
        fatorial[i] = fatorial[i-1] * i % MOD;
    }
    inverso_fatorial[limite] = potencia_mod(fatorial[limite], MOD-2, MOD);
    for (int i = limite-1; i >= 0; i--) {
        inverso_fatorial[i] = inverso_fatorial[i+1] * (i+1) % MOD;
    }
}

long long soma_potencias_otimizada(long long n, long long k) {
    vector<long long> valores(k+3);
    valores[0] = 0;
    for (int i = 1; i <= k+2; i++) {
        valores[i] = (valores[i-1] + potencia_mod(i, k, MOD)) % MOD;
    }
    
    if (n <= k+2) return valores[n];
    
    vector<long long> prefixo(k+3), sufixo(k+3);
    prefixo[0] = 1;
    for (int i = 1; i <= k+2; i++) {
        prefixo[i] = prefixo[i-1] * ((n - i + MOD) % MOD) % MOD;
    }
    
    sufixo[k+3] = 1;
    for (int i = k+2; i >= 0; i--) {
        sufixo[i] = sufixo[i+1] * ((n - i + MOD) % MOD) % MOD;
    }
    
    long long resultado = 0;
    for (int i = 1; i <= k+2; i++) {
        long long termo = valores[i];
        termo = termo * prefixo[i-1] % MOD;
        termo = termo * sufixo[i+1] % MOD;
        termo = termo * inverso_fatorial[i-1] % MOD;
        termo = termo * inverso_fatorial[k+2-i] % MOD;
        
        if ((k+2-i) % 2 == 1) termo = MOD - termo;
        resultado = (resultado + termo) % MOD;
    }
    return resultado;
}