首页 > 代码库 > BZOJ4555: [Tjoi2016&Heoi2016]求和
BZOJ4555: [Tjoi2016&Heoi2016]求和
题意:求给定n,求这个式子%一个NTT模数的值。 $ f(n) = \sum\limits_{i = 0}^n {\sum\limits_{j = 0}^i {s(i,j)*{2^j}*j!} } $ 其中S(i,j)为第二类斯特林数。
题解:首先根据第二类斯特林数的定义,我们可以把第二个sigma上界变成n(这里很关键,就是因为这个没看出来导致没推出卷积形式。。)
根据第二类斯特林数的公式,式子可以写成
$ \begin{array}{l}f(n) = \sum\limits_{i = 0}^n {\sum\limits_{j = 0}^n {\sum\limits_{k = 0}^j {{{( - 1)}^k}*\frac{{{{(j - k)}^i}}}{{k!(j - k)!}}} {2^j}*j!} } \\\end{array} $
再把i的sigma丢到后面去 $ \begin{array}{l}f(n) = \sum\limits_{j = 0}^n {\sum\limits_{k = 0}^j {{{( - 1)}^k}*\frac{{\sum\limits_{i = 0}^{\rm{n}} {{{(j - k)}^i}} }}{{k!(j - k)!}}} {2^j}*j!} \\\end{array} $
或者写成这样更显然一点 $ \begin{array}{*{20}{l}}{f(n) = \sum\limits_{j = 0}^n {{2^j}*j!\sum\limits_{k = 0}^j {\frac{{{{( - 1)}^k}}}{{{\rm{k!}}}}*\frac{{\sum\limits_{i = 0}^{\rm{n}} {{{(j - k)}^i}} }}{{(j - k)!}}} } }\end{array} $
这个式子就是个卷积,直接NTT咯。
这道题有些坑点,首先对于卷积那一部分里我们要弄一个等比数列求和,这里公比为1的时候要注意一下(还记得等比数列求和公式要分类讨论吗?)
然后还有对于第0项的讨论。这些都要注意。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define mod 998244353 5 #define N 400005 6 #define G 3 7 8 inline LL read(){ 9 int x=0,f=1; char a=getchar(); 10 while(a<‘0‘ || a>‘9‘) {if(a==‘-‘) f=-1; a=getchar();} 11 while(a>=‘0‘ && a<=‘9‘) x=x*10+a-‘0‘,a=getchar(); 12 return x*f; 13 } 14 15 int n,fac[N],nfac[N],two[N],a[N],b[N],f[N],ans; 16 17 inline int fpow(int x,int k){ 18 int ret=1; 19 while(k){ 20 if(k&1) ret=1LL*ret*x%mod; 21 k>>=1; x=1LL*x*x%mod; 22 } 23 return ret; 24 } 25 26 namespace NTT{ 27 int rev[N],wn[30]; 28 29 inline void getwn(){for(int i=1,t=2;i<20;i++,t<<=1) wn[i]=fpow(G,(mod-1)/t);} 30 31 inline void ntt(int x[],int len,int f){ 32 for(int i=1;i<=len;i++) if(i<rev[i]) swap(x[i],x[rev[i]]); 33 for(int t=1,lnow=2;lnow<=len;lnow<<=1,t++){ 34 for(int i=0;i<len;i+=lnow){ 35 int w=1; 36 for(int j=i;j<i+lnow/2;j++){ 37 int t1=x[j],t2=1LL*w*x[j+lnow/2]%mod; 38 x[j]=(t1+t2)%mod; 39 x[j+lnow/2]=((t1-t2)%mod+mod)%mod; 40 w=1LL*w*wn[t]%mod; 41 } 42 } 43 } 44 if(f==-1){ 45 for(int i=len/2;i+1;i--) swap(x[i],x[len-i]); 46 int inv=fpow(len,mod-2); 47 for(int i=0;i<=len;i++) a[i]=1LL*a[i]*inv%mod; 48 } 49 } 50 51 inline void work(int a[],int b[],int l1,int l2){ 52 int len,t; 53 for(len=1,t=0;len<=(l1+l2+1);len<<=1,t++); t=1<<(t-1); 54 for(int i=1;i<=len;i++) rev[i]=rev[i>>1]>>1|(i&1?t:0); 55 ntt(a,len,1); ntt(b,len,1); 56 for(int i=0;i<=len;i++) a[i]=1LL*a[i]*b[i]%mod; 57 ntt(a,len,-1); 58 } 59 } 60 61 int main(){ 62 NTT::getwn(); 63 n=read(); 64 fac[0]=1; for(int i=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%mod; 65 nfac[n]=fpow(fac[n],mod-2); for(int i=n-1;i+1;i--) nfac[i]=1LL*nfac[i+1]*(i+1)%mod; 66 two[0]=1; for(int i=1;i<=n;i++) two[i]=1LL*two[i-1]*2%mod; 67 for(int i=0;i<=n;i++) f[i]=1LL*two[i]*fac[i]%mod; 68 for(int i=0;i<=n;i++) a[i]=1LL*(fpow(i,n+1)-1)*fpow(i-1,mod-2)%mod*nfac[i]%mod,a[i]=(a[i]+mod)%mod; 69 a[0]=1; a[1]=n+1; //就是这里 70 for(int i=0;i<=n;i++) b[i]=(1LL*(i&1?-1:1)*nfac[i]%mod+mod)%mod; 71 NTT::work(a,b,n,n); 72 for(int i=0;i<=n;i++) ans=((LL)ans+1LL*f[i]*a[i]%mod)%mod; 73 printf("%d\n",ans+1); //要把s(0,0)加上 74 return 0; 75 }
BZOJ4555: [Tjoi2016&Heoi2016]求和