多项式插值法 - 牛顿多项式插值法

时间复杂度较为优秀，为$O(k)$。连续函数：

#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=a;i<=b;i++)
using namespace std;
typedef long long ll;
typedef long double type;
class NewtonPoly{
	public:
	type f[105],d[105],x[105];
	ll n=0;
	void add(type X,type Y){
		x[n]=X,f[n]=Y;
		rep(i,1,n)f[n-i]=(f[n-i+1]-f[n-i])/(x[n]-x[n-i]);
		d[n++]=f[0];
	}
	type cal(type X){
		type ans=0,t=1;
		rep(i,0,n-1)ans+=d[i]*t,t*=X-x[i];
		return ans;
	}
}P;
int main(){
	P.add(0,0);
	P.add(1,1);
	P.add(2,5);
	P.add(3,15);
	P.add(4,35);
	type x;
	while(cin>>x)cout<<P.cal(x)<<endl;
	return 0;
}

南京G题AC代码（600ms，离散函数）：

#include <bits/stdc++.h>
#define rep(i,a,b) for(LL i=a;i<=b;i++)
using namespace std;
typedef long long LL;
typedef long long type;
const LL mod=1e9+7;
LL Pow(LL a,LL b,LL mod){
    LL res=1;
    while(b>0){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
class NewtonPoly{
	public:
	type f[105],d[105],x[105];
	LL n=0;
	void add(type X,type Y){
		x[n]=X,f[n]=Y;
		rep(i,1,n)f[n-i]=(f[n-i+1]-f[n-i])*Pow(x[n]-x[n-i],mod-2,mod)%mod;
		d[n++]=f[0];
	}
	type cal(type X){
		type ans=0,t=1;
		rep(i,0,n-1)ans=(ans+d[i]*t)%mod,t=t*(X-x[i])%mod;
		return (ans+mod)%mod;
	}
}P;
int main(){
	P.add(0,0);
	P.add(1,1);
	P.add(2,5);
	P.add(3,15);
	P.add(4,35);
	type x;
	int t;scanf("%d",&t);
	while(t--)scanf("%lld",&x),printf("%lld\n",P.cal(x));
	return 0;
}