题目链接 (Qoj)

Anna 与 Bruno 通信。

Anna 有一个大小为 的数组 和一个希望使 Bruno 知道的数 。数组只能存放 或 。

数组有 个位置损坏，即 Anna 无论向这个位置存放什么，Bruno 收到时都只能看到 。

交互细节：

作为 Anna，你需要包含 Annalib.h，并实现函数 void Anna(int N, long long X, int K, int P[])；你使用函数 void Set(int pos, int bit) 操作数组。注意，你必须为数组的每个位置指定存储内容，即使你知道这个位置损坏。

作为 Bruno，你需要包含 Bruno.h，并实现函数 long long Bruno(int N, int A[])。

原题保证 。

---

Algo 1

考虑相邻两位数组表示一个三进制位：

• 如果可行，使用
  1. 表示 ；
  2. 表示 ；
  3. 表示 ；
• 若不可行，则令两位均为 ，表示这两位没有有效信息；

最劣情况下，我们可以表示的值域为 。

不妨将数组随机打乱，这样我们可以假定每一位损坏的概率是均匀的，为 。

同样，我们可以对 三进制表示下每一位分别作随机映射，因此 也可以视为随机的。

因此对于数组的相邻两位，可以成功表示出三进制的一位的概率为

在本题数据中，，因此期望意义下有超过 个位可用，而我们实际上只需要 位，看起来基本够用了。

当然，我们也可以计算无法表示的概率，这个值可以估计为

代入计算一下发现不超过 。

Algo 2

有一个保证正确的很聪明的做法。

考虑使用数组的 个连续位置为单位存储信息。

我们建立这样的表示关系：

容易说明，对于 个位置均完好的单元，至少可以表示 个二进制位；对于存在一个位置损坏的单元，至少可以表示 个二进制位。

具体来说，对于一个位置损坏的单元

• 希望表示 ：
  • 若第一个位置损坏，则使用 表示；
  • 若后两个位置损坏，使用 表示；
• 希望表示 ：
  • 若中间位置未损坏，使用 ；
  • 若中间位置损坏，使用 或 ，此时可以额外表示下一位。

显然最劣情况会有 个完全损坏的单元或 个损坏一位的单元，又因为总共有 个单元，因此总可以表示 位。