\(\texttt{Description}\)
第二类斯特林数 \(\begin{Bmatrix} n \\m \end{Bmatrix}\) 表示把 \(n\) 个不同元素划分成 \(m\) 个相同的集合中（不能有空集）的方案数。
给定 \(n\)，对于所有的整数 \(i\in[0,n]\)，你要求出 \(\begin{Bmatrix} n \\i \end{Bmatrix}\)。
\(1\le n\le 2\times 10^5\)
\(\texttt{Solution}\)
讲课把这个题讲了，来写个题解。
实际上是二项式反演的模板题。
前置知识
- ntt
- 二项式反演
解法
考虑如下式子：
\[ m^n = \sum_{i=0}^m \binom{m}{i} \times \begin{Bmatrix} n \\i \end{Bmatrix} \times i!
\]
关于式子的正确性，考虑组合意义：左侧是 \(m\) 个不同盒子放 \(n\) 个球的方案数，右边是枚举 \(i\) 个集合非空，赋标号。
然后随便二项式反演一下：
\[ m!\begin{Bmatrix} n \\m \end{Bmatrix} = \sum_{i=0}^m(-1)^{m-i}\binom{m}{i} i^n
\]
\[ \begin{Bmatrix} n \\m \end{Bmatrix} = \sum_{i=0}^m\dfrac {(-1)^{m-i}} {(m-i)!} \dfrac {i^n}{i!}
\]
显然的加法卷积。
\(\texttt{Code}\)
inline void solve() {
cin >> n ;
for (int i = 0; i <= n; ++i) a[i] = (i&1?mod-ifac[i]:ifac[i]);
for (int i = 0; i <= n; ++i) b[i] = 1ll*ksm(i,n)*ifac[i] % mod ;
// for (int i = 0; i < n; ++i) cout << a[i] << " " << b[i] << endl ;
mul(a,b,c,n<<1) ;
for (int i = 0; i <= n; ++i) cout << c[i] << " ";
cout << endl ;
}