NTT+分治FFT--P4091 [HEOI2016/TJOI2016]求和

本文主要是介绍NTT+分治FFT--P4091 [HEOI2016/TJOI2016]求和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

这道题很妙啊

首先看题目中的式子，令新的$f(n)={\sum }_{i=0}^{n}S(n,i)\times 2^i\times (i!)$，如果能快速求出这个式子的值，那么$ans={\sum }_{i=0}^{n}f(i)$

首先设$g(n)={\sum }_{i=0}^{n}S(n,i)\times i!$，考虑组合意义，第二类$striling$数是$n$个不同小球放入$m$个相同盒子，那么$g(n)$就代表把$n$个小球放入任意多$(\le n)$的不同盒子的方案数。
也就可以转化成 $g(n)={\sum }_{i=0}^{n}C(n,i)\times g(i)$

考虑原式：$f(n)={\sum }_{i=0}^{n}C(n,i)\times g(i)\times 2^i$
其实就相当于给每个盒子黑白染色

也可以转化成：$f(n)={\sum }_{i=0}^{n-1}C(n,i)\times f(i)$

把组合数展开，发现式子可以化简为：$\frac{f(n)}{n!}={\sum }_{i=0}^{n-1}\frac{2}{(n-i)!}\times \frac{f(i)}{i!}$

到这步就可以看到右边的两部分下标和为$i$，就可以分治$FFT$来求出$f$，最后求答案的时候只需要$\times i!$
因为题目要取模，模数刚好是$998244353$，原根为$3$，直接$NTT$即可

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 400005
#define LL long long
using namespace std;
int n,limit=1,lim,rev[maxn];
LL a[maxn],b[maxn],f[maxn],fac[maxn],inv[maxn],ans;
const int mod=998244353,g=3;inline LL qpow(LL x,int k){LL ret=1;while(k){if(k&1) (ret*=x)%=mod;(x*=x)%=mod; k>>=1;} return ret%mod;
}inline void NTT(LL *F,int type){for(int i=0;i<limit;i++)if(i<rev[i]) swap(F[i],F[rev[i]]);for(int mid=1;mid<limit;mid<<=1){LL Wn=qpow(g,type==1?(mod-1)/(mid<<1):(mod-1-(mod-1)/(mid<<1)));for(int r=mid<<1,j=0;j<limit;j+=r){LL w=1;for(int k=0;k<mid;k++,(w*=Wn)%=mod){LL x=F[j+k],y=F[j+mid+k]*w%mod;F[j+k]=(x+y)%mod,F[j+mid+k]=(x-y+mod)%mod;}}}if(type==-1){LL INV=qpow(limit,mod-2);for(int i=0;i<limit;i++) F[i]=(F[i]*INV)%mod;}
}inline void work(){NTT(a,1); NTT(b,1);for(int i=0;i<limit;i++) a[i]=a[i]*b[i]%mod;NTT(a,-1);
}inline void cdqFFT(int l,int r){if(l==r) return;int mid=(l+r)>>1,len=r-l-1;cdqFFT(l,mid);limit=1,lim=0;while(limit<=len) limit<<=1,++lim;for(int i=0;i<limit;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(lim-1)),a[i]=b[i]=0;//清零 for(int i=l;i<=mid;i++) a[i-l]=f[i];for(int i=1;i<=r-l;i++) b[i-1]=2LL*inv[i]%mod;work();for(int i=mid+1;i<=r;i++) f[i]=(f[i]+a[i-l-1]%mod)%mod;cdqFFT(mid+1,r);
}int main(){scanf("%d",&n); fac[1]=fac[0]=1; f[0]=1;for(int i=2;i<=n;i++) fac[i]=1LL*fac[i-1]*i%mod;inv[n]=qpow(fac[n],mod-2);for(int i=n;i>1;i--) inv[i-1]=1LL*inv[i]*i%mod;cdqFFT(0,n);for(int i=0;i<=n;i++) (ans+=f[i]*fac[i]%mod)%=mod;printf("%lld\n",ans);return 0;
}

这篇关于NTT+分治FFT--P4091 [HEOI2016/TJOI2016]求和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---