论文参考
https://arxiv.org/pdf/2008.08822.pdf
int t[N],p[N],q[N],dp[N],dq[N],ddp[N],ddq[N]; int coefficient(int n,int len) { int v=inv(2),wn=ksm(h,(mo-1)/(2*len)),wm=inv(wn); for(int i=0;i<len;i++)dp[i]=p[i],dq[i]=q[i]; ntt(dp,len,+1);ntt(dq,len,+1); while(n) { //ddp ddq for(int i=0;i<len;i++)ddp[2*i]=dp[i],ddq[2*i]=dq[i]; for(int i=0,w=1;i<len;i++,w=1ll*w*wn%mo)p[i]=1ll*p[i]*w%mo,q[i]=1ll*q[i]*w%mo; ntt(p,len,+1);ntt(q,len,+1); for(int i=0;i<len;i++)ddp[2*i+1]=p[i],ddq[2*i+1]=q[i]; //p dp for(int i=0;i<2*len;i++)t[i]=1ll*ddp[i]*ddq[i^len]%mo; if(n&1)for(int i=0,w=1;i<2*len;i++,w=1ll*w*wm%mo)t[i]=1ll*t[i]*w%mo; for(int i=0;i<len;i++)t[i]=1ll*v*inc(t[i],t[i+len])%mo,dp[i]=t[i]; ntt(t,len,-1);for(int i=0;i<len;i++)p[i]=t[i]; //q dq for(int i=0;i<2*len;i++)t[i]=1ll*ddq[i]*ddq[i^len]%mo; for(int i=0;i<len;i++)t[i]=1ll*v*inc(t[i],t[i+len])%mo,dq[i]=t[i]; ntt(t,len,-1);for(int i=0;i<len;i++)q[i]=t[i]; n>>=1; } return 1ll*p[0]*inv(q[0])%mo; } int recurrence(int *f,int *g,int n,int k) { int len=1; while(len<(n+1))len<<=1; for(int i=0;i<len;i++)p[i]=q[i]=0; q[0]=1;for(int i=1;i<=n;i++)q[i]=dec(0,g[i]); for(int i=0;i<n;i++)a[i]=f[i]; b[0]=0;for(int i=1;i<=n;i++)b[i]=g[i]; poly_mul(len,len); for(int i=0;i<n;i++)p[i]=dec(f[i],a[i]); return coefficient(k,len); }