CF908E New Year and Entity Enumeration

题意：给定 $n$ 个二进制下 $m$ 位的数，问有多少个集合 $S$ 包含这 $n$ 个数并且满足取反、与运算封闭（即任意对 $S$ 集合内部元素取反或者是与运算操作得到的数都 $\in S$），问都多少个这样的 $S$。$m\le 1000$，$n\le 50$，对 ${10}^9+7$ 取模。

首先容易发现一个结论：或和异或操作都是可以实现的。

一顿构造得到：$a|b=\sim ((\sim a)\odot (\sim b))$，$a\oplus b=(a|b)\odot (\sim (a\odot b))$。那么下面相当于 3 种基本运算都可以使用并且是封闭的。

假设一个集合 $\{x_1,x_2,\dots ,x_k\}$ 在 $n$ 个数中，这些位置出现 01 是相同的（即要么都出现 0，要么都出现 1）。考虑以下一个结论：$S$ 和这样的集合划分一一对应。

首先如果一个集合内出现了一个不和别人相同的，那么比如在某一位 $x_1=0$，$x_2=1$，那么我们取反就可以得到 $x_1=1,x_2=0$ 的情况，这样下去，那么 $x_1$ 和 $x_2$ 就不是一个集合的了。

一个集合会一起出现 01 两种情况，不同集合之间随意组合，然后就可以得到 $S$ 的所有元素了。

容易发现如果两个位置在某个数出现的是不同的，那么这两个永远不可能成为一个集合。也就是说我们只需要关心每个数出现的 bit 都是相同的，这些位置的才可能被划分为一个集合。

怎样固定大小求集合划分计数呢？容易发现这个就是 Bell 数，当然其实也是第二类斯特林数一行的和。随便做做就可以 $O(m^2)$ 啦。

最后复杂度不高，可以轻松通过。判断每个 bit 是不是相同显然可以压位扔到 std::map 里。

void init()
{
	fact[0] = infact[0] = 1;
	for (int i = 1; i < N; ++ i) fact[i] = (LL) fact[i - 1] * i % Mod;
	infact[N - 1] = qpow(fact[N - 1]);
	for (int i = N - 2; i; -- i) infact[i] = (LL) infact[i + 1] * (i + 1) % Mod;
	B[0] = 1;
	for (int i = 0; i < N - 1; ++ i)
		for (int j = 0; j <= i; ++ j) B[i + 1] = (B[i + 1] + (LL) C(i, j) * B[j]) % Mod;
}
 
int main()
{
	init();
	std::cin >> m >> n;
	for (int i = 1; i <= n; ++ i)
		for (int j = 1, t; j <= m; ++ j)
		{
			scanf("%1d", &t);
			if (t) s[j] |= 1LL << i;
		}
	for (int i = 1; i <= m; ++ i) ++ F[s[i]];
	int res = 1;
	for (auto [s, cnt] : F) res = (LL) res * B[cnt] % Mod;
	std::cout << res << '\n';
	return 0;
}