方知蓦然回首之时
那人却已不在灯火阑珊处

分类 题解 下的文章

c_0 / c_1 / c_? 表示举报序列中 0 / 1 / \text{?} 的数量。

  • 2^{c_?} 的做法,暴力枚举剩余位;
  • 2^{c_0} 的做法,FWT 预处理一遍,固定所有的 1 位,然后对 0 位进行容斥;
  • 2^{c_1} 的做法,FWT 预处理一遍,固定所有的 0 位,然后对 1 位进行容斥。

可以发现我们最后的复杂度即 O(n \log n + q \min(2^{c_0}, 2^{c_1}, 2^{c_?})) = O(n \log n + 2^6 q) 。可以通过此题。

READ MORE

对于每个联通块,可以看做进出了若干次将其走完,显然可以暴力状压预处理出走 ii \in [1, k])步将该联通块走完的方案数。题意转换为,有 n 个颜色染若干个格子,相邻两个格子不能同色,某种颜色染了的次数唯一对应一个固定权值,一种方案的权值为每种颜色分别染的次数对应的权值的连乘积。这显然可以通过二项式反演来求。

READ MORE

联测的题,刚好前几天做过类似的 idea 结果就 AC 了 QAQ ...

考虑对于每个 k ,处理出 b_{1 ... n - k + 1} ,对于 b 的每个长度超过 k 的极长连续段连边,可以用调和级数证明总次数不会超过 O(n \log n) 。使用后缀数组维护,类似「优秀的拆分」,也可以直接二分。后缀数组的复杂度是 O(n \log n)

考虑连边,可以利用「萌萌哒」一题的 idea ,在倍增数组上递归合并,如果左右两边已经相同就 return 掉否则就计算到答案中。可以证明这个的复杂度是均摊 \log n 级别的。

故如果使用后缀数组 + ST 表 + 倍增并查集,复杂度为 O(n \log n \times \alpha(n)) ,可以通过此题。在 n 较小 T 较大的数据点可能因为常数原因 TLE ,可以考虑对于 n 足够小的部分 O(n^2) 暴力做。

READ MORE