验题人/参赛者题解 | F Broken LED Lights

验题人（我）的做法：

对灯管进行状压后，枚举每两个数，状态相同的灯管集合。

设第 $i$ 盏灯和第 $j$ 盏灯的状态相同的灯管集合为 $S_{i,j}$ ，那么答案（即保留的灯管集合）不能为任意 $S_{i,j}$ 的子集，这启发我们考虑对 $S$ 做 $AND$ 卷积（即高维后缀和）。时间复杂度为 $O(T(7m)2^{7m})$ ，不能通过。

对于 $S$ 的每个元素，我们只关心它是否为 $0$ 。这启发我们使用 $std::bitset$ 去优化。对于每个二进制位 $i$ ，使用一个 $std::bitset$ 去记录位运算卷积的系数。具体地，对于每个状态 $mask$ ，如果它的第 $i$ 位为 $1$ ，就把第 $i$ 个 $std::bitset$ 的 $mask$ 位设置为 $1$ 。那么做 $AND$ 卷积的时候，枚举二进制位 $i$ ，把对应的 $std::bitset$ 拿出来跟 $S$ 进行与运算，左移 $2^i$ 位，再与 $S$ 进行或运算即可。时间复杂度为 $O((7m)2^{7m} + T(7m)2^{7m}/w)$ 。

提交链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78736158

一位参赛者的做法：

主要思路还是 $AND$ 卷积。但是注意到 $T\le 100$ ，因此可以这把 $T$ 组位运算卷积用 $int128$ 打包成一个数，最后做一次 $AND$ 卷积。时间复杂度为 $O((7m)2^{7m} + T2^{7m})$ 。

提交链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=78730188

类似的处理方法：https://codeforces.com/contest/1034/problem/E

验题人/参赛者题解 | #F Broken LED Lights#

验题人/参赛者题解 | F Broken LED Lights