NTT 플레이트

그나저나 NTT가 보통 빠르진 않네...그리고 도대체 그 모로 하는거야...UOJ 모드에 문제가 생기지 않을까...됐어, UOJ 모델로 하자...코드:

#include
#include
#include
#include
#include
#include
#define ll long long
#define max(a,b) a>b?a:b
#define min(a,b) a
using namespace std;
inline int read(){
    int x=0,f=1;char ch=' ';
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
const int N=3e6,p=998244353,g=3,gi=332748118;
int n,m,L,R[N];
ll inv,wn[20],A[N],B[N];
inline ll ksm(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1)ans=ans*a%p;
        a=a*a%p;
        n>>=1;
    }
    return ans;
}
inline void NTT(ll *a,int f){
    for(int i=0;iif(ifor(int i=1;i1){
        ll wn=ksm((f==1)?g:gi,(p-1)/(i<<1));
        for(int j=0;j1)){
            ll w=1;
            for(int k=0;kif(!~f)for(int i=0;iint main(){
    for(int i=0;i<20;++i)wn[i]=ksm(g,(p-1)/(1<scanf("%d %d",&n,&m);
    for(int i=0;i<=n;++i)A[i]=read(),A[i]=(A[i]+p)%p;
    for(int i=0;i<=m;++i)B[i]=read(),B[i]=(B[i]+p)%p;
    m+=n;
    for(n=1;n<=m;n<<=1)++L;
    inv=ksm(n,p-2);
    for(int i=0;i>1]>>1)|((i&1)<1));
    NTT(A,1);NTT(B,1);
    for(int i=0;i1);
    for(int i=0;i<=m;++i)printf("%d ",A[i]);
    return 0;
}