代码

#include <bits/stdc++.h>
using namespace std;
#define clr(a) memset(a, 0, sizeof(a))
#define full(a) memset(a, 0x3f, sizeof(a))
#define mset(a, b) memset(a, b, sizeof(a))
#define cpy(a,b) memcpy(a, b, sizeof(a))
#define fornext(x, i) for(int i = hd[x], y = ver[i]; i; i = nxt[i], y = ver[i])
#define Rep(i, a, b) for(int i = (int)(a); i <= (int)(b); ++i)
#define dRep(i, a, b) for(int i = (int)(a); i >= (int)(b); --i)
#define IOset(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout);
#define pb push_back
#define It iterator
#define endl '\n'
#define un unsigned
#define ll long long
#define db double
#define rept cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
#define dbg cout<<"c "
#define dbug(x) cerr << #x " = " << (x) << endl
template<typename _T> inline void _prt(_T _d) { cerr << _d << ' '; }
template <typename _T, typename ...Args> inline void _prt(_T _d, Args ..._a) { _prt(_d), _prt(_a...); }
template <typename _T, typename ...Args> inline void prt(_T _d, Args ..._a) { _prt(_d), _prt(_a...), cerr<<endl; }
template <typename _T, typename ...Args> inline void prt(_T _d) { cerr << _d <<endl; }
template <typename _T, typename ...Args> inline void cbg(_T _d, Args ..._a) { cerr << "--LINE " << __LINE__ << "--: "; prt(_d, _a...); }
template<typename _T> inline void rd(_T &_d) {
    signed _f; char _c; _f = _d = 0; while (_c = getchar(), !isdigit(_c)) _f = _f || (_c == '-');
    while (isdigit(_c)) _d = _d * 10 + _c - '0', _c = getchar();
    _d = (_f ? -_d : _d);
}
template <typename _T, typename ...Args> inline void rd(_T &_d, Args &..._a) { rd(_d); rd(_a...); }

const int N=4e5+5,g=3,M=998244353;
int n,m,a[N],b[N],tr[N];

inline int qpow(int a, int b) {
    int ans = 1;
    for (; b; b >>= 1, a = 1LL*a * a % M) if (b & 1) ans = 1LL*ans * a % M;
    return ans;
}
const int ig=qpow(3,M-2);

inline int md(int x) { return x >= M ? x - M : x; }

void ntt(int *f,bool flg) {
    Rep(i,0,n-1) if(i<tr[i]) swap(f[i],f[tr[i]]);
    int G,bs,tmp,len;
    for(int l=2;l<=n;l<<=1) {
        G=qpow(flg?ig:g,(M-1)/l);
        len=l>>1;
        for(int p=0;p<n;p+=l) {
            bs=1;
            Rep(k,p,p+len-1) {
                tmp=1LL*f[k+len]*bs%M;
                f[k+len]=md(f[k]-tmp+M);
                f[k]=md(f[k]+tmp);
                bs=1LL*bs*G%M;
            }
        }
    }
}
signed main() {
    rd(n, m);
    Rep(i, 0, n) rd(a[i]);
    Rep(i, 0, m) rd(b[i]);  
    int r=n+m,len=0;
    n=1; while(n<=r) n<<=1,++len;
    Rep(i,1,n-1) tr[i]=(tr[i>>1]>>1)|((i&1)<<(len-1));
    ntt(a,0),ntt(b,0);
    Rep(i,0,n-1) a[i]=1LL*a[i]*b[i]%M;
    ntt(a,1);
    int inv=qpow(n,M-2);
    Rep(i,0,r) printf("%d ", (int)(1LL*a[i]*inv%M)); 
    return 0;   
}

评测结果