\(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}^n Stirling2(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)\)

Read More

题意

Alice 想要得到一个长度为 \(n\) 的序列,序列中的数都是不超过 \(m\) 的正整数,而且这 \(n\) 个数的和是 \(p\) 的倍数。Alice 还希望,这 \(n\) 个数中,至少有一个数是质数。Alice 想知道,有多少个序列满足她的要求,答案对 \(20170408\) 取模。

其中,\(1 \leq n \leq 10^9\)\(1 \leq m \leq 2 \times 10^7\)\(1 \leq p \leq 100\)

Read More

题意

\(m\) 个石头围成一个圆圈,编号从 \(0\)\(m - 1\)\(n\) 只青蛙,编号从 \(1\)\(n\)。第 \(i\) 只青蛙只能跳 \(a_i\) 步,即从 \(j\ mod\ m\)\((j + a_i)\ mod\ m\)。求被青蛙踩过的石头的编号和,每个石头的编号只算一次。

不超过 \(20\) 组数据,其中,\(1 \leq m \leq 10^9\)\(1 \leq n \leq 10^4\)

Read More

题意

Alice 和 Bob 在玩取石子游戏。

\(n\) 堆石子,\(a_1, a_2, \ldots, a_n\) 表示每堆石子的个数,\(b_1, b_2, \ldots, b_n\) 代表每堆石子的约束类型。

Bob 每次可以从其中一堆中取走任意数量的石子。

\(b_i = 0\),Alice 可以从该堆中取走任意数量的石子。

\(b_i = 1\),Alice 只能从该堆中取走奇数数量的石子。

\(b_i = 2\),Alice 只能从该堆中取走偶数数量的石子。

无法取石子的人输,Alice 先取石子,问谁必胜?

\(1 \leq n \leq 10^5\)\(1 \leq a_i \leq 10^9\)\(0 \leq b_i \leq 2\)

保证所有测试数据中 \(n\) 的和不超过 \(10^6\)

Read More