「Luogu5395」【模板】第二類斯特林數·行

problem

Solution

一句話題意：求\(_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}\)

根據第二類斯特林數的展開式，有
\[\begin{Bmatrix}n\\k\end{Bmatrix}=\frac{1}{k!}\sum_{i=0}^k(-1)^i\begin{pmatrix}k\\i\end{pmatrix}(k-i)^n\]

具體證明可以看這里

進一步整理，式子化為

\[\begin{Bmatrix}n\\k\end{Bmatrix}=\sum_{i=0}^k\frac{(-1)^i}{i!}\times \frac{(k-i)^n}{(k-i)!}\]

可以發現這是一個卷積的形式

構造多項式

\[F(x)=\sum_{i=0}^n\frac{(-1)^i}{i!}x^i\]

\[G(x)=\sum_{i=0}^n\frac{i^n}{i!}x^i\]

\[S(x)=F(x)*G(x)\]

則\(S(x)\)的\(k\)次項系數即為\(\begin{Bmatrix}n\\k\end{Bmatrix}\)

預處理階乘的逆元

本題的模數有原根\(3\)，所以直接用\(NTT\)做卷積就可以了

時間復雜度\(O(n\log n)\)

Code

#include <cstdlib> #include <iostream> #include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #define inv(x) (fastpow((x),mod-2)) using namespace std; typedef long long ll;const int maxn=200005; const ll mod=167772161,g=3,ig=55924054; int n; ll a[maxn<<2],b[maxn<<2],ifac[maxn];ll fastpow(ll a,ll b) {ll re=1,base=a;while(b){if(b&1)re=re*base%mod;base=base*base%mod;b>>=1;}return re; }int len; int rev[maxn<<2];void NTT(ll *f,int type) {for(register int i=0;i<len;++i)if(i<rev[i])swap(f[i],f[rev[i]]);for(register int p=2;p<=len;p<<=1){int length=p>>1;ll unr=fastpow(type==1?g:ig,(mod-1)/p);for(register int l=0;l<len;l+=p){ll w=1;for(register int i=l;i<l+length;++i,w=w*unr%mod){ll tt=f[i+length]*w%mod;f[i+length]=(f[i]-tt+mod)%mod;f[i]=(f[i]+tt)%mod;}}}if(type==-1){ll ilen=inv(len);for(register int i=0;i<len;++i)f[i]=f[i]*ilen%mod;} }int main() {scanf("%d",&n);ifac[0]=1;for(register ll i=1;i<=n;++i)ifac[i]=ifac[i-1]*i%mod;ifac[n]=inv(ifac[n]);for(register ll i=n-1;i;--i)ifac[i]=ifac[i+1]*(i+1)%mod;for(register int i=0,o=1;i<=n;++i,o=mod-o)a[i]=o*ifac[i]%mod,b[i]=fastpow(i,n)*ifac[i]%mod;for(len=1;len<=n+n;len<<=1);for(register int i=1;i<len;++i)rev[i]=(rev[i>>1]>>1)|((i&1)?(len>>1):0);NTT(a,1);NTT(b,1);for(register int i=0;i<len;++i)a[i]=a[i]*b[i]%mod;NTT(a,-1);for(register int i=0;i<=n;++i)printf("%lld ",a[i]); }

轉載于:https://www.cnblogs.com/lizbaka/p/11370782.html

總結

以上是生活随笔為你收集整理的「Luogu5395」【模板】第二类斯特林数·行的全部內容，希望文章能夠幫你解決所遇到的問題。

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