[CF1097F] Alex and a TV Show

CF1097F Alex and a TV Show

题解

考虑到正常维护每个数是否出现过并不能做(第三个操作无法实现)。考虑类似FFT一样,维护一个可以进行这些操作的一些数,然后通过一些操作计算答案。

使用bitset,因为存储的数都是0/1中的一个。然后数集 $i$ 维护一个bitset$f_i$ ,$f_{i,j}$表示在 $i$ 这个数集内 $j$ 的倍数数量。下面考虑如何应对每一个操作:

  1. 预处理bitset数组 $p_{i}$ 表示只有第 $i$ 个数的数组的0/1取值。使用时直接用bitset=操作即可。
  2. 相当于^操作。
  3. 相当于&操作。
  4. 这个操作比较棘手一些。首先我们知道$f(x)=\sum_{x|d} g(d)$,那么$g(x)=\sum_{x|d}\mu(\frac{d}{x}) f(d)$。这完全吻合这道题询问的形式。那么我们要做的是 $\mu$ 和 $f$ 的对位相乘(需要做一些细节处理)后1的个数。

代码

发表评论