子集 dp 的一个 trick.
根据 Lucas 定理,显然就是要求对于子序列 $p$ 中相邻两个数,满足 $p_{i}$ 是 $p_{i-1}$ 的子集.
设 $f(i)$ 表示以 $i$ 结尾的子序列数目,依次计算每个 $f(a_i)$ ,转移时大力枚举 $a_i$ 的超集.
记 $k=\log \max a_i$ ,由于保证了 $a_i$ 互不相同,时间复杂度 $O(3^k)$ ,然而这样就可以直接干过去,可以算作事故了.
考虑进一步优化,将前 $\frac k 2$ 个数位和后 $\frac k 2$ 个数位分开考虑.
设 $s(x)$ 表示 $\sum f(y)$ ,其中 $y$ 满足 $y$ 的前 $\frac k 2$ 位和 $x$ 的前 $\frac k 2$ 位相同, $y$ 的后 $\frac k 2$ 位是 $x$ 的后 $\frac k 2$ 位的超集.
转移时,只需要枚举 $a_i$ 前 $\frac k 2$ 位的超集即可算出 $f(a_i)$ ,然后枚举 $a_i$ 后 $\frac k 2$ 位的子集去更新 $s$ .
保证了 $a_i$ 互不相同,所以对于每种前面的 $\frac k 2$ 位,只会枚举 $2^{\frac k 2}$ 次超集,后面枚举子集的分析是同理的.
时间复杂度 $O(6^{\frac k 2})$ .
如果不保证元素互不相同,暴力做法会被卡到 $O(n\cdot 2^k)$ ,而将数位分开考虑的做法会退化到 $O(n\cdot 2^{\frac k 2})$ .
1 | //%std |