$O(nm2^n)$ 得到 $70$ 分是怎么回事呢？$O(nm2^n)$ 相信大家都很熟悉，但是 $O(nm2^n)$ 得到 $70$ 分是怎么回事呢，下面就让小编带大家一起了解吧。

$O(nm2^n)$ 得到 $70$ 分，其实就是

#include<bits/stdc++.h>

using namespace std;

const int N=1e3+5, M=5e3+5, MOD=1e9+7;

int n, m, q; 

bitset<M> a[N], b[N];
unordered_map<bitset<M>, int> cnt[N];
unordered_map<bitset<M>, int>::iterator it;

int main()
{
	ios::sync_with_stdio(false);
	
	cin>>n>>m>>q;
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=1; i<=q; i++) cin>>b[i];
	
	cnt[0][a[0]]=1;
	for(int i=1; i<=n; i++) 
	{
		for(it=cnt[i-1].begin(); it!=cnt[i-1].end(); it++)
		{
			cnt[i][(*it).first&a[i]]=(cnt[i][(*it).first&a[i]]+(*it).second)%MOD;
			cnt[i][(*it).first|a[i]]=(cnt[i][(*it).first|a[i]]+(*it).second)%MOD;
		}
	}
	for(int i=1; i<=q; i++) cout<<cnt[n][b[i]]<<endl;
	
	return 0;
}

大家可能会很惊讶 $O(nm2^n)$ 怎么会得到 $70$ 分呢？但事实就是这样，小编也感到非常惊讶。

这就是关于暴力做法得到 $70$ 分的事情了，大家有什么想法呢，欢迎在评论区告诉小编一起讨论哦！

---

符号说明：下文的串均默认为长度为 $m$ 的 $01$ 串；集合 $X$ 的大小或者串 $X$ 中 $1$ 的数量均记为 $\#X$；变量 $\oplus$ 代表某种位运算；当串 $X$ 中 $1$ 的位置在 $Y$ 中均为 $1$，那么就记 $X\subseteq Y$。

（尽管看起来有点滥用符号，但实际上这里只是为了避免将串转成集合描述的麻烦，下文用到的串和集合其实没啥区别。）

---

记

$$S_n=\#\{0\oplus_0 a_1\oplus_1 a_2\cdots\oplus_{n-1} a_n |\oplus_i\in\{\land,\lor\}\}$$

目标是去算这个 $S_n$ 的上界。

跳过 observation，这里直接给出欲证明的性质

$$\forall x,y\in S_n,\#x\le \#y\Longleftrightarrow x\subseteq y$$

其中 $\Longleftarrow$ 根据定义即得，所以下文主要考虑 $\Longrightarrow$。

对 $n$ 归纳。$n=0$ 时显然；假设 $n=i-1$ 时成立，考虑 $n=i$，用反证法，假设

$$\exists p,q\in S_{i-1},\#(p\oplus_p a_i)\le \#(q\oplus_q a_i)$$

使得

$$(p\oplus_p a_i)\not\subseteq (q\oplus_q a_i)$$

上式蕴含了 $(p\oplus_p a_i)\not= (q\oplus_q a_i)$。分类讨论：

• $(\oplus_p,\oplus_q)=(\land,\land)$ 时，由归纳假设，可以分两类讨论
  • $p\subseteq q$，则 $(p\land a_i)\subseteq (q\land a_i)$，矛盾；
  • $q\subseteq p$，则 $(q\land a_i)\subseteq (p\land a_i)$，又因为 $\#(p\land a_i)\le \#(q\land a_i)$，从而 $(p\land a_i)= (q\land a_i)$，矛盾；
• $(\oplus_p,\oplus_q)=(\land,\lor)$ 时，由 $(p\land a_i)\subseteq a_i \subseteq(q\lor a_i)$，矛盾；
• $(\oplus_p,\oplus_q)=(\lor,\land)$ 时，由 $(q\land a_i)\subseteq a_i \subseteq(p\lor a_i)$，又因为 $\#(p\lor a_i)\le \#(q\land a_i)$，从而 $(q\land a_i)=(p\lor a_i)$，矛盾；
• $(\oplus_p,\oplus_q)=(\lor,\lor)$ 时，由归纳假设，可以分两类讨论
  • $p\subseteq q$，则 $(p\lor a_i)\subseteq (q\lor a_i)$，矛盾；
  • $q\subseteq p$，则 $(q\lor a_i)\subseteq (p\lor a_i)$，又因为 $\#(p\lor a_i)\le \#(q\lor a_i)$，从而 $(p\lor a_i)= (q\lor a_i)$，矛盾；

由数学归纳法得证。

---

由上面证明的结论即可直接推得

$$\forall x,y\in S_n,\#x=\#y\Longleftrightarrow x=y$$

因此对于 $\# x=0,1,\cdots,m$，对应的 $x$ 最多只有一个。因此

$$\#S_n\le m+1$$

这就证明了这个做法是 $O(nm^2/w)$ 的。