{"problem":{"name":"[CTS2024] 多方计算","description":{"content":"**这是一道交互题。** 有 $n+1$ 个人，由 $0$ 至 $n$ 编号。第 $i(0 \\le i \\le n-1)$ 个人有一个 $[0,2^m-1]$ 之间的整数 $a_i$。 编号为 $n$ 的人希望知道 $a_0+a_1+\\cdots+a_{n-1}$ 的值。为此，他们可以进行如下通讯： 1. 首先，选定通讯的秒数 $N$。 2. 接下来的 $N$ 秒中的每一秒，所有 $i(0 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10213"},"statements":[{"statement_type":"Markdown","content":"**这是一道交互题。**\n\n有 $n+1$ 个人，由 $0$ 至 $n$ 编号。第 $i(0 \\le i \\le n-1)$ 个人有一个 $[0,2^m-1]$ 之间的整数 $a_i$。\n\n编号为 $n$ 的人希望知道 $a_0+a_1+\\cdots+a_{n-1}$ 的值。为此，他们可以进行如下通讯：\n\n1. 首先，选定通讯的秒数 $N$。\n2. 接下来的 $N$ 秒中的每一秒，所有 $i(0 \\le i \\le n-1)$ **同时**向 $(i+1)$ 发送一个比特的信息。\n\n  - 该消息会在下一秒开始前收到。特别地，最后一秒发出的信息不会被收到。\n  - 除此之外，不允许任何其他形式的通讯。\n\n你需要用尽可能少的通讯秒数完成这个任务。\n\n## 实现细节\n\n请确保你的程序开头有 `#include \"mpc.h\"`。\n\n你不需要也不应该实现主函数。你需要实现以下两个函数：\n\n```cpp\nint precalc(int n, int m);\n```\n\n- `n` 表示人数，`m` 表示整数的值域。\n- 你需要返回通讯的秒数 $N$。\n\n```cpp\nbool transmit(player &player, int round, int position);\n```\n\n- `round` 表示目前通讯的秒数，其取值为 $[1,N]$ 中的整数；\n- `position` 表示当前传递信息的人的编号，其取值为 $[0,n]$ 中的整数；\n- `player` 为一个结构体类型，描述了当前传递信息的人。该结构体实现在 `mpc.h` 中。其包含以下两个成员变量：\n  - 布尔类型变量 `last_message`，表示上一秒上一个人传递的信息。若 `position` 为 $0$ 或 `round` 为 $1$，则 `last_message` 的值一定为 $0$；\n  - 长度为 $4096$ 的整型数组 `memory`，描述当前传递信息的人的“记忆”。\n    - 在 `transmit` 函数中，这个数组可以被任意修改。\n    - `player.memory` 只可能在 `transmit` 函数中被修改。若 `transmit` 函数中不对 `player.memory` 进行修改，则同一个人多次传递信息时，`player.memory` 都存储相同的值。\n    - `player.memory` 的初始值按照以下规则设定：\n      - `position` 不为 $n$ 时，`memory` 的 $0$ 到 $m-1$ 位取值为 $\\{0,1\\}$，从低位到高位描述 $a_{\\text{position}}$ 的二进制表示（即第 $i$ 位对应位权 $2^i$ 的位），而其余位置为 $0$；\n      - 否则，该数组的所有位置均为 $0$。\n- 你需要返回这个人在这一秒传递给下一个人的信息。\n  - 当 `position` 为 $n$ 时或 `round` 为 $N$ 时，该返回值不会产生任何影响。\n\n在所有 `transmit` 调用结束后，你需要保证编号为 $n$ 的人的 `player.memory` 中前 $2200$ 位取值均属于 $\\{0,1\\}$，且对应的二进制数是所有 $a_i$ 的和。\n\n在满足题目条件和数据范围的情况下，交互库至多消耗 $0.15$ 秒的时间以及 $128\\text{MiB}$ 的空间。\n\n**在程序中使用其他形式的通讯，包括但不限于使用全局变量，会被视为攻击交互库。**\n\n## 测试程序方式\n\n试题目录下提供了一个交互库的参考实现 `grader.cpp`。最终测试时所用的交互库实现与该实现有不同，因此选手的解法不应依赖交互库的具体实现。\n\n你需要在本题目录下使用以下编译命令得到可执行程序：\n\n`g++ mpc.cpp grader.cpp -o mpc -O2 -std=c++17 -lm`\n\n可执行文件将从标准输入读入以下格式的数据：\n\n- 第一行两个整数 $n, m$，\n- 接下来 $n$ 行每行 $m$ 个 `01` 整数，从低到高表示每个人的整数的二进制表示，每行的两个整数之间用一个空格分隔。\n\n读入完成后，交互库会先调用一次 `init(n,m)` 函数得到 $N$，然后进行 $\\max(0,N)$ 轮调用，第 $k(1 \\le k \\le \\max(0,N))$ 轮调用会调用所有 $\\text{round}=k$ 的 `transmit` 函数，并在调用完之后更新相应的 `player.last_message` 的值。\n\n- 若 $N \\le 0$，则不会进行任何调用，所有 `player.memory` 为其初始值。\n\n若你的程序正确运行，可执行文件会输出以下格式的数据：\n\n- 第一行一个长度为 $2200$ 的字符串，表示所有 $a_i$ 的和，按二进制从低位到高位输出。\n- 第二行一个字符串，依次输出所有交互完毕后编号为 $n$ 的人的 `player.memory` 中前 $2200$ 个位置表示的数，**相邻两个数之间没有空格**。\n- 第三行，如果上述两个字符串不同，那么会告知你答案错误；不然，会输出你在这组数据上的得分。\n\n本题目录中同时下发了样例 `1.in`，`1.ans` 以及一个样例程序 `mpc.cpp`。该样例程序可以通过下发的样例。\n\n## Background\n\n## 滥用本题评测将被封号\n\n**特别注意**：为了能够正常评测，请删去代码开头的 `#include \"mpc.h\"` 并加入以下代码段：\n\n```cpp\n#include <array>\nstruct player{\n    bool last_message;\n    std::array<int, 4096> memory;\n};\nint precalc(int n, int m);\nbool transmit(player &player, int round, int position);\n```\n\n[samples]\n\n## Note\n\n## 子任务\n\n对于所有测试数据，$1 \\le n,m \\le 2000$。\n\n本题共有 10 个子任务，每个子任务 10 分。\n\n| 子任务编号 |  1   |  2   |  3   |  4   |  5   |  6   |  7   |  8   |  9   |  10  |\n| :--------: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: |\n|   $n =$    |  5   | 1000 | 1000 | 1000 |  3   |  10  | 500  | 1000 | 1500 | 2000 |\n|   $m =$    |  5   |  1   |  10  |  30  | 1000 | 1000 | 1000 | 1000 | 1500 | 2000 |\n\n## 评分方式\n\n本题首先会受到和传统题相同的限制，例如编译错误会导致整道题目得 0 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 0 分等。\n\n在上述条件以外，在一个测试点中，若 $N > n+m+100$，或者在所有的 `transmit` 调用结束后编号为 $n$ 的人的 `player.memory` 中前 $2200$ 位对应的二进制数不是所有 $a_i$ 的和，你会获得 $0$ 分。否则，根据 $(N - n - m)$ 的值，你在该测试点的分数按照以下表格计算：\n\n| $(N - n - m) \\in$ | $[14,100]$ | $[12, 13]$ | $[9, 11]$ | $[6,8]$ | $[5,5]$ | $[4,4]$ | $(-\\infty, 3]$ |\n| :---------------: | :--------: | :--------: | :-------: | :-----: | :-----: | :-----: | :------------: |\n|       分数        |     1      |     2      |     3     |    4    |    6    |    8    |       10       |\n\n你在一个子任务中的分数为该子任务中所有测试点的分数的最小值。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10213","tags":["2024","交互题","Special Judge","CTSC/CTS"],"sample_group":[],"created_at":"2026-03-03 11:09:25"}}