贝尔数

定义

\(B_n\) 是将 \(n\) 个不同的元素划分为两两不相交的非空子集的方案。

公式

\[ \begin{align} B_{n+1}&=\sum_{i=0}^nC_n^i*B_i\\ B_n&=\sum_{i=0}^nS_2(n,i) \end{align} \]

模版

递推\(O(n^2)\)多项式\(O(n*\log n)\)

C++
for (int i = 1 ; i <= n ; i++) {
    B[i][0] = B[i - 1][i - 1];
    for (int j = 1 ; j <= i ; j++) {
        B[i][j] = B[i - 1][j - 1] + B[i][j - 1];
    }
}

C++
{ 多项式基础模版 }
int n;
cin >> n;
cout << other::Bell(n);