首页 > 代码库 > 2017 3 11 分治FFT
2017 3 11 分治FFT
考试一道题的递推式为$$f[i]=\sum_{j=1}^{i} j^k \times (i-1)! \times \frac{f[i-j]}{(i-j)!}$$
这显然是一个卷积的形式，但$f$需要由自己卷过来(我也不知到怎么说)，以前只会生成函数的做法，但这题好像做不了(谁教教我怎么做)，于是无奈的写了一发暴力，看题解发现是分治FFT.
分治每层用$f[l]-f[mid]$与$a[1]-a[r-l]$做NTT。
这样显然每个$f[l]-f[mid]$对$f[mid+1]-f[r]$的贡献都考虑到了。
因为分治是从1开始的，所以$f[0]$的转移预处理了。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #define ll long long 6 #define N 400005 7 using namespace std; 8 int n,k; 9 const int p = 998244353;10 ll poow[N],jie[N],ni[N];11 ll pw(ll x,ll y)12 {13 ll lst=1;14 while(y)15 {16 if(y&1)lst=lst*x%p;17 x=x*x%p;18 y>>=1;19 }20 return lst;21 }22 ll f[N];23 int R[N],a[N],b[N];24 void NTT(int *a,int n,int f,int L)25 {26 for(int i=0;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));27 for(int i=0;i<n;i++)if(i<R[i])swap(a[i],a[R[i]]);28 for(int i=1;i<n;i<<=1)29 {30 int wn=pw(3,((p-1)/(i<<1)*f+p-1)%(p-1));31 for(int j=0;j<n;j+=(i<<1))32 {33 int w=1;34 for(int k=0;k<i;k++,w=1LL*w*wn%p)35 {36 int x=a[j+k],y=1LL*a[j+k+i]*w%p;37 a[j+k]=(x+y)%p;a[j+k+i]=(x-y+p)%p;38 }39 }40 }41 if(f==-1)42 {43 int nw=pw(n,p-2);44 for(int i=0;i<n;i++)a[i]=1LL*a[i]*nw%p;45 }46 return ;47 }48 void solve(int l,int r)49 {50 if(l==r)51 {52 f[l]=f[l]*jie[l-1]%p;53 return ;54 }55 int mid=(l+r)>>1;56 solve(l,mid);int len=r-l+1;int m=len<<1;57 for(int i=1;i<len;i++)a[i]=poow[i];58 for(int i=l;i<=mid;i++)b[i-l]=f[i]*ni[i]%p;59 int L=0;for(len=1;len<m;len<<=1)L++;60 for(int i=mid-l+1;i<len;i++)b[i]=0;61 NTT(a,len,1,L);NTT(b,len,1,L);62 for(int i=0;i<len;i++)a[i]=1LL*a[i]*b[i]%p;63 NTT(a,len,-1,L);64 for(int i=mid+1;i<=r;i++)f[i]=(f[i]+a[i-l])%p;65 solve(mid+1,r);66 }67 int main()68 {69 scanf("%d%d",&n,&k);70 jie[0]=1;ni[0]=1;71 for(int i=1;i<=n;i++)jie[i]=(jie[i-1]*i)%p;72 for(int i=1;i<=n;i++)ni[i]=pw(jie[i],p-2);73 poow[0]=1;74 for(int i=1;i<=n;i++)poow[i]=pw(i,k);75 for(int i=1;i<=n;i++)f[i]=poow[i];76 solve(1,n);77 printf("%lld\n",f[n]);78 return 0;79 }
2017 3 11 分治FFT
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。