#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=(0);i<(n);i++)
using namespace std;
typedef vector<int> poly;
typedef unsigned long long ll;
inline int read(){
char ch=getchar();int x=0,op=0;
while(!isdigit(ch))op|=(ch=='-'),ch=getchar();
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return op?-x:x;
}
const int mod=998244353;
namespace Poly{
const int N=(1<<20)+5,g=3;
inline int power(int x,int p){
int res=1;
for(;p;p>>=1,x=(ll)x*x%mod)
if(p&1)res=(ll)res*x%mod;
return res;
}
void dft(poly &A,int n){
static ll W[N<<1],*H[30],*las=W,mx=0;
for(;mx<n;mx++){
H[mx]=las;ll w=1,wn=power(g,(mod-1)>>(mx+1));
REP(i,1<<mx)*las++=w,w=w*wn%mod;
}
static ll a[N];A.resize(1<<n);
for(int i=0,j=0;i<(1<<n);++i){
a[i]=A[j];
for(int k=1<<(n-1);(j^=k)<k;k>>=1);
}
for(int k=0,d=1;k<n;k++,d<<=1)
for(int i=0;i<(1<<n);i+=d<<1){
ll *l=a+i,*r=a+i+d,*w=H[k],t;
for(int j=0;j<d;++j,++l,++r){
t=(*w++)*(*r)%mod;
*r=*l+mod-t,*l+=t;
}
}
REP(i,1<<n)A[i]=a[i]%mod;
}
void idft(poly &a,int n){
a.resize(1<<n);
reverse(a.begin()+1,a.end());
dft(a,n);
int inv=power(1<<n,mod-2);
REP(i,1<<n)a[i]=(ll)a[i]*inv%mod;
}
poly mul(poly a,poly b){
int aim=(a.size()+b.size()),n=1;
while((1<<n)<=aim)n++;
dft(a,n),dft(b,n);
REP(i,1<<n)a[i]=(ll)a[i]*b[i]%mod;
return idft(a,n),a.resize(aim),a;
}
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c){
n++,m++;
poly A(n,0),B(m,0);
REP(i,n) A[i]=a[i];
REP(i,m) B[i]=b[i];
poly C=Poly::mul(A,B);
REP(i,n+m-1) c[i]=C[i];
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 51.177 ms | 47 MB + 300 KB | Runtime Error | Score: 0 | 显示更多 |