#include<bits/stdc++.h>
using namespace std;
const int N=(1<<22)+20;
const int mod=998244353;
typedef vector<int> vec;
typedef unsigned long long ull;
namespace Math{
inline int add(int x,int y){return (x+y>=mod)?x+y-mod:x+y;}
inline int dec(int x,int y){return (x-y<0)?x-y+mod:x-y;}
inline void inc(int &x,int y){x=add(x,y);}
inline void rec(int &x,int y){x=dec(x,y);}
inline int ksm(int x,int y){
int ret=1;
for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) ret=1ll*ret*x%mod;
return ret;
}
int iv[N],tp;
inline void init_inv(int n){
if(!tp){iv[0]=iv[1]=1;tp=2;}
for(;tp<=n;++tp) iv[tp]=1ll*(mod-mod/tp)*iv[mod%tp]%mod;
}
}
using namespace Math;
int Wn[N<<1],lg[N],r[N],tot;
inline void init_poly(int n){
int p=1;while(p<=n)p<<=1;
for(int i=2;i<=p;++i) lg[i]=lg[i>>1]+1;
for(int i=1;i<p;i<<=1){
int wn=ksm(3,(mod-1)/(i<<1));
Wn[++tot]=1;
for(int j=1;j<i;++j) ++tot,Wn[tot]=1ll*Wn[tot-1]*wn%mod;
}
}
inline void init_pos(int lim){
int len=lg[lim]-1;
for(int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<len);
}
ull fr[N];
const ull Mod=998244353;
inline void NTT(int *f,int lim,int tp){
for(int i=0;i<lim;++i) fr[i]=f[r[i]];
for(int mid=1;mid<lim;mid<<=1){
for(int len=mid<<1,l=0;l+len-1<lim;l+=len){
for(int k=l;k<l+mid;++k){
ull w1=fr[k],w2=fr[k+mid]*Wn[mid+k-l]%Mod;
fr[k]=w1+w2;fr[k+mid]=w1+Mod-w2;
}
}
}
for(int i=0;i<lim;++i) f[i]=fr[i]%Mod;
if(!tp){
reverse(f+1,f+lim);
int iv=ksm(lim,mod-2);
for(int i=0;i<lim;++i) f[i]=1ll*f[i]*iv%mod;
}
}
int f[N],g[N];
void poly_multiply(unsigned *a,int n,unsigned *b,int m,unsigned *c){
n++;m++;init_poly(n+m);
int rec=n+m-1;
int len=lg[rec],lim=1<<len+1;
init_pos(lim);
for(int i=0;i<n;++i) f[i]=a[i];
for(int i=0;i<m;++i) g[i]=b[i];
NTT(f,lim,1);NTT(g,lim,1);
for(int i=0;i<lim;++i) f[i]=1ll*f[i]*g[i]%mod;
NTT(f,lim,0);
for(int i=0;i<rec;++i) c[i]=f[i];
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 234.03 ms | 63 MB + 704 KB | Accepted | Score: 100 | 显示更多 |