Luogu P5395 第二类斯特林数·行

\(\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 ;
}

Luogu P5395 第二类斯特林数·行

上一篇:基本的DOS命令


下一篇:访问c++类的私有成员