题解 P4721 【【模板】分治 FFT】

Great_Influence

2018-07-04 15:45:36

Solution

都是求逆啊。。虽然可以理解。 分治$FFT$可以解决题目所描述的问题。 发现题目的要求类似于卷积,于是考虑使用$FFT$。 但是后面的数字基于前面的数字,无法快速计算,时间复杂度退化至$O(n^2)$。 于是我们考虑将类似的转移同时进行,来节省复杂度。 考虑利用分治。 假设我们求出了$l\to mid$的答案,要求这些点对$mid+1\to r$的影响,那么对右半边点$x$的贡献为: $$w_x=\sum_{i=l}^{mid} f[i] * g[x-i]$$ 这部分可以利用卷积来快速计算。计算完以后,答案直接加到答案数组就可以了。 需要注意的是,如果要求左边点对右边点的影响,首先整个区间以左对该区间的贡献应该先求出。所以分治过程为先分治左边,在求出中间,然后在递归右边。 时间复杂度$O(n\log^2n)$~~(被求逆$O(n\log n)$吊打)~~ 有一个卡常技巧,就是可以发现你计算的时候只会用到 $md-l\sim r-l$ 的这一部分,前半部分不需要管。因此,直接用循环卷积对它进行处理,做乘法的时候不必做长度为 $1.5(r-l+1)$ 的,只需要做长度为 $r-l+1$ 的就可以了。这样常数会到原来的 $0.5\sim 0.67$ 倍(因为 $1.5(r-l+1)$ 的循环卷积通常会直接做长度为 $2(r-l+1) $ 的)。 upd:有人说要完整代码,我就放出来算了。。。 代码: ```cpp #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() { return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++); } static char Out[Output],*nowps=Out; inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;} template<typename T>inline void read(T&x) { 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 int ad(int u,int v){return(u+=v)>=mod?u-mod:u;} 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; *(F+j+k+ii)=ad(*(F+j+k),mod-tt); *(F+j+k)=ad(*(F+j+k),tt); } 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; using poly::ad; 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); Rep(i,md+1,r)F[i]=ad(F[i],A[i-l]); cdq_FFT(F,G,md+1,r); } int main() { file(); predone(); read(n); rep(i,1,n)read(G[i]); cdq_FFT(F,G,0,n-1); rep(i,0,n)write(F[i],' '); flush(); return 0; } ```