CF1995D Cases
题意：
给定一个长为 \(n\)，字符集大小 \(c=18\) 的字符串，给定一个整数 \(m\) ，你需要求出一个字符集合 \(S\) 满足在原串中每 \(m\) 个字符中至少有一个被包含在集合 \(S\) 中。
其中 \(m\le n\le 2^{18}=262144\)
思路：
最暴力的想法：\(dp_{i,S}\) 表示已钦定 \(S\) 内的点都选取，当前推到了字符串的第 \(i\) 位，是否可行。时间复杂度 \(O(n2^{18})\) 。进一步找性质发现对于一个位置 \(i\) ，只会往后转移 \(c\) 个位置，所以我们能否尝试根据这个性质 bitset 优化？显然无法操作，因为一是无法分割 bitset 成若干位置，二是 \(n\) 过大导致 bitset 时间复杂度无法接受。
更换思路，我们考虑什么样的 \(S\) 是一定无法成立的。可以发现，若连续 \(k\) 个字符所形成的字符集 \(T\) 满足 \(T\cap S=\empty\) ，一定无法成立。但是我们这样的 \(T\) 的数量 \(=n-k+1\) ，暴力判断仍然不行，因为这样的 \(S\) 之间没有相关性，即无法相互推导（考虑到两个不相等的集合 \(S_1,S_2\cap T=0\)，他们形成的并集也一定与 \(T\) 的交集为空）。考虑优化。直接找到满足这种性质的 \(S\) 显然不好找，由于 \(T\cap S=\empty\) ，所以 \(T\cap \overline{S}=T\) ，并且对于任意字符 \(c\notin \overline{S} ,(\{c\}\cup\overline S)\cap T=T\)，所以我们不妨尝试寻找这样的 \(\overline{S}\) 。
这是简单的，先标记所有的 \(dp_T=1\) ，然后按照上面的性质以此遍历所有的集合。