C++(clang++11) 解法, 执行用时: 592ms, 内存消耗: 504K, 提交时间: 2021-05-14 23:26:11

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2005,mod=998244353,G=3,Gi=332748118;
int n,m,k,rev[N<<2],a[N<<2],b[N<<2],c[N<<2];
ll qpow(ll a,ll n)
{
    ll ans=1;
    while(n)
    {
        if(n&1) ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
void NTT(int *f,int n,int opt)
{
    for(int i=0;i<n;i++)
        if(i<rev[i]) swap(f[i],f[rev[i]]);
    for(int l=2,k=1;l<=n;l<<=1,k<<=1)
    {
        ll w=qpow(opt==1?G:Gi,(mod-1)/l);
        for(int i=0;i<n;i+=l)
        {
            ll wi=1;
            for(int j=0;j<k;j++,wi=wi*w%mod)
            {
                ll b=wi*f[i+j+k]%mod;
                f[i+j+k]=(f[i+j]-b+mod)%mod;
                f[i+j]=(f[i+j]+b)%mod;
            }
        }
    }
}
int len=1,bit=0;
ll invlen;
int main()
{
    //freopen("1.in","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i-1]),a[i-1]=1ll*i*a[i-1]%mod;
    for(int i=1;i<=m;i++) scanf("%d",&b[i]);
    int ans=0;
    while(len<=n-1+k) len<<=1,bit++;
    for(int i=0;i<len;i++)
        rev[i]=(rev[i>>1]>>1)|((i&1)<<bit-1);
    invlen=qpow(len,mod-2);
    NTT(a,len,1);
    for(int t=1;t<=k;t++)
    {
        for(int i=0;i<=k;i++) c[i]=b[i];
        for(int i=k+1;i<len;i++) c[i]=0;
        NTT(c,len,1);
        for(int i=0;i<len;i++) c[i]=(ll)c[i]*a[i]%mod;
        NTT(c,len,mod-1);
        for(int i=0;i<=k;i++) c[i]=c[i]*invlen%mod;
        for(int i=0;i<=k;i++)
            b[i]=(1ll*b[i+1]*(i+1)+c[i])%mod;
        ans=(ans+b[0])%mod;
    }
    printf("%d\n",ans);
}