2019.01.04 洛谷 P4721 【模板】分治 FFT

传送门

如同题目所描述的一样，这是一道板题。

题意简述：给你一个数组g1,2,...ng_{1,2,...n}g1,2,...n并定义f0=1,fi=∑j=1ifi−jgjf_0=1,f_i=\sum_{j=1}^if_{i-j}g_jf0=1,fi=∑j=1ifi−jgj，让你求f0,1,...,nf_{0,1,...,n}f0,1,...,n

解析

代码：

#include<bits/stdc++.h>
#define ri register int
#define add(a,b) ((a)+(b)>=mod?(a)+(b)-mod:(a)+(b))
#define dec(a,b) ((a)>=(b)?(a)-(b):(a)-(b)+mod)
#define mul(a,b) ((ll)(a)*(b)%mod)
using namespace std;
inline int read(){
    int ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
typedef long long ll;
const int N=1e5+5,mod=998244353;
int n,lim,tim;
vector<int>A,B,pos;
inline void init(const int&up){
    lim=1,tim=0;
    while(lim<=up*2)lim<<=1,++tim;
    A.resize(lim),B.resize(lim),pos.resize(lim),pos[0]=0;
    for(ri i=0;i<lim;++i)pos[i]=(pos[i>>1]>>1)|((i&1)<<(tim-1));
}
inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}
inline void ntt(vector<int>&a,const int&type){
    for(ri i=0;i<lim;++i)if(i<pos[i])swap(a[i],a[pos[i]]);
    for(ri mid=1,wn,mult=(mod-1)/2,typ=type==1?3:(mod+1)/3;mid<lim;mid<<=1,mult>>=1){
        wn=ksm(typ,mult);
        for(ri j=0,len=mid<<1;j<lim;j+=len)for(ri w=1,k=0,a0,a1;k<mid;++k,w=mul(w,wn)){
            a0=a[j+k],a1=mul(w,a[j+k+mid]);
            a[j+k]=add(a0,a1),a[j+k+mid]=dec(a0,a1);
        }
    }
    if(type==-1)for(ri i=0,inv=ksm(lim,mod-2);i<lim;++i)a[i]=mul(a[i],inv);
}
struct poly{
    vector<int>a;
    poly(int k=0,int x=0){a.resize(k+1),a[k]=x;}
    inline poly extend(const int&k){poly ret=*this;return ret.a.resize(k+1),ret;}
    inline int deg()const{return a.size()-1;}
    inline int&operator[](const int&k){return a[k];}
    inline const int&operator[](const int&k)const{return a[k];}
};
inline void cdqFFT(poly&a,poly&b,int l,int r){
    if(l==r)return;
    int mid=l+r>>1;
    cdqFFT(a,b,l,mid),init(2*(r-l+1));
    for(ri i=0;i<lim;++i)A[i]=B[i]=0;
    for(ri i=l;i<=mid;++i)A[i-l]=a[i];
    for(ri i=0;i<=r-l;++i)B[i]=b[i];
    ntt(A,1),ntt(B,1);
    for(ri i=0;i<lim;++i)A[i]=mul(A[i],B[i]);
    ntt(A,-1);
    for(ri i=mid+1;i<=r;++i)a[i]=add(a[i],A[i-l]);
    cdqFFT(a,b,mid+1,r);
}
int main(){
    n=read()-1;
	poly a(n),b(n);
	a.extend(n),b.extend(n),a[0]=1;
    for(ri i=1;i<=n;++i)b[i]=read(),a[i]=0;
    cdqFFT(a,b,0,n);
 	for(ri i=0;i<=n;++i)cout<<a[i]<<' ';
    return 0;
}

巴特西

2019.01.04 洛谷 P4721 【模板】分治 FFT

最新文章

热门文章