好好玩
即对于k∈[1,t] 求(ax+by)^k
以下图片均来自于：
一
二项式展开：
设：
那么：
可以卷积了
二
求：
（PS：随机序列的0~k次方和，这是一个经典问题。）
我的思路：O(nk)暴力
神仙思路：求一个毫不沾边的东西，然后写两次，对应上系数。O(nlog^2n)
不妨考虑求A(x)：
先求一个看起来毫不沾边的东西：
这个G成为了写两次的东西
解决问题的中轴和杠杆
利用
分治NTT+求Ln
现在已经写了一次
写第二次：
对于单独一项，采用Taylor展开，往多项式方向靠近
合起来：
交换顺序：
哇！
写第二次，
用Taylor展开+交换求和号
对应系数直接相等
神仙神仙~！~~~！！~！
Code
多项式全家桶
const int N=1e5+5;int n,m,K;int a[N],b[N];int A[N],B[N];int c[N];int jie[N],inv[N];il Poly divi(int l,int r){ if(l==r){ Poly g;g.resize(2);g[0]=1;g[1]=c[l];return g; } int mid=(l+r)>>1; Poly L=divi(l,mid),R=divi(mid+1,r); return L*R;}void wrk(int *a,int *A,int n){ for(reg i=1;i<=n;++i) c[i]=a[i]; Poly G=divi(1,n); // G.out(); G.resize(K+4); G=Ln(G); G.resize(K+1); // G.out(); for(reg k=1;k<=K;++k){ if((k+1)&1){ A[k]=mod-mul(G[k],k); }else{ A[k]=mul(G[k],k); } }}int main(){ rd(n);rd(m); for(reg i=1;i<=n;++i){ rd(a[i]); } for(reg i=1;i<=m;++i){ rd(b[i]); } rd(K); wrk(a,A,n); wrk(b,B,m); A[0]=n; B[0]=m; // prt(A,0,K); // prt(B,0,K); Poly f,g; f.resize(K+1);g.resize(K+1); jie[0]=1; for(reg i=1;i<=K;++i) jie[i]=(ll)jie[i-1]*i%mod; inv[K]=qm(jie[K],mod-2); for(reg i=K-1;i>=0;--i) inv[i]=mul(inv[i+1],i+1); for(reg i=0;i<=K;++i){ f[i]=mul(A[i],inv[i]); g[i]=mul(B[i],inv[i]); } f=f*g; for(reg i=1;i<=K;++i){ ll ans=mul(jie[i],f[i]); ans=mul(ans,qm(mul(n,m),mod-2)); printf("%lld\n",ans); } return 0;}
