翻译不够人道
查看原帖
翻译不够人道
516831
Leo_LeLe楼主2021/12/18 10:55

这个题的翻译省略了一个关键的矩阵FF

然后就没了

给定一个整数 kk 和一个网格 2k×2k2^k \times 2^k

在其单元格中写入一些数字,单元格 (i,j)(i,j) 最初包含数字 aija_{ij}网格被认为是一个环面,

(i,2k)(i, 2^k)(i,1)(i,1)(2k,i)(2^k, i)下方的单元格是 (1,i)(1,i)

也给定了一个格图 FF ,由tt 个单元组成,其中 tt 是奇数。

FF 不必连接。

我们可以执行以下操作:将 FF 放置在网格上的某个位置。(只允许平移,禁止旋转和反射)。

现在选择任何非负整数 xx 。之后,对于每个被 FF 覆盖的单元格 (i, j)(i,j) ,替换 aija_{ij}aijx{a_{ij}} \oplus {x}

其中 \oplus 表示按位异或运算。

更正式地说,让 F 由单元格 (x1,y1),(x2,y2),,(xt,yt)(x_1, y_1), (x_2, y_2), \dots, (x_t, y_t)

然后你可以做如下操作:

选择任意一个 x,yx, y1x,y2k1\leq x, y \leq 2^k ,任何非负整数 xx ,并且对于从 1 到 nn 的每个 ii 替换单元格中的数字

(((x+xi1)mod2k)+1,((y+yi1)mod2k)+1)(((x + x_i - 1)\bmod 2^k) + 1, ((y + y_i - 1)\bmod 2^k) + 1)

a((x+xi1)mod2k)+1,((y+yi1)mod2k)+1xa_{((x + x_i - 1)\bmod 2^k) + 1, ((y + y_i - 1)\bmod 2^k) + 1}\oplus x

我们的目标是使所有数字都等于 0 。

我们能做到吗?如果可以,请找到可以执行此操作的最少操作数。

2021/12/18 10:55
加载中...