某考试 T2 sum

为什么其他人都是插值套插值啊，，，，就我是XJB做的吗2333

k次多项式的前缀和可以表示成k+1次多项式，用两次这个玩意就可以发现g可以表示成一个k+2次多项式。

然后我的做法是把g用拉格朗日插值+暴力多项式乘法乘出来，通过其他方法合并g(a),g(a+d),,,,,g(a+nd)。

假设我们现在把g的多项式的每个指数的系数都求出来了，设x^i前的系数是b[i]，

那么答案显然就是b[0] * a^0 + b[1] * a^1 + b[2] * a^2 +....b[k+2] * a^(k+2) + b[0] * (a+d)^0 + b[1] * (a+d)^1 + b[2] * (a+d)^2 +....b[k+2] * (a+d)^(k+2)+......

然后我们可以把次数一样的合并到一个类里，提一个b[]出来，里面的求和只需要把括号拆了之后推一推，然后你就会发现还需要组合数和自然幂数前缀和。

所以我们在之前预处理一下组合数还有 1到n 的 1-k+2 次前缀和，就可以直接计算了。

不过这个算法的瓶颈不在这里，这些计算的复杂度只是O(K^2)的。

前面的暴力多项式乘法才是这个算法的瓶颈，是O(K^3)的，不过足够通过本题了2333 (反正好像直接插值套插值也要 O(N^3)吧)。

至于前面的拉格朗日插值部分我就不说了，反正就算我说了会的还是会不会的还是不会2333。

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#define ll long long

using namespace std;

const int maxn=405;

const int ha=1234567891;

inline ll add(ll x,ll y){

	x+=y;

	return x>=ha?x-ha:x;

}

struct node{

	ll tp,a[maxn];

	inline void clear(){

		tp=0;

		memset(a,0,sizeof(a));

	}

	node operator +(const node &u)const{

		node r; r.clear();

		r.tp=max(tp,u.tp);

		for(int i=0;i<=r.tp;i++) r.a[i]=add(a[i],u.a[i]);

		return r;

	}

	node operator *(const node &u)const{

		node r; r.clear();

		r.tp=tp+u.tp;

		for(int i=0;i<=tp;i++)

		    for(int j=0;j<=u.tp;j++) r.a[i+j]=add(r.a[i+j],a[i]*u.a[j]%ha);

		return r;

	}

	node operator *(const ll &u)const{

		node r; r.clear();

		r.tp=tp;

		for(int i=0;i<=tp;i++) r.a[i]=a[i]*u%ha;

		return r;

	}

}qz[maxn],hz[maxn],ANS;

ll K,A,N,D,T,L,jc[maxn];

ll f[maxn],g[maxn],ni[maxn];

ll C[maxn][maxn],sum[maxn];

inline ll ksm(ll x,ll y){

	ll an=1;

	for(;y;y>>=1,x=x*x%ha) if(y&1) an=an*x%ha;

	return an;

}

inline void prework(){

	L=K+3;

	for(int i=0;i<=L+1;i++) qz[i].clear(),hz[i].clear();

	ANS.clear();

}

inline void init(){

	C[0][0]=1;

	for(int i=1;i<=400;i++){

		C[i][0]=1;

		for(int j=1;j<=i;j++) C[i][j]=add(C[i-1][j-1],C[i-1][j]);

	}

    jc[0]=1,ni[0]=1;

	for(int i=1;i<=400;i++) jc[i]=jc[i-1]*(ll)i%ha,ni[i]=ksm(jc[i],ha-2);

}

inline ll calc(ll tmp){

	ll tot=0,INV=ksm(A,ha-2),base=ksm(A,tmp),d=1;

	for(int i=0;i<=tmp;i++,base=base*INV%ha,d=d*D%ha){

		tot=add(tot,sum[i]*C[tmp][i]%ha*base%ha*d%ha);

	}

	return tot;

}

inline void solve(){

	for(int i=1;i<=L;i++) f[i]=add(f[i-1],ksm(i,K));

	for(int i=1;i<=L;i++) g[i]=add(g[i-1],f[i]);

	//calc g

	qz[0].a[0]=hz[L+1].a[0]=1;

	for(int i=1;i<=L;i++){

		qz[i].a[0]=ha-i,qz[i].a[1]=1,qz[i].tp=1;

		hz[i]=qz[i];

	}

	for(int i=1;i<L;i++) qz[i]=qz[i-1]*qz[i];

	for(int i=L;i>1;i--) hz[i]=hz[i+1]*hz[i];

	for(int i=1;i<=L;i++) ANS=ANS+(qz[i-1]*hz[i+1])*(g[i]*ni[i-1]%ha*ni[L-i]%ha*(((L-i)&1)?ha-1:1)%ha);

	//g is OK!

	ll ans=0; sum[0]=N+1;

	for(int i=1;i<=ANS.tp;i++){

		sum[i]=ksm(N+1,i+1);

		for(int j=0;j<i;j++) sum[i]=add(sum[i],ha-C[i+1][i+1-j]*sum[j]%ha);

		sum[i]=sum[i]*ksm(i+1,ha-2)%ha;

	}

	for(int i=0;i<=ANS.tp;i++) ans=add(ans,ANS.a[i]*calc(i)%ha);

	printf("%lld\n",ans);

}

int main(){

//	freopen("sum.in","r",stdin);

//	freopen("sum.out","w",stdout);

	scanf("%lld",&T);

	init();

	while(T--){

		scanf("%lld%lld%lld%lld",&K,&A,&N,&D);

		prework();

		solve();

	}

	return 0;

}

巴特西

某考试 T2 sum

最新文章

热门文章