#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
typedef long long ll;
typedef unsigned un;
ll read()
{
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
using std::min;
using std::max;
template<typename T>bool umin(T& a,T t){if(a>t)return a=t,1;return 0;}
template<typename T>bool umax(T& a,T t){if(a<t)return a=t,1;return 0;}
ll abs(ll x){return x>0?x:-x;}
const int MAXN = 2097211,mod=998244353;
ll Qpow(ll a,ll p)
{
ll res=1;
while(p){if(p&1)res=res*a%mod;a=a*a%mod,p>>=1;}
return res;
}
inline int S(int x){return x<mod?x:x-mod;}
inline int D(int x){return x<0?x+mod:x;}
ll RT[MAXN];
int f[MAXN],g[MAXN];
int init(int n)
{
int len=1;
while(len<=n)len<<=1;
for(int i=1;i<len;i<<=1)
{
ll R(Qpow(3,(mod-1)/(i<<1)));
RT[i]=1;
for(int j=1;j<i;++j)RT[i+j]=RT[i+j-1]*R%mod;
}
return len;
}
int status[MAXN];
void DFT(int* a,int len)
{
for(int i=0;i<len;++i)
if(status[i]>i)std::swap(a[i],a[status[i]]);
for(int cur=1;cur<4&&cur<len;cur<<=1)
for(int j=0;j<len;j+=cur<<1)
for(int k=0;k<cur;++k)
{
int x=a[j+k],y=a[j+cur+k]*RT[cur+k]%mod;
a[j+k]=S(x+y),a[j+cur+k]=D(x-y);
}
for(int cur=4;cur<len;cur<<=1)
for(int j=0;j<len;j+=cur<<1)
for(int k=0;k<cur;k+=4)
{
int y=a[j+cur+k]*RT[cur+k]%mod;
a[j+cur+k]=D(a[j+k]-y),a[j+k]=S(a[j+k]+y);
y=a[j+cur+k+1]*RT[cur+k+1]%mod;
a[j+cur+k+1]=D(a[j+k+1]-y),a[j+k+1]=S(a[j+k+1]+y);
y=a[j+cur+k+2]*RT[cur+k+2]%mod;
a[j+cur+k+2]=D(a[j+k+2]-y),a[j+k+2]=S(a[j+k+2]+y);
y=a[j+cur+k+3]*RT[cur+k+3]%mod;
a[j+cur+k+3]=D(a[j+k+3]-y),a[j+k+3]=S(a[j+k+3]+y);
}
}
void IDFT(int* a,int len)
{
std::reverse(a+1,a+len);
DFT(a,len);
ll inv=Qpow(len,mod-2);
for(int i=0;i<len;++i)a[i]=a[i]*inv%mod;
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
int len=init(n+m);
for(int i=0;i<=n;++i)f[i]=a[i];
for(int i=0;i<=m;++i)g[i]=b[i];
for(int i=0;i<len;++i)
status[i]=(status[i>>1]>>1)|((i&1)?len>>1:0);
DFT(f,len),DFT(g,len);
for(int i=0;i<len;++i)f[i]=ll(f[i])*g[i]%mod;
IDFT(f,len);
for(int i=0;i<=n+m;++i)c[i]=f[i];
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 256.27 ms | 47 MB + 680 KB | Accepted | Score: 100 | 显示更多 |