拉格朗日插值优化 dp

#include
using namespace std;
int k,n,md;
int fac[1005],inv[1005],ifac[1005];
inline void init(){
	fac[0]=fac[1]=inv[0]=inv[1]=ifac[0]=ifac[1]=1;
	for(int i=2;i<=2*n+1;i++)fac[i]=1ll*fac[i-1]*i%md;
	for(int i=2;i<=2*n+1;i++)inv[i]=1ll*(md-md/i)*inv[md%i]%md;
	for(int i=2;i<=2*n+1;i++)ifac[i]=1ll*ifac[i-1]*inv[i]%md;
}
int pre[1005],suf[1005];
inline int lag(int *f,int len,int x){
	int res=0;pre[0]=x%md;suf[len+1]=1;
	for(int i=1;i<=len;i++)pre[i]=1ll*pre[i-1]*(x-i)%md;
	for(int i=len;i>=0;i--)suf[i]=1ll*suf[i+1]*(x-i)%md;
	for(int i=0;i<=len;i++){
		int tmp=1ll*f[i]*ifac[i]%md*ifac[len-i]%md*((len-i)&1?md-1:1)%md;
		if(i)tmp=1ll*tmp*pre[i-1]%md;
		if(i!=len)tmp=1ll*tmp*suf[i+1]%md;
		res=(res+tmp)%md;
	}
	return res;
}
int dp[505][1005];
int main(){
	scanf("%d%d%d",&k,&n,&md);
	init();
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		int sum=dp[i-1][0];
		for(int j=1;j<=2*n+1;j++){
			dp[i][j]=1ll*j*sum%md;
			sum=(sum+dp[i-1][j])%md;
		}
	}
	for(int i=1;i<=2*n+1;i++)dp[n][i]=(dp[n][i]+dp[n][i-1])%md;
	dp[n][0]=lag(dp[n],2*n+1,k);
	printf("%lld",(1ll*dp[n][0]*fac[n]%md+md)%md);


	return 0;
}

#include
using namespace std;
const int md=1e9+7;
int T;
long long n;
int m;
int a[55],k,f[55],pre[55],suf[55],fac[55];
map ma;
inline int pwr(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=1ll*res*x%md;
        x=1ll*x*x%md;y>>=1;
    }
    return res;
}
inline int lag(long long x){
    if(x<=k+2)return f[x];
    int res=0;pre[0]=1;suf[k+3]=1;x%=md;
    for(int i=1;i<=k+2;i++)pre[i]=1ll*pre[i-1]*(x-i)%md;
    for(int i=k+2;i>=1;i--)suf[i]=1ll*suf[i+1]*(x-i)%md;
    for(int i=1;i<=k+2;i++){
        int x=1ll*pre[i-1]*suf[i+1]%md;
        int fu=((k+2-i)&1)?-1:1;
        int y=1ll*fac[i-1]*fac[k+2-i]%md*fu%md;
        res=(res+1ll*f[i]*x%md*pwr(y,md-2)%md)%md;
    }
    return (res+md)%md;
}
inline void init(){
    fac[0]=1;
    for(int i=1;i<=52;i++)fac[i]=1ll*fac[i-1]*i%md;
}
int main(){
    scanf("%d",&T);init();
	while(T--){
        scanf("%lld%d",&n,&m);k=m+1;
        ma.clear();
        for(int i=1;i<=m;i++)scanf("%d",&a[i]),ma[a[i]]=1;
        sort(a+1,a+m+1);
        while(ma[n])n--,k--,m--;
        for(int i=1;i<=k+2;i++)f[i]=(f[i-1]+pwr(i,k))%md;
        int res=lag(n);
        for(int i=1;i<=m;i++)res=(res-pwr(a[i],k))%md;
        for(int i=1;i<=m;i++)res=(res+lag(n-a[i]))%md;
        for(int i=1;i<=m;i++){
            for(int j=i-1;j>=1;j--){
				res=(res-pwr(a[i]-a[j],k))%md;
			}
		}
        printf("%d\n",(res+md)%md);
    }
    return 0;
}

#include
using namespace std;
int n;
const int md=1e9+7;
namespace Lagrange{
	int pre1[305],suf1[305],pre2[305],suf2[305],inv[305];
	inline void init(){
		inv[0]=inv[1]=1;
		for(int i=2;i<=n;i++)inv[i]=1ll*(md-md/i)*inv[md%i]%md;
	}
	inline int lag(int *y,int k,int t){
		if(t<=k)return y[t];
		pre1[0]=suf1[0]=suf2[k+1]=1;pre2[0]=t%md;
		for(int i=1;i<=k;i++)pre1[i]=1ll*pre1[i-1]*inv[i]%md;
		for(int i=1;i<=k;i++)suf1[i]=1ll*suf1[i-1]*-inv[i]%md;
		for(int i=1;i<=k;i++)pre2[i]=1ll*pre2[i-1]*(t-i)%md;
		for(int i=k;i>=1;i--)suf2[i]=1ll*suf2[i+1]*(t-i)%md;
		int res=0;
		for(int i=0;i<=k;i++)res=(res+1ll*y[i]*pre1[i]%md*suf1[k-i]%md*(i?pre2[i-1]:1)%md*suf2[i+1])%md;
		return (res+md)%md;
	}
}
using Lagrange::lag;
int A[305],B[305],lim;
int vis[305][305],cnt,L[3005],R[3005],dp[3005][10005];
void build(int l,int r){
	if(l>r||vis[l][r])return ;
	vis[l][r]=++cnt;L[cnt]=l;R[cnt]=r;
	if(l==r)return ;
	for(int i=l;i<=r;i++){
		if(abs((r-i)-(i-l))>2)continue;
		build(l,i-1);build(i+1,r);
	}
}
bool used[305][305];
void solve(int l,int r,int len,int v){
	if(l>r||used[l][r])return ;
	int id=vis[l][r];used[l][r]=1;
	for(int i=1;i<=len;i++)dp[id][i]=0;
	for(int i=l;i<=r;i++){
		if(abs((r-i)-(i-l))>2||A[i]>v||B[i]<=v)continue;
		solve(l,i-1,len,v);solve(i+1,r,len,v);
		for(int j=1;j<=len;j++)dp[id][j]=(dp[id][j]+1ll*dp[vis[l][i-1]][j]*dp[vis[i+1][r]][j-1])%md;
	}
	for(int i=1;i<=len;i++)dp[id][i]=(dp[id][i]+dp[id][i-1])%md;
}
inline void Getval(int l,int r){
	for(int i=1;i<=cnt;i++)dp[i][0]=lag(dp[i],R[i]-L[i]+1,r-l+1);
	for(int l=1;l<=n;l++)for(int r=l;r<=n;r++)used[l][r]=0;
}
vector hsh;
int main(){
	scanf("%d",&n);
	Lagrange::init();
	for(int i=1;i<=n;i++)scanf("%d%d",&A[i],&B[i]),++B[i];
	for(int i=1;i<=n;i++)hsh.push_back(A[i]);
	for(int i=1;i<=n;i++)hsh.push_back(B[i]);
	sort(hsh.begin(),hsh.end());
	hsh.erase(unique(hsh.begin(),hsh.end()),hsh.end());
	for(int i=1;i<=n;i++)A[i]=upper_bound(hsh.begin(),hsh.end(),A[i])-hsh.begin();
	for(int i=1;i<=n;i++)B[i]=upper_bound(hsh.begin(),hsh.end(),B[i])-hsh.begin();
	for(int i=0;i<=n;i++)dp[0][i]=1;
	build(1,n);
	for(int i=0;i+1