This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ningenMe/compro-library
/* * @title Polynomial - 多項式補間 * @docs md/math/Polynomial.md */ template<class T> class Polynomial{ public: //O(N^2) inline static vector<T> interpolation(const vector<T>& x,const vector<T>& y) { assert(x.size()==y.size()); int n = x.size(); vector<T> dp(n+1,0),tp(n+1),res(n,0); dp[0] = 1; for(int i=0;i<n;++i) { for(int j=0;j<=n;++j) tp[j] = 0; for(int j=0;j<=i;++j) { tp[j+0] += dp[j]*(-x[i]); tp[j+1] += dp[j]*1; } swap(dp,tp); } for(int i=0;i<n;++i) { if(x[i].x == 0) { for(int j=0;j<n;++j) { tp[j] = dp[j+1]; } } else { T ix = T(1) / x[i]; tp[0] = dp[0]*(-ix); for(int j=1;j<n;++j) { tp[j] = (dp[j]-tp[j-1])*(-ix); } } T base = 1,c = 0; for(int j=0;j<n;++j) { c += base*tp[j]; base *= x[i]; } c = y[i] / c; for(int j=0;j<n;++j) { res[j] += c*tp[j]; } } return res; } //O(N \log mod) inline static T interpolation_arithmetic(const T a0,const T d, const vector<T>& y,const T x) { int n = y.size(); T gx = 1,fx = 0; vector<T> gxi(n,1); for(int i=0;i<n;++i) gx *= x-(a0 + d*i); for(int i=1;i<n;++i) gxi[0] *= (-d*i); for(int i=1;i<n;++i) gxi[i] = gxi[i-1] * (d*i) / (d*(i-n)); for(int i=0;i<n;++i) fx += (y[i] / gxi[i]) * (gx / (x - (a0 + d*i))); return fx; } //O(N) inline static T eval(const vector<T>& f,T x) { T base = 1, res = 0; for(int i=0;i<f.size(); ++i) { res += base*f[i]; base *= x; } return res; } };
#line 1 "lib/30-math/Polynomial.cpp" /* * @title Polynomial - 多項式補間 * @docs md/math/Polynomial.md */ template<class T> class Polynomial{ public: //O(N^2) inline static vector<T> interpolation(const vector<T>& x,const vector<T>& y) { assert(x.size()==y.size()); int n = x.size(); vector<T> dp(n+1,0),tp(n+1),res(n,0); dp[0] = 1; for(int i=0;i<n;++i) { for(int j=0;j<=n;++j) tp[j] = 0; for(int j=0;j<=i;++j) { tp[j+0] += dp[j]*(-x[i]); tp[j+1] += dp[j]*1; } swap(dp,tp); } for(int i=0;i<n;++i) { if(x[i].x == 0) { for(int j=0;j<n;++j) { tp[j] = dp[j+1]; } } else { T ix = T(1) / x[i]; tp[0] = dp[0]*(-ix); for(int j=1;j<n;++j) { tp[j] = (dp[j]-tp[j-1])*(-ix); } } T base = 1,c = 0; for(int j=0;j<n;++j) { c += base*tp[j]; base *= x[i]; } c = y[i] / c; for(int j=0;j<n;++j) { res[j] += c*tp[j]; } } return res; } //O(N \log mod) inline static T interpolation_arithmetic(const T a0,const T d, const vector<T>& y,const T x) { int n = y.size(); T gx = 1,fx = 0; vector<T> gxi(n,1); for(int i=0;i<n;++i) gx *= x-(a0 + d*i); for(int i=1;i<n;++i) gxi[0] *= (-d*i); for(int i=1;i<n;++i) gxi[i] = gxi[i-1] * (d*i) / (d*(i-n)); for(int i=0;i<n;++i) fx += (y[i] / gxi[i]) * (gx / (x - (a0 + d*i))); return fx; } //O(N) inline static T eval(const vector<T>& f,T x) { T base = 1, res = 0; for(int i=0;i<f.size(); ++i) { res += base*f[i]; base *= x; } return res; } };