2024暑假集训第一周总结

迟来的第一周总结……

第一周一共打了四场比赛。整体感受是：还有很多知识点没学，或者学得不够深。八月之前应该会持续补新知识，八月之后再重点加深理解和熟练度。比赛前期大家能过的题差距不大，后期更多取决于知识点覆盖和掌握程度。

牛客多校一

这一场补了三个题。

A - A Bit Common

题意

给定 $n$、$m$、$q$，其中 $n,m \le 5000$，$q \le 10^9$。从 $[0,2^m)$ 中取数构成长度为 $n$ 的序列，要求序列中存在一个子序列，其按位与结果为 $1$。求方案数并对 $q$ 取模。

分析

由于 $n,m$ 都是 $5000$，时间复杂度需要控制在 $O(n^2)$ 附近，因此可以考虑枚举子序列的长度。

假设子序列长度为 $k$，则位置选择有 $C(n,k)$ 种。一个数的按位与为 $1$ 时，最低位必须为 $1$；多个数按位与为 $1$ 时，它们最低位都为 $1$，其他位不能同时全为 $1$。

剩下的 $n-k$ 个数可以任意选择，因此得到公式：

$$\sum_{k=2}^{n} C(n,k)(2^k-1)^{m-1}2^{(m-1)(n-k)}$$

组合数用递推式预处理，枚举序列计算答案，整体时间复杂度约为 $O(n^2)$。这题本身不算难，主要还是组合计数推式子的训练不够。

B - A Bit More Common

题意

题意和范围与 A 题类似，区别是要求序列中存在两个按位与结果为 $1$ 的子序列，计算满足条件的方案数。

分析

这题可以沿用 A 题的计数思路，但需要额外处理两个子序列之间的重叠关系。相比 A 题，难点不在组合数本身，而在于如何避免把同一组序列重复计入多个子序列条件中。