正題

題目鏈接:https://www.luogu.com.cn/problem/P5825

---

題目大意

對于每個$k$，求有多少個長度為$n$的排列有$k$個位置上升。
$1\le n\le 2\times 10^5$

---

解題思路

考慮到同時考慮大于和小于十分麻煩，設$f_i$表示欽定$i$個上升時的方案

連續的上升段可以視為同一個組，那么整個序列就會被分為$m=n?k$段，每個組內都是無序的。

所以可以考慮一下$\text{EGF}$來做，因為不能選空段，那么每一段的生成函數就是$e^x?1$。

也就是$f_{n?m}=(e^x?1{)}^m[x^n]$。二項式定理展開一下
$$f_m=\sum _{i=0}^m\left(\genfrac{}{}{0ex}{}{m}{i}\right)(?1{)}^{m?i}{e}^{ix}$$
$$=\sum _{i=0}^m\frac{m!}{i!(m?i)!}(?1{)}^{m?i}\frac{i^n}{n!}$$
$$=\frac{m!}{n!}\sum _{i=0}^m\frac{(?1{)}^{m?i}}{(m?i)!}\frac{i^n}{i!}$$
$\text{NTT}$卷起來就好了。

然后$g_i$表示恰好有$i$個的話，上二項式反演即可
$$f_i=\sum _{j=0}^i\left(\genfrac{}{}{0ex}{}{i}{j}\right)g_j?g_i=\sum _{j=i}(?1{)}^{j?i}(\genfrac{}{}{0ex}{}{j}{i})f_j$$
這個也是顯然可以卷積快速求得的。

順帶一提的是，這個求得其實就是歐拉數$?\begin{array}{c}n\\ k\end{array}?$

聯立上面的$f_i$和$g_i$的式子可以得到歐拉數的通式
$$?\begin{array}{c}n\\ k\end{array}?=\sum _{i=0}^{n?k}(?1{)}^{n?k?i}{i}^n(\genfrac{}{}{0ex}{}{n+1}{k+j+1})$$

這個可以一次卷積求得

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

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=8e5+10,P=998244353; ll n,m,inv[N],fac[N],f[N],g[N],r[N]; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; } void NTT(ll *f,ll op){for(ll i=0;i<m;i++)if(i<r[i])swap(f[i],f[r[i]]);for(ll p=2;p<=m;p<<=1){ll tmp=power(3,(P-1)/p),len=(p>>1);if(op==-1)tmp=power(tmp,P-2);for(ll k=0;k<m;k+=p){ll buf=1;for(ll i=k;i<k+len;i++){ll tt=f[i+len]*buf%P;f[i+len]=(f[i]-tt+P)%P;f[i]=(f[i]+tt)%P;buf=buf*tmp%P;}}}if(op==-1){ll invn=power(m,P-2);for(ll i=0;i<m;i++)f[i]=f[i]*invn%P;}return; } signed main() {scanf("%lld",&n);inv[1]=1;for(ll i=2;i<=n;i++)inv[i]=P-inv[P%i]*(P/i)%P;inv[0]=fac[0]=1;for(ll i=1;i<=n;i++)inv[i]=inv[i-1]*inv[i]%P,fac[i]=fac[i-1]*i%P;for(ll i=0;i<=n;i++)f[i]=inv[i]*power(i,n)%P,g[i]=(i&1)?(P-inv[i]):inv[i];m=1;while(m<=2*n)m<<=1;for(ll i=0;i<m;i++)r[i]=(r[i>>1]>>1)|((i&1)?(m>>1):0);NTT(f,1);NTT(g,1);for(ll i=0;i<m;i++)f[i]=f[i]*g[i]%P;NTT(f,-1);memset(g,0,sizeof(g));for(ll i=0;i<m;i++)f[i]=(i<n)?(f[i+1]*fac[i+1]%P):0;for(ll i=n;i<m;i++)f[i]=0;for(ll i=0;i<n;i++){f[i]=f[i]*fac[n-i-1];f[i]=(i&1)?(P-f[i]):f[i];g[i]=inv[i];}NTT(f,1);NTT(g,1);for(ll i=0;i<m;i++)f[i]=f[i]*g[i]%P;NTT(f,-1);for(ll i=0;i<n-i-1;i++)swap(f[i],f[n-i-1]);for(ll i=0;i<n;i++){f[i]=f[i]*inv[i]%P;f[i]=((n-i)&1)?f[i]:(P-f[i]);printf("%lld ",f[i]%P);}putchar('0');return 0; }

總結

以上是生活随笔為你收集整理的P5825-排列计数【EGF,NTT】的全部內容，希望文章能夠幫你解決所遇到的問題。

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