为什么其他人都是插值套插值啊，，，，就我是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
",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;
}