#include "math/lagrange_interpolation.hpp"
#pragma once #include<vector> /** * @brief ラグランジュ補完(連続点->一点) */ template<typename T> T lagrange_interpolation(std::vector<T>v,long long n){ long long k=v.size(); if(n<k)return v[n]; std::vector<T> tmp1(k+1,1),tmp2(k+1,1); T ans=0; for(int i=0;i<k;++i)tmp1[i]=(i?tmp1[i-1]:1)*(n-i); for(int i=k-1;i>=0;--i)tmp2[i]=(i<k-1?tmp2[i+1]:1)*(n-i); for(int i=0;i<k;++i){ ans+=v[i]*(i<k-1?tmp2[i+1]:1)*(i?tmp1[i-1]:1)/(T(k-1-i).fact()*T(i).fact()*T((k-1-i)%2?-1:1)); } return ans; }
#line 2 "math/lagrange_interpolation.hpp" #include<vector> /** * @brief ラグランジュ補完(連続点->一点) */ template<typename T> T lagrange_interpolation(std::vector<T>v,long long n){ long long k=v.size(); if(n<k)return v[n]; std::vector<T> tmp1(k+1,1),tmp2(k+1,1); T ans=0; for(int i=0;i<k;++i)tmp1[i]=(i?tmp1[i-1]:1)*(n-i); for(int i=k-1;i>=0;--i)tmp2[i]=(i<k-1?tmp2[i+1]:1)*(n-i); for(int i=0;i<k;++i){ ans+=v[i]*(i<k-1?tmp2[i+1]:1)*(i?tmp1[i-1]:1)/(T(k-1-i).fact()*T(i).fact()*T((k-1-i)%2?-1:1)); } return ans; }