2019.01.04 洛谷 P4721 【模板】分治 FFT-白红宇

2019.01.04 洛谷 P4721 【模板】分治 FFT

阅读量：4553 次

发布时间：2019-06-08

本文共 1565 字，大约阅读时间需要 5 分钟。

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

题意简述：给你一个数组

g_{1,2,...n}

并定义

f0=1,fi=∑j=1ifi−jgjf_0=1,f_i=\sum_{j=1}^if_{i-j}g_j

，让你求

f_{0,1,...,n}

代码：

#include
    
     #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
     
      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
      
       >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
       
        &a,const int&type){
        for(ri i=0;i
        
         
          >=1){ wn=ksm(typ,mult); for(ri j=0,len=mid<<1;j

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

转载于:https://www.cnblogs.com/ldxcaicai/p/10367783.html

你可能感兴趣的文章