[ABC423F] Loud Cicada 题解

赛时

看到这个题先乱写了一个状压，发现显然没有正确性，然后开始乱推容斥，后面发现自己想复杂了，想到了本文的做法，但是因为太慌了在一直在乱写，调半天没过样例，最后在 85 分钟才做出来，菜死了。

看到 显然状压。首先容易想到设 表示一定出现的蝉种类形成的集合为 的年份数量（没有被选中的蝉不一定出现）， 表示出现的蝉种类形成的集合为 时的年份数量（没有被选中的蝉一定不出现）， 表示出现的蝉种类形成的集合为 时，每种蝉出现年份的最小倍数，显然有 。若精细实现（ 由 转移而来），可以做到 计算 与 （忽略 的时间复杂度）。

然而，我们要求的是 。容易发现，有 ，即 。于是考虑倒序枚举 ，再枚举满足 的 进行转移，可是这样是 的，显然不行。不过这个时候你发现，这一部分可以用 [ARC205E] Subset Product Problem 里教的 trick 解决，这里不再详细展开。于是这道题就做完了。

但是这个东西的时间复杂度是多少呢？如果我们固定 的前 位，枚举后 位的子集，此时的时间复杂度是 。而 的前 一共有 种情况，所以时间复杂度是 。再加上计算 与 ，总时间复杂度是 。状压本身常数小，所以跑起来并不是很卡。

赛时提交记录，没有精细实现，时间复杂度 。

关于官方题解

官方题解与本文的区别在于计算 的方式不同。官方题解中，定义「一致条件 」表示 中的蝉出现（没有被选中的蝉一定不出现），「部分条件 」 表示 中的蝉一定出现（没有被选中的蝉不一定出现）。它是这样计算 的（机翻）：

一旦求出满足各个部分条件的元素个数，通过应用零变换的逆变换（也称为梅比乌斯变换），就可以得到满足各个一致条件的元素个数，从而得到答案。简单来说，就是「对于条件 使用一致条件，对于条件 使用部分条件」这样的条件设置方式，并逐步将部分条件中的元素每次增加 转换为一致条件进行计算。

时间复杂度 。