Everything on It ARC096E

[ARC096E] Everything on It

称一个不可重集 $a$ 合法当且仅当：

• $a$ 中仅含 $[0,2^n-1]$ 中的数。
• 对于任意一个二进制位 $0\le i<n$，$a$ 中至少有 $2$ 个数满足其在这一二进制位为 $1$ 。

计数合法的 $a$。

$n\le 3000$。对一个质数 $m$ 取模。

先来基本的推式子：

$$\begin{aligned} \text{Ans}&=\sum_a\prod_{i=1}^n[\operatorname{count}(a,i)\ge 2]\\ &=\sum_a\prod_{i=1}^n1-[\operatorname{count}(a,i)\le 1]\\ &=\sum_a\prod_{i=1}^n1-[\operatorname{count}(a,i)=0]-[\operatorname{count}(a,i)=1] \end{aligned}$$

其中 $\operatorname{count(a,i)}$ 表示 $a$ 中第 $i$ 位的出现次数。

然后就是基本操作了。称 $\operatorname{count}(a,i)=0$ 为 $\mathcal{I}$ 类限制，$\operatorname{count}(a,i)=1$ 为 $\mathcal{II}$ 类限制。那么钦定 $i$ 个二进制位为 $\mathcal{I}$ 类限制，$j$ 个二进制位为 $\mathcal{II}$ 类限制。容斥系数为 $(-1)^{i+j}$。同时我们要钦定他们的位置，故还有 $\binom{n}{i,j}$ 的贡献。并且，由于 $n-i-j$ 个位置没有任何的限制，于是又有 $2^{2^{n-i-j}}$ 的贡献。

Part I. $\mathcal{I}$ 类限制

先看简单的 $\mathcal{I}$ 类限制。此时这些位置必须为 $0$，相当于强行抹去了这些位的存在。因此计数时只需要强行抹去这些位的存在就行。

Part II. $\mathcal{II}$ 类限制

这些限制相当于要求这 $j$ 个位置必须恰好被一个数覆盖。然后就不会了……

注意到，这件事情，其实相当于将 $j$ 个位置划分为若干个集合。为什么？例如当 $n=j=2$ 时，有这四种数：

$$00,01,10,11$$

一个 $11$ 的出现可以使得两个位置都被覆盖。反之如果 $11$ 不出现，则必须是 $01$ 和 $10$ 出现。换言之，一个二进制数 $K$ 的出现，相当于将其内部所有 $1$ 的位置划分为一个集合。而又因为所有的 $j$ 个位置都要被划分，因此这件事情其实相当于将 $j$ 个数划分为若干个集合。设划分为 $k$ 个集合，则有 $j\brace{k}$ 中划分方法。

然后由于还有 $2^{n-i-j}$ 个位置没有被分配，自由配置，所以实际上划分的 $k$ 个集合，每一个集合都可以自由选择 $2^{n-i-j}$ 中方案填充其他的没有限制的二进制位，于是总方案数还有 $(2^{n-i-j})^k$ 的贡献。

Part III. 整合答案

接下来就很简单了。

将上面的写下来：

$$\sum_{i,j}\binom{n}{i,j}(-1)^{i+j}2^{2^{n-i-j}}\sum_k{j\brace k}(2^{n-i-j})^k$$

直接计算可以做到 $\tilde{\mathcal{O}}(n^3)$ 。

类似的，由于 $i,j$ 很像，不妨令 $p=i+j$，那么原式为：

$$\sum_p\binom{n}{p}(-1)^p2^{2^{n-p}}\sum_k(2^{n-p})^k\sum_j {j\brace k}\binom{p}{j}$$

由于 $\sum\limits_{j}{j\brace k}\binom{p}{j}={p+1\brace k+1}$，于是：

$$\sum_p\binom{n}{p}(-1)^p2^{2^{n-p}}\sum_k(2^{n-p})^k{p+1\brace k+1}$$

复杂度 $\tilde{\mathcal{O}}(n^2)$，可以通过。