LightGHLi's Blog

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

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

当i = 1时。当前没有被使用的边的集合为L1(m)，因为图连通，所以通过Kruskal算法插入L1(m)后，所得到的生成森林一定是一棵最小生成树，即T1。又因为F1(m)为通过Kruskal算法插入L1(m)后得到的生成森林的边集，所以F1(m)为T1的边集，命题成立。
假设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的边集。

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

题目想说的是，如果两个点(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))中属于同一连通分量。

题意

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

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

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