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\) ,然后按照上面的性质以此遍历所有的集合。