BZOJ 3453 - tyvj 1858 XLkxc（插值+推式子）

题面传送门

首先根据我们刚学插值时学的理论知识，\(f(i)\) 是关于 \(i\) 的 \(k+1\) 次多项式。而 \(g(x)\) 是 \(f(x)\) 的前缀和，根据有限微积分那一套理论，\(g(x)\) 是关于 \(x\) 的 \(k+2\) 次多项式。注意到此题 \(k\) 数据范围不过 \(10^2\) 级别，因此我们可以考虑把 \(g\) 多项式的系数插出来。我们代入 \(k+3\) 个点值 \(1,2,3,\cdots,k+3\)，预处理出 \(\prod\limits_{i=1}^{k+3}(x-i)\)，这样每次相当于多项式除以二项式，可以 \(\Theta(k)\) 地计算除法运算的结果，这样我们可以在 \(\Theta(k^2)\) 的时间内计算出 \(g(x)\) 的系数。不妨设 \(g(x)=\sum\limits_{i=0}^{k+2}b_ix^i\)

下面开始推式子：

\[\begin{aligned}
ans&=\sum\limits_{i=0}^ng(a+id)\\
&=\sum\limits_{i=0}^n\sum\limits_{j=0}^{k+2}b_j(a+id)^j\\
&=\sum\limits_{j=0}^{k+2}b_j\sum\limits_{i=0}^n\sum\limits_{l=0}^ja^l(id)^{j-l}\dbinom{j}{l}\\
&=\sum\limits_{j=0}^{k+2}b_j\sum\limits_{l=0}^ja^ld^{j-l}\dbinom{j}{l}\sum\limits_{i=0}^ni^{j-l}
\end{aligned}
\]

后面一个 \(\sum\) 里的东西可以插值求出。注意本质不同的 \(j-l\) 只有 \(k+3\) 个，因此只用插 \(k+3\) 次值，总复杂度 \(\Theta(k^2)\)

const int MAXN=126;

int k,a,n,d;

int qpow(int x,int e){

	int ret=1;

	for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;

	return ret;

}

int fac[MAXN+5],ifac[MAXN+5];

void init_fac(int n){

	for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;

	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;

}

int binom(int n,int k){return 1ll*fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;}

int sum[MAXN+5],pre[MAXN+5],suf[MAXN+5],b[MAXN+5],s[MAXN+5];

int calc_sum(int n,int k){//\sum\limits_{i=0}^ni^k

	if(!k) return n+1;

	for(int i=1;i<=k+2;i++) sum[i]=(0ll+sum[i-1]+qpow(i,k))%MOD;

	pre[0]=suf[k+3]=1;int res=0;

	for(int i=1;i<=k+2;i++) pre[i]=1ll*pre[i-1]*(n-i+MOD)%MOD;

	for(int i=k+2;i;i--) suf[i]=1ll*suf[i+1]*(n-i+MOD)%MOD;

	for(int i=1;i<=k+2;i++){

		int coef=1ll*pre[i-1]*suf[i+1]%MOD;

		coef=1ll*coef*ifac[k+2-i]%MOD*ifac[i-1]%MOD;

		if((k+2-i)&1) coef=MOD-coef;

		res=(0ll+res+1ll*coef*sum[i])%MOD;

	} return res;

}

int ff[MAXN+5];

void add(int v){

	static int tmp[MAXN+5];memset(tmp,0,sizeof(tmp));

	for(int i=0;i<=k+3;i++) tmp[i]=(0ll+((!i)?0:ff[i-1])-1ll*ff[i]*v%MOD+MOD)%MOD;

	for(int i=0;i<=k+3;i++) ff[i]=tmp[i];

}

void div(int v){

	static int tmp[MAXN+5];

	memset(tmp,0,sizeof(tmp));

	int iv=qpow(MOD-v,MOD-2);

	for(int i=0;i<=k+3;i++){

		tmp[i]=(0ll+ff[i]-((!i)?0:tmp[i-1])+MOD)%MOD;

		tmp[i]=1ll*tmp[i]*iv%MOD;

	}

	for(int i=0;i<=k+3;i++) ff[i]=tmp[i];

//	for(int i=0;i<=k+3;i++) printf("%d%c",ff[i]," \n"[i==k+3]);

}

void calc_b(){

	memset(b,0,sizeof(b));

	for(int i=1;i<=k+3;i++) sum[i]=(0ll+sum[i-1]+qpow(i,k))%MOD;

	for(int i=1;i<=k+3;i++) sum[i]=(0ll+sum[i-1]+sum[i])%MOD;

	memset(ff,0,sizeof(ff));ff[0]=1;

	for(int i=1;i<=k+3;i++) add(i);

//	for(int i=0;i<=k+3;i++) printf("%d%c",ff[i]," \n"[i==k+3]);

	for(int i=1;i<=k+3;i++){

		div(i);int mul=1;

		for(int j=1;j<=k+3;j++) if(i^j) mul=1ll*mul*(i-j+MOD)%MOD;

		mul=1ll*qpow(mul,MOD-2)*sum[i]%MOD;

		for(int j=0;j<=k+2;j++) b[j]=(0ll+b[j]+1ll*ff[j]*mul%MOD)%MOD;

		add(i);

	}

}

void solve(){

	scanf("%d%d%d%d",&k,&a,&n,&d);calc_b();int ans=0;

//	for(int i=0;i<=k+2;i++) printf("%d%c",b[i]," \n"[i==k+2]);

	for(int j=0;j<=k+2;j++) s[j]=calc_sum(n,j);

	for(int j=0;j<=k+2;j++) for(int l=0;l<=j;l++){

		int coef=1ll*b[j]*binom(j,l)%MOD*qpow(a,l)%MOD*qpow(d,j-l)%MOD;

		ans=(0ll+ans+1ll*coef*s[j-l]%MOD)%MOD;

	} printf("%d\n",ans);

}

int main(){

	init_fac(MAXN);

	int qu;scanf("%d",&qu);while(qu--) solve();

	return 0;

}

/*

1

2 5 2 5

6755

*/

巴特西

BZOJ 3453 - tyvj 1858 XLkxc（插值+推式子）

最新文章

热门文章