C++ 解法, 执行用时: 546ms, 内存消耗: 3120K, 提交时间: 2021-12-23 20:50:24

#include<iostream>
#include<cstdio>
#include<algorithm>
#define FF FOF(i,0,L)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FOF(i,a,b) for(int i=a;i< b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define CON(a,b) DFT(a,L);FF a[i]=1ll*a[i]*b[i]%P;IFT(a,L);
using namespace std;
const int N=150150,P=998244353;
int n,m,K,L,o,A,Q;
int rv[N],W[N],p[N],f[N],t[N],a[N],b[N];
void ipt(int&x){scanf("%d",&x);x%=P;x+=x>>31&P;}
int qpw(int x,int y){int z=1;for(;y;y>>=1,x=1ll*x*x%P)if(y&1) z=1ll*z*x%P;return z;}
void ini(int n){
	for(L=1;L<=n;L<<=1,o++);
	FF rv[i]=rv[i>>1]>>1|(i&1)<<(o-1);
	int V=qpw(3,P>>o);W[L>>1]=1;
	FOF(i,(L>>1)+1,L) W[i]=1ll*W[i-1]*V%P;
	ROF(i,(L>>1)-1,1) W[i]=W[i<<1];
}
void DFT(int*A,int L){
	static unsigned long long B[N];
	int u=o-__builtin_ctz(L),t;
	FF B[i]=A[rv[i]>>u];
	for(int i=1;i<L;i<<=1)for(int j=0,s=i<<1;j<L;j+=s)FOF(k,0,i)
		t=B[i+j+k]*W[i+k]%P,B[i+j+k]=B[j+k]+P-t,B[j+k]+=t;
	FF A[i]=B[i]%P;
}
void IFT(int*A,int L){
	reverse(A+1,A+L);DFT(A,L);
	int V=P-(P-1)/L;
	FF A[i]=1ll*A[i]*V%P;
}
int upl(int n){return 1<<(32-__builtin_clz(n));}
void INV(int*A,int*B,int n){
	static int C[N],L;
	if(!n) return B[0]=qpw(A[0],P-2),void();
	INV(A,B,n>>1);L=upl(n<<1);
	FF C[i]=i>n?0:A[i];
	DFT(C,L);DFT(B,L);
	FF B[i]=(2-1ll*C[i]*B[i]%P+P)*B[i]%P;IFT(B,L);
	FF B[i]=i>n?0:B[i],C[i]=0;
}
void MUL(int*A,int*B){
	static int C[N];
	FF C[i]=A[i];DFT(C,L);
	CON(B,C);
	FF C[i]=i>K?0:B[n-i];
	CON(C,t);
	FF C[i]=i>K?0:C[i];
	reverse(C,C+K+1);
	CON(C,p);
	FF (B[i]+=P-C[i])%=P;
}
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
typedef long long ll;
ll power(ll x,ll y){
    ll res = 1;
    while(y){
        if(y&1) res = 1ll*res*x%P;
        x = x*x%P;
        y >>= 1;
    }
    return res;
}
int main(){
	scanf("%d%d",&Q,&m);
	ini(m<<1);n=m-1<<1;K=n-m;
    int x;
	FOR(i,1,m){
		x = read();
        x = 1ll*x*(x+1)%P*(2*x+1)%P*power(6, P-2)%P;
        p[i] = 1ll*(x+1)*(x+1)%P+x+1;
        p[i] %= P;
	} 
	FOF(i,0,m){
		f[i] = read();
	} 
	p[0]=P-1;
	INV(p,t,K);DFT(t,L);
	reverse(p,p+m+1);DFT(p,L);
	a[1]=b[0]=1;
	for(;Q;Q>>=1,MUL(a,a))if(Q&1) MUL(a,b);
	FOF(i,0,m) (A+=1ll*b[i]*f[i]%P)%=P;
	cout<<A<<'\n';
}