\(B_n\)表示将\(n\)个不同的元素划分为若干非空集合的方案数。

递推式:\(B_{n + 1} = \sum_{k = 0}^nC(n, k)B_k\)

证明:考虑第\(n+1\)个元素,可以把它和\(k\)个其他元素划分在一起,那么剩余\(n - k\)个元素有\(B_{n - k}\)种划分。

递推式:\(B_n = \sum_{k = 0}^nStirling2(n, k)\)

证明:\(Stirling2(n, k)\)表示将\(n\)个不同的元素划分为\(k\)个非空集合的方案数。

Bell三角

1

1 2

2 3 5

5 7 10 15

15 20 27 37 52

  1. \(b(0, 0) = 1\)
  2. \(b(i, 0) = b(i - 1, i - 1)\)
  3. \(b(i, j) = b(i, j - 1) + b(i - 1, j - 1)\)

证明:

\[ \begin{align} b(n, 0) &= b(n - 1, n - 1)\\ &= b(n - 1, n - 2) + b(n - 2, n - 2)\\ &= b(n - 1, n - 3) + 2b(n - 2, n - 3) + b(n - 3, n - 3)\\ &= \dots\\ &= \sum_{k = 0}^{n - 1}C(n - 1, k)b(k - 1, 0) \end{align} \]

1

2 1

5 3 2

15 10 7 5

32 37 27 20 15

  1. \(b(0, 0) = 1\)
  2. \(b(i, i) = b(i - 1, 0)\)
  3. \(b(i, j) = b(i, j + 1) + b(i - 1, j)\)

\(p\)为任意素数

模运算性质:\(B_{p + n} \equiv B_n + B_{n + 1} \pmod p\)

模运算性质:\(B_{p^m + n} \equiv mB_n + B_{n + 1} \pmod p\)

周期:\(\frac{p^p - 1}{p - 1}\)

\(10\)个Bell数:\(B_0 = 1\), \(B_1 = 1\), \(B_2 = 2\), \(B_3 = 5\), \(B_4 = 15\), \(B_5 = 52\), \(B_6 = 203\), \(B_7 = 877\), \(B_8 = 4140\), \( B_9 = 21147\)

Bell数预处理:时间复杂度\(O(n^2)\) 空间复杂度\(O(n)\)

求第\(n\)个Bell数模任意素数\(p\)

构造\(p \times p\)的矩阵,矩阵快速幂。时间复杂度\(O(p^3log(n/p))\)

预处理\(B_0\sim B_p\),将\(n\)转换成\(p\)进制,\(n = a_0 + a_1p + a_2p^2 + \dots + a_{lim}p^{lim}\),设\(d_{i, j}(k)\)表示\(B_{jp^i + k + a_1p + \dots + a_{i - 1}p^{i - 1}}\),则答案为\(d_{lim, a_{lim}}(a_0)\)。时间复杂度\(O(p^2log_pn)\)

求第\(n\)个Bell数模任意数

中国剩余定理合并

HDOJ 2512

HDOJ 4767

comments powered by Disqus