面国超算 - 题目

面皇有 $n$ 台电脑，这 $n$ 台电脑两两之间都用了特殊的缆线连接，它们的编号是 $0 \cdots n-1$。

现在有两个 $n \times n$ 的元素都是 $32$ 位无符号整数的矩阵 $A[0\cdots n-1, 0\cdots n-1]$，$B[0\cdots n-1, 0\cdots n-1]$。你需要用这些电脑来计算矩阵 $C=AB$。你只需要计算 $C$ 中每个元素对 $2^{32}$ 取模的结果。

一开始第 $i$ 台电脑只知道 $A$ 的第 $i$ 行的值和 $B$ 的第 $i$ 行的值，你需要让他们进行一些计算，使得最终第 $i$ 台电脑知道 $C$ 的第 $i$ 行的值。你需要让这些电脑进行通信来完成计算。

通信是分轮次进行的。具体来说，每一轮开始的时候，对于每个 $i$，第 $i$ 台电脑会根据已知的信息决策出一个数组 $\{\mathrm{sendTo}_{i,j}, 0 \leq j < n\}$，表示本轮第 $i$ 台电脑将给第 $j$ 台电脑发送什么信息。当所有电脑都完成决策后，所有 $\mathrm{sendTo}_{i,j}$ 都会瞬间传送到他的目标电脑上。在传输完成以后，这 $n$ 台电脑就会进入下一轮通信。（注意：和试机赛题目不同的是，这里同一台电脑发送给其他电脑的信息不一定要相同）。

由于缆线十分特殊，带宽相当有限（其实是因为面黄拨的经费太少）。因此，每轮通信中，$\mathrm{snedTo}_{i,j}$ 只能传输 $32$ 个二进制位。也就是说，$\mathrm{sendTo}_{i,j}$ 必须是 $0$ 至 $2^{32}-1$ 内的一个 $32$ 位无符号整数。

同时，每台电脑的磁盘大小也十分有限（也是因为经费太少），里面只能存储 $4 \times 10^{4}$ 个 $32$ 位二进制数。

现在你需要设计一个合理的算法，使得在尽量少的轮数内（经费太少不够付电费），每台电脑能计算出自己要计算的东西。

以上是题目北京，由于评测系统的限制，我们将通过一些手段来模拟通信的过程。下面将介绍模拟的方法。

在本题中，你需要实现函数

void node_mul(int maxSize, int node_id, int round_id);

其中 node_id 表示当前电脑的编号，round_id 表示当前是第几轮通信，通信的轮数从 $1$ 开始计数。

接下来我们用 uint 表示 $32$ 位无符号整数。

我们设置了一个全局变量 CO，你的代码需要和它交互来完成计算。

CO 记录了整个通信过程中的传输的信息，每台电脑初始得到的信息和每台电脑的存储系统。我们将第 $i$ 台电脑中存储的 $4 \times 10^4$ 个 $32$ 位二进制数组织成一个数组 uint F[i][40000] 供我们存取。

CO 有下面这些方法可以调用：

```
uint getMemory(int w)
```
- 返回 F[node_id][w]。
```
void updateMemory(int w, uint val)
```
- 将 F[node_id][w] 修改为 val。
```
uint getinfoA(int w)
```
- 返回 A[node_id][w]。
```
uint getinfoB(int w)
```
- 返回 B[node_id][w]。
```
uint getinfoT(int k, int w)
```
- 获取当前电脑在第 $k$ 轮种收到的来自第 $w$ 台电脑的消息，要求 $1 \leq k < \mathrm{round_id}$。
```
void updateC(int w, uint val)
```
- 提交 val 作为 C[node_id][w] 的答案，你可以多次提交，只会采用最后一次。
```
void getinfoC(int w)
```
- 返回你提交过的 C[node_id][w]，如果你没有提交过，则返回 $0$。
```
void sendinfoTo(int k, uint w)
```
- 在本轮通信中，这台电脑要发送 $w$ 给第 $k$ 台电脑，你可以在同一轮同一台电脑上多次调用该函数发送给同一台电脑，但是我们只采用最后一次。

例如你在 node_mul(5, 2, 2) 中先后调用了：

CO.sendinfoTo(1, 2);
CO.sendinfoTo(1, 3);

则我们视为你向电脑 $1$ 发送了信息 $3$。

下面介绍我们的模拟方法。

我们会先枚举 $i=1\cdots 130$，表示当前通信的轮数，接着在循环体内部枚举 $j=0\cdots n-1$，调用 node_mul(matSize, j, i)，之后检查是否所有的电脑已经提交了正确的答案，即是否对所有 $x$，第 $x$ 台电脑已经知道了 $C$ 中第 $x$ 行的所有元素。如果是的话，结束测试，我们认为这些电脑用了 $i$ 轮完成了计算。若 $130$ 轮通信结束后，仍然存在一台电脑没有计算出自己应该计算的东西，则被视为使用了 $131$ 轮通信完成了计算。

以下是一些代码规范和注意事项。

在函数 node_mul 中，任何非法传递信息的行为，即不通过题目中给定的方法来传递信息的行为，都会被认为是作弊，它们包括但不限于：开全局变量；内嵌汇编代码；使用 malloc，calloc 等函数开辟内存，通过 new 指针来共享内存；将数据写到本地磁盘上等。

同时，你不允许调用除了 CO 的方法以外的任何函数，不能定义任何全局变量，包括静态全局变量。

除此以外，如果你在调用 CO 的方法的时候传入的参数不合法（比如 getMemory(-1)，sendinfoTo(114514, 35)），那么模拟器会陷入死循环并使你的代码超时。

另外，由于我们使用的是代码填空机制，你只能在代码空格处填写上 node_mul 函数的实现，不能有违规操作，包括但不限于：将 node_mul 函数提前结束并声明其他函数等。

最后，某些企图修改内存的行为也是不合法的，你不能够修稿我们定义的每一个全局变量的值，比如修改 CO 类型体里面每一个变量的值。

我们会人工检查你的代码是否使用了违规的行为，如果我们认为你的代码有违规行为（包括但不仅限于以上提到的行为），那么我们会拒绝你的提交，把你本次的提交的分数变成 $0$ 分并通知你。由于人工检查有一定延迟，请尽量避免比赛结束前几分钟提交一些危险代码，不然可能会导致比赛结束后才知道提交被拒绝。

但是，你可以在函数体内声明一些局部变量和数组来帮助你完成计算。

你可以查看我们下发的 see.cpp 来了解其他细节，但是 see.cpp 并不是我们最后测试用的代码，最后测试用的代码将会进行一些加密。最后测试时，我们将会把你的代码填进 see.cpp，然后运行，如果 see.cpp 运行超过了 $50$ 秒，则你本题算超时。

提交时请提交函数体内的代码，假如你补全成了 void node_mul(int matSize, int node_id, int round_id){int yjq;}，提交时应该只提交 “ int yjq; ”。

注意，在本地测试 see.cpp 时，你需要将栈大小开大。

数据规模与约定

本题只有一个测试点 $n = 125$。

假设你花 $x$ 轮完成了计算，那么你最后得到的分数是

$$f(x) = \begin{cases} 0 & x \geq 126 \\ 100 & x \leq 34 \\ \max\left(20, \min\left(100, \left( 100, \left\lfloor60 + 10 \times \ln\left(\frac{y}{1-y}\right)\right\rfloor \right)\right)\right) & \text{否则}\end{cases}$$

其中 $y=\displaystyle \frac{80-x}{92}+0.5$，这个除法没有取整。

QOJ.ac

QOJ

# 5366. 面国超算

数据规模与约定