2018-07-04 15:45:36

$$w_x=\sum_{i=l}^{mid} f[i] * g[x-i]$$

upd:有人说要完整代码，我就放出来算了。。。

#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cassert>
#include<iostream>
#define Rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(register int i=(a);i>=(b);--i)
#define rep(i,a,b) for(register int i=(a);i<(b);++i)
#define pb push_back
#define mx(a,b) (a>b?a:b)
#define mn(a,b) (a<b?a:b)
typedef unsigned long long uint64;
typedef unsigned int uint32;
typedef long long ll;
using namespace std;

namespace IO
{
const uint32 Buffsize=1<<15,Output=1<<24;
static char Ch[Buffsize],*S=Ch,*T=Ch;
inline char getc()
{
}
static char Out[Output],*nowps=Out;

inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;}

{
x=0;static char ch;T f=1;
for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getc())x=x*10+(ch^48);
x*=f;
}

template<typename T>inline void write(T x,char ch='\n')
{
if(!x)*nowps++='0';
if(x<0)*nowps++='-',x=-x;
static uint32 sta[111],tp;
for(tp=0;x;x/=10)sta[++tp]=x%10;
for(;tp;*nowps++=sta[tp--]^48);
*nowps++=ch;
}
}
using namespace IO;

void file()
{
#ifndef ONLINE_JUDGE
FILE*DSD=freopen("water.in","r",stdin);
FILE*CSC=freopen("water.out","w",stdout);
#endif
}

const int MAXN=1<<19;

namespace poly
{
const int mod=998244353,gen=3;

static int g[23][MAXN],iv[MAXN];

inline int power(int u,int v)
{
register int sm=1;
for(;v;v>>=1,u=(uint64)u*u%mod)if(v&1)
sm=(uint64)sm*u%mod;
return sm;
}

inline void predone()
{
Rep(i,1,18)
{
g[i][0]=1,g[i][1]=power(gen,(mod-1)>>i);
Rep(j,2,2e5)g[i][j]=(ll)g[i][j-1]*g[i][1]%mod;
}
}

static int Len,rev[MAXN];

inline void calrev()
{
int II=log(Len)/log(2)-1;
Rep(i,1,Len-1)rev[i]=rev[i>>1]>>1|(i&1)<<II;
}

inline void NTT(int*F,int typ)
{
Rep(i,1,Len-1)if(i<rev[i])swap(F[i],F[rev[i]]);
for(register int i=2,ii=1,t=1;i<=Len;i<<=1,ii<<=1,++t)
for(register int j=0;j<Len;j+=i)rep(k,0,ii)
{
register int tt=(uint64)*(F+j+k+ii)*g[t][k]%mod;
}
if(typ==-1)
{
reverse(F+1,F+Len);
register uint64 invn=power(Len,mod-2);
rep(i,0,Len)*(F+i)=invn**(F+i)%mod;
}
}
}
using poly::power;
using poly::Len;
using poly::calrev;
using poly::NTT;
using poly::mod;
using poly::predone;

static int n,F[MAXN],G[MAXN],A[MAXN],B[MAXN];

void cdq_FFT(int*F,int*G,int l,int r)
{
if(l==r)
{
if(!l)F[l]=1;
return;
}
int md=(l+r)>>1;
cdq_FFT(F,G,l,md);
memcpy(A,F+l,sizeof(int)*(md-l+1));
memcpy(B,G,sizeof(int)*(r-l+1));
for(Len=2;Len<=r-l+1;Len<<=1);
calrev();
memset(A+md-l+1,0,sizeof(int)*(Len-(md-l)));
memset(B+r-l+1,0,sizeof(int)*(Len-(r-l)));
NTT(A,1),NTT(B,1);
rep(i,0,Len)A[i]=(ll)A[i]*B[i]%mod;
NTT(A,-1);
cdq_FFT(F,G,md+1,r);
}

int main()
{
file();
predone();
}