CF908E
给定 \(m\)，令 \(M = 2^m -1\)。给定 \(\{0,1,\cdots, M\}\) 的大小为 \(n\) 的子集 \(T\)，定义集合 \(T \subseteq S \subseteq \{0,1,\cdots,M\}\) 是好的当且仅当：
\(a \in S \Rightarrow a \oplus M \in S\)
\(a,b \in S \Rightarrow a\ and\ b \in S\)
求好的集合的个数
\(1 \leq m \leq 1000, 1 \leq n \leq min(2^m, 50)\)
-
我们先考虑假如得到了一个不完整的 \(S\) 如何把他变为合法的集合
-
打表找规律
-
可以发现当加入了
00011和00111后，他会把54分成一部分，3一部分，21一部分，然后填0/1，答案是： -
00000 00011 00100 00111 11000 11011 11100 11111 -
可以发现，若 \(S\) 中的 \(x_1,x_2,\cdots,x_t\) 位在所有数中要么同为 \(1\)，要么同为 \(0\)，也就是说相同，那么他们就会”打包“在一起，在 \(S\) 中独立取 \(0/1\)
-
其实这不是巧合，这是有依据的
-
第一条操作的意思显然就是 \(a \in S \Rightarrow (\sim a) \in S\)
-
而我们有：
- \[\begin{align} & a\ or\ b = \sim((\sim a)\ and\ (\sim b)) \\ & a \oplus b = \sim((\sim(a\ or\ b)\ or\ (a\ and\ b)) \end{align} \]
-
因此上述的操作最终制造出了一个异或操作，即这些数构成了一个异或的线性基
-
因此我们只需要按位进行集合划分
-
设 \(dp_i\) 表示 \(i\) 位数，拆开 or 不拆开的所有方案数，有转移：
- \[dp_i \leftarrow \sum_{j=0}^{i-1} \binom{i-1}{j} dp_{i-j-1} \]
-
大致意思是考虑第 \(i\) 位数和另外 \(i-1\) 个位置中 \(j\) 个位置划分成一个集合，然后继续递归
-
最后只需要根据乘法原理相乘即可
-
最终复杂度为 \(O(m^2+mn)\)