4555: [Tjoi2016&Heoi2016]求和

Time Limit:?40 Sec??Memory Limit:?128 MB
Submit:?315??Solved:?252

Description

在2016年，佳媛姐姐剛剛學習了第二類斯特林數，非常開心。

現在他想計算這樣一個函數的值: S(i, j)表示第二類斯特林數，遞推公式為: S(i, j) = j ? S(i ? 1, j) + S(i ? 1, j ? 1), 1 <= j <= i ? 1。 邊界條件為：S(i, i) = 1(0 <= i), S(i, 0) = 0(1 <= i) 你能幫幫他嗎?

Input

輸入只有一個正整數

Output

?輸出f(n)。由于結果會很大，輸出f(n)對998244353(7 × 17 × 223 + 1)取模的結果即可。1 ≤ n ≤ 100000

Sample Input

3

Sample Output

87

HINT

Source

?

?

【分析】

　　額。。要用第二類斯特林數的展開式？

　　表示并不會。于是看題解。ORZ。。ATP大神

　　

　　帶進去，注意不用管j從1到i，因為j從1到n的話后面都是0，沒有關系的。

　　最后化成

　　

　　一臉卷積么？個人認為還不是很能看出來。

　　但是，就是！

　　

　　h用NTT求，然后求和即可。

　　再次ORZ。。

?

1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 #define Maxn 500010 8 #define LL long long 9 const int Mod=998244353; 10 const int G=3; 11 12 int a[Maxn],b[Maxn],fac[Maxn]; 13 14 int qpow(int x,int b) 15 { 16 int ans=1; 17 while(b) 18 { 19 if(b&1) ans=1LL*ans*x%Mod; 20 x=1LL*x*x%Mod; 21 b>>=1; 22 } 23 return ans; 24 } 25 26 int nn,R[Maxn],inv; 27 void ntt(int *s,int f) 28 { 29 for(int i=0;i<nn;i++) if(i<R[i]) swap(s[i],s[R[i]]); 30 for(int i=1;i<nn;i<<=1) 31 { 32 int wn=qpow(G,(Mod-1)/(i<<1)); 33 for(int j=0;j<nn;j+=(i<<1)) 34 { 35 int w=1; 36 for(int k=0;k<i;k++) 37 { 38 int x=s[j+k],y=1LL*w*s[j+k+i]%Mod; 39 s[j+k]=(x+y)%Mod;s[j+k+i]=((x-y)%Mod+Mod)%Mod; 40 w=1LL*w*wn%Mod; 41 } 42 } 43 } 44 if(f==-1) 45 { 46 reverse(s+1,s+nn); 47 for(int i=0;i<=nn;i++) s[i]=1LL*s[i]*inv%Mod; 48 } 49 } 50 51 int main() 52 { 53 int n; 54 scanf("%d",&n); 55 fac[0]=1;for(int i=1;i<=n;i++) fac[i]=1LL*i*fac[i-1]%Mod; 56 for(int i=0;i<=n;i++) 57 { 58 a[i]=qpow(fac[i],Mod-2); 59 if(i&1) a[i]=Mod-a[i]; 60 b[i]=(1-qpow(i,n+1))%Mod; 61 b[i]=1LL*b[i]*qpow(1-i,Mod-2)%Mod; 62 b[i]=1LL*b[i]*qpow(fac[i],Mod-2)%Mod; 63 b[i]=(b[i]%Mod+Mod)%Mod; 64 } 65 nn=1;int ll=0; 66 while(nn<=2*n) nn<<=1,ll++; 67 for(int i=0;i<=nn;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(ll-1)); 68 inv=qpow(nn,Mod-2); 69 b[1]=n+1; 70 ntt(a,1);ntt(b,1); 71 for(int i=0;i<=nn;i++) a[i]=1LL*a[i]*b[i]%Mod; 72 ntt(a,-1); 73 int ans=0; 74 for(int i=0;i<=n;i++) ans=(ans+1LL*a[i]*qpow(2,i)%Mod*fac[i])%Mod; 75 printf("%d\n",ans); 76 return 0; 77 } View Code

代碼只需在FFT基礎上修改一點點即可。

?

對于原根，因為你讀題時就知道模數，你可以自己打個暴力求一下。具體方法在FFT和NTT總結中有說。

然后你直接賦值原根G的值就好了。

?

2017-04-14?15:10:42

?

?

　　

?

轉載于:https://www.cnblogs.com/Konjakmoyu/p/6708996.html

總結

以上是生活随笔為你收集整理的【BZOJ 4555】 4555: [Tjoi2016Heoi2016]求和 （NTT）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。