interpolate (one point)
(FPS/interpolate.hpp)

• View this file on GitHub
• Last update: 2024-01-12 04:16:01+09:00
• Include: #include "FPS/interpolate.hpp"

Required by

• $\sum_{k} r^k\cdot poly(k)$ (FPS/sumofpolyexp.hpp)

Verified with

• Verify/LC_sum_of_exponential_times_polynomial.test.cpp
• Verify/LC_sum_of_exponential_times_polynomial_limit.test.cpp

Code

#pragma once

template<typename T>T Interpolate(vector<T>& ys,ll t){ // f(0),..,f(d) -> f(t)
    int d=ys.size()-1;
    if(t<=d)return ys[t];
    vector<T> L(d+1,1),R(d+1,1);
    rep(i,0,d)L[i+1]=L[i]*(t-i);
    for(int i=d;i;i--)R[i-1]=R[i]*(t-i);
    T ret;
    rep(i,0,d+1){
        T add=ys[i]*L[i]*R[i]*Fact<T>(i,1)*Fact<T>(d-i,1);
        if((d-i)&1)ret-=add;
        else ret+=add;
    }
    return ret;
}

/**
 * @brief interpolate (one point)
*/

#line 2 "FPS/interpolate.hpp"

template<typename T>T Interpolate(vector<T>& ys,ll t){ // f(0),..,f(d) -> f(t)
    int d=ys.size()-1;
    if(t<=d)return ys[t];
    vector<T> L(d+1,1),R(d+1,1);
    rep(i,0,d)L[i+1]=L[i]*(t-i);
    for(int i=d;i;i--)R[i-1]=R[i]*(t-i);
    T ret;
    rep(i,0,d+1){
        T add=ys[i]*L[i]*R[i]*Fact<T>(i,1)*Fact<T>(d-i,1);
        if((d-i)&1)ret-=add;
        else ret+=add;
    }
    return ret;
}

/**
 * @brief interpolate (one point)
*/

Back to top page