本文共 2032 字，大约阅读时间需要 6 分钟。
题目大意： 多次询问，求贝尔数的第 n n n 项。
题解
先考虑只有一个集合的情况，设 f i f_i fi 表示 i i i 个不同元素分成 1 1 1 个集合的方案数，显然有 f i = 1 f_i=1 fi=1，由于不允许有空集，所以 f 0 = 0 f_0=0 f0=0。
设 f f f 的 E G F EGF EGF 为 F ( x ) F(x) F(x)，发现 F ( x ) F(x) F(x) 正好就是 e x − 1 e^x-1 ex−1。
然后考虑求答案：显然题目要我们求的其实就是贝尔数，设贝尔数的第 n n n 项为 B n B_n Bn，设 G ( x ) G(x) G(x) 为 B B B 的 E G F EGF EGF，那么满足 G ( x ) = ∑ i = 0 F i i ! G(x)=\sum_{i=0} \dfrac {F^i} {i!} G(x)=∑i=0i!Fi，所以 G ( x ) = e F = e e x − 1 G(x)=e^F=e^{e^x-1} G(x)=eF=eex−1。
由于是 E G F EGF EGF，所以 B n = [ x n ] G ( x ) × n ! B_n=[x^n]G(x)\times n! Bn=[xn]G(x)×n!。
顺便纪念一下，除了求逆部分漏了个取模，第一次 一次写对多项式全家桶！
代码如下：
#include #include #include #include using namespace std;#define maxn 300010#define mod 998244353#define MS(f,x) memset(f,0,4<<(x))#define bin(x) (1<<(x))int T,n;int inv[maxn],log_2[maxn];int ksm(int x,int y){ int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}int *w[30];void prep(int N){ inv[1]=1;for(int i=2;i<=N;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod,log_2[i]=ceil(log2(i)); for(int i=1,wn;i<=log_2[N];i++){ w[i]=new int[bin(i-1)];w[i][0]=1;wn=ksm(3,(mod-1)/bin(i)); for(int j=1;j >1]>>1)|((i&1)<<(lg-1));}void ntt(int *f,int lg,int type=0){ limit=bin(lg);if(type)reverse(f+1,f+limit); for(int i=1;i >1);int lg=log_2[ln*2-1]; get(lg);MS(A,lg);MS(B,lg);memcpy(A,f,ln<<2);memcpy(B,g,ln<<2); ntt(A,lg);ntt(B,lg);for(int i=0;i 0;i--)g[i]=1ll*f[i-1]*inv[i]%mod;g[0]=0;}void getln(int *f,int *g,int ln){ MS(C,log_2[ln*2-1]);MS(D,log_2[ln*2-1]); getinv(f,C,ln);Dao(f,D,ln);NTT(C,D,ln);Jifen(C,g,ln);}void getexp(int *f,int *g,int ln){ if(ln==1){ g[0]=1;return;}getexp(f,g,(ln+1)>>1); MS(E,log_2[ln*2-1]);getln(g,E,ln); for(int i=0;i =1;i--)inv_fac[i]=1ll*inv_fac[i+1]*(i+1)%mod;}int F[maxn],G[maxn];void solve(){ Wk(262144);prep(262144); for(int i=1;i<=100000;i++)F[i]=inv_fac[i]; getexp(F,G,100001);for(int i=1;i<=100000;i++)G[i]=1ll*G[i]*fac[i]%mod;}int main(){ solve();scanf("%d",&T);while(T--)scanf("%d",&n),printf("%d\n",G[n]);}
转载地址：http://ksnib.baihongyu.com/