\(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)\)

Read More

B

采用数学归纳法证明Fi(m)为Ti的边集:

  1. 当i = 1时。当前没有被使用的边的集合为L1(m),因为图连通,所以通过Kruskal算法插入L1(m)后,所得到的生成森林一定是一棵最小生成树,即T1。又因为F1(m)为通过Kruskal算法插入L1(m)后得到的生成森林的边集,所以F1(m)为T1的边集,命题成立。
  2. 假设i = k时,成立。则当i = k + 1时,当前没有被使用的边的集合为L1(m) \ F1(m) \ F2(m) \ ... \ Fk(m) = L2(m) \ F2(m) \ ... \ Fk(m) = Lk(m) \ Fk(m) = Lk+1(m)。因为图连通,所以通过Kruskal算法插入Lk+1(m)后,所得到的生成森林一定是一棵最小生成树,即Tk+1。又因为Fk+1(m)为通过Kruskal算法插入Lk+1(m)后所得到的生成森林的边集,所以Fk+1(m)为Tk+1的边集,命题成立。

综上所述,对于正整数i,Fi(m)为Ti的边集。

C

这个就不采用过于形式化的证明了。

题目想说的是,如果两个点(u, v)在(V, Fi(t))中属于同一连通分量,那么对于任意的j < i,(u, v)在(V, Fj(t))中也属于同一连通分量。

这个是由Kruskal算法造成的,Kruskal算法每次选一条边,判断这两个点是否在同一个连通分量中,如果在,则放弃这条边,如果不在,则将选择这条边,并将两个点合并到同一连通分量中。

(u, v)在(V, Fi(t))中属于同一连通分量,那么这条连接(u, v)的边一定是在(V, Fj(t))中被放弃过的,所以(u, v)在(V, Fj(t))中属于同一连通分量。

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