自动搬运

查看原文

来自洛谷，原作者为

	zhoukangyang ^w^/

搬运于2025-08-24 22:32:40，当前版本为作者最后更新于2021-07-30 09:18:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

场上题目看错两次，day2 成功爆炸 /ll

验体读阅的好更

本文下标从 1 开始

算法 1

我会容斥！

先把问题转化成统计不存在一个合法位置的方案数。

接着统计有钦定 $k$ 个合法的，其他随便的方案数。其容斥系数为 $(-1)^k$。

在一次机器人的操作后，所有输入的数在经过机器人在操作后的输出都可以表示成 $0$，$1$，$x$ 或 $1-x$ 的形式（$x$ 是这个位置上输入的数）

考虑一个纸带：对于一个被钦定的每一个位置，要求输入经过这个机器人操作之后一定等于输出。仍然把输出表示成输入的形式，只不过这个输出可以以多种方式被输入表达。

对于每一个位置分类讨论：

1. 如果这个位置上表示成的结果 既有 0 又有 1 或 既有 x 又有 1-x：输入输出都为空。方案数为 $1$。
2. 如果不满足条件 $1$，这个位置上表示成的结果 有 0 或 1 且 有 x 或 1-x：输入输出都为空，否则输入输出就被固定了。方案数为 $2$。
3. 条件 1，2 都不满足：对于每一个输入都对应一个唯一的输出，方案数为 $3$。

这个纸带上每一个位置就是独立的了，最后把每个位置的答案乘起来即可。

注意机器人爆炸的情况。

时间复杂度 $\Theta(n^22^nm)$，期望得分 $20$。

code

算法 2

我会优化算法1！

对于第 $i$ 个机器人，考虑实际进行修改了的位置只有 R 的个数个（设为 $c_i$）。

考虑枚举最后一个钦定的位置在哪里（设为 $r$）。这样就可以知道哪些机器人是爆炸的了：有且仅有 $c_i > n - r$ 的爆炸了。

然后对于前 $r$ 个位置 $\rm DP$。状压记录前面的元素中哪些元素被钦定了。钦定了一个位置就给答案乘上 $-1$。在 $\rm DP$ 的过程中，做到第 $i$ 个数就把第 $i$ 个位置的贡献（即输入输出方案数）统计掉。

但我们发现并不是所有元素都需要记录下来的：只用记录与当前位置距离不超过 $n - r$ 的和与当前位置距离超过 $n-r$ 的位置中有没有 $1$ 即可。

最后再处理一下位置超过 $r$ 的元素即可。

时间复杂度 $\Theta(n^2m2^{n/2})$，期望得分 $48$。

code

算法 3

我会 bitset！

发现我们统计一个位置的贡献的时候，只有 是否有... 有用。所以考虑用 $\rm bitset$ 同时处理一堆纸条是否有 0，1，x 和 1-x。

这样复杂度就降到了 $\Theta(\frac{n^2m2^{n/2}}{\omega})$，常数巨大。但是还可以优化。

其实我们要求的是类似于一个子集中的 $\rm bitset$ 的子集并，这个东西仍然可以优化，就是类似于 f[x] = f[x & -x] | f[x ^ (x & -x)]。

时间复杂度 $\Theta(\frac{nm2^{n/2}}{\omega})$，期望得分 $100$。

code

感觉讲的有些抽象，不过相信大家想到算法2 之后就会做了。

祝大家学习愉快！