菜王的 blog

显然如果 $x$ 能到达 $y$ 一定有 $y \subseteq x$，则我们只需要关心 $x - y$ 的值 $z$。

然后对于一个 $z$，方案数显然是 $\operatorname{popc}(z)!$，因为每次走一条边相当于把 $z$ 中的某一位 $1 \to 0$。

现在只需要计算对于一个 $z$，可以得到这个 $z$ 的 $(x, y)$ 对的数量，显然是 $2^{n - \operatorname{popc}(z)}$，因为对于某一位，如果 $x, y$ 在这一位上相同，可以都填 $0 / 1$。

于是我们考虑枚举 $\operatorname{popc}(z)$，则对应的 $z$ 就有 $\binom n{\operatorname{popc}(z)}$ 种。整合一下得到式子：

$ans(n) = \sum_{k = 0}^n \binom nk k! 2^{n - k}$

可以 $O(n)$ 单次计算。把二项式展开可以得到：

$\begin{aligned} ans(n) &= \sum_{k = 0}^n \frac{n!}{(n - k)!k!} k!2^{n - k}\\ &= \sum_{k = 0}^n \frac{n!}{(n - k)!} 2^{n - k}\\ &= n! \sum_{k = 0}^n \frac{2^{n - k}}{(n - k)!} \\ &= n! \sum_{k = 0}^n \frac{2^k}{k!}\\ \end{aligned}$

预处理前缀和即可，可以做到 $O(n + T)$。

去掉 $x = y$ 以及 $y = 0$ 的贡献是简单的，这里不再赘述。