题意
给定一个\(n\) 次的 \(f\) 函数，向右移动 \(m\) 次得到 \(g\) 函数，第 \(i\) 次移动长度是 \(a_i\) ，求 \(g\) 函数解析式的各项系数，对 \(998244353\) 取模。
\(1 \leq n \leq 10^5\)
\(1\leq \sum m \leq 10^5\)
思路
设 \(\displaystyle S=-\sum_{i=1}^ma_i\)
\[g(x)=f(x+S)\\
g(x)=\sum_{i=0}^nc_i(x+S)^i\\
\]
二项展开后得到
\[g(x)=\sum_{i=0}^nc_i[\sum_{j=0}^i{i\choose j}S^{i-j}\cdot x^j]\\
\]
将 \(\displaystyle\sum_{j}\) 拉出，得到。
\[g(x)=\sum_{j=0}^n\sum_{i=j}^nc_i{i\choose j}S^{i-j}\cdot x^j\\
\]
那么多项式 \(g\) 的第 \(j\) 项 \(b_j\) 就是 \(\displaystyle\sum_{i=j}^nc_i{i\choose j}S^{i-j}\)
将组合数展开
\[b_j=\sum_{i=j}^nc_i S^{i-j}{i!\over j!(i-j)!}
\]
将只与 \(j\) 相关的项提出，合并变量相同的项得到
\[b_j={1\over j!}\sum_{i=j}^nc_ii!\cdot S^{i-j}{1\over (i-j)!}
\]
不难发现，右边有两项仅与 \(i\) 有关，有两项仅与 \(i-j\) 有关。
把式子写成卷积的形式
\[b_j={1\over j!}c_ii!\cdot S^{i-j}{1\over (i-j)!}
\]
用 \(i+j\) 替换 \(j\) 得到
\[b_{i+j}={1\over (i+j)!}c_ii!\cdot S^{-j}{1\over (-j)!}
\]
其中 \(i\in[0,n] ,j\in[-n,0],i+j\in[-n,n]\)
设 \(\displaystyle A_i=c_ii!,B_j=S^{-j}{1\over{(-j)!}}\)
那么就有了最终的表达式 \(\displaystyle b_{i+j}={1\over{i+j}}A_iB_j\)
对 \(A,B\) 两多项式进行卷积，最后乘上 \(\displaystyle {1\over {i+j}}\) 即可。
最后我们需要的只是 \(b\) 在 \([0,n]\) 的结果，多项式相乘一步，可以理解为：一组状态，每一个值都向一些方向转移一些值，用多项式表示就是一个状态多项式、一个转移多项式乘出一个结果多项式。关键是要保证所有状态的转移方向一致。
代码
#include<bits/stdc++.h>
#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)
#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)
typedef long long ll;
using namespace std;
const int P=998244353,g=3;
const int N=1<<17|5;
namespace Maths
{
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b){x=1,y=0;return;}
exgcd(b,a%b,y,x),y-=a/b*x;
}
ll Pow(ll a,ll p,ll P)
{
ll res=1;
for(;p>0;p>>=1,(a*=a)%=P)if(p&1)(res*=a)%=P;
return res;
}
ll inv(ll a,ll P){ll x,y;exgcd(a,P,x,y);return (x%P+P)%P;}
};
using namespace Maths;
namespace _NTT
{
int A[N<<1],B[N<<1];
int r[N<<1];
void NTT(int *a,int p,int n)
{
FOR(i,0,n-1)if(i<r[i])swap(a[i],a[r[i]]);
for(int i=2;i<=n;i<<=1)
{
int wn=Pow(g,(P-1)/i,P);
if(p==-1)wn=inv(wn,P);
for(int j=0;j<n;j+=i)
{
int w=1;
for(int k=0;k<i/2;k++)
{
int u=a[j+k],t=(ll)w*a[j+k+i/2]%P;
a[j+k]=(u+t)%P,a[j+k+i/2]=(u-t)%P;
w=(ll)w*wn%P;
}
}
}
}
void multiply(const int *a,const int *b,int *c,int n1,int n2)
{
int n=1;
while(n<n1+n2-1)n<<=1;
FOR(i,0,n1-1)A[i]=a[i];
FOR(i,0,n2-1)B[i]=b[i];
FOR(i,n1,n-1)A[i]=0;
FOR(i,n2,n-1)B[i]=0;
FOR(i,0,n-1)r[i]=(r[i>>1]>>1)|((i&1)*(n>>1));NTT(A,1,n),NTT(B,1,n);
FOR(i,0,n-1)A[i]=(ll)A[i]*B[i]%P;
NTT(A,-1,n);
int I=inv(n,P);
FOR(i,0,n1+n2-2)c[i]=(ll)A[i]*I%P;
}
};
int A[N],B[N],C[N<<2];
int fac[N],c[N],S;
int n,m;int main()
{
fac[0]=1;FOR(i,1,N-1)fac[i]=(ll)fac[i-1]*i%P;
while(~scanf("%d",&n))
{
FOR(i,0,n)scanf("%d",&c[i]);
scanf("%d",&m);
S=0;
while(m--)
{
int x;
scanf("%d",&x);
S-=x;
if(S<0)S+=P;
}
FOR(i,0,n)A[i]=(ll)c[i]*fac[i]%P;
FOR(i,-n,0)B[i+n]=Pow(S,-i,P)*inv(fac[-i],P)%P;
_NTT::multiply(A,B,C,n+1,n+1);
FOR(i,0,n)printf("%lld ",(C[i+n]*inv(fac[i],P)%P+P)%P);
puts("");
}
return 0;
}
