#P12479. [2025年福建省队集训]Diana 的梦境
[2025年福建省队集训]Diana 的梦境
题目描述
给定一个 的布尔矩阵 ,你需要构造一串指令,对任意初始矩阵 都能完成转置。所有下标从 开始。
可以使用 个长度为 的布尔数组 。最初, 依次等于 的各行,其余数组全为 。
允许使用以下操作。每条指令按执行前的值计算右侧结果。
| 指令 | 效果 | 参数限制 |
|---|---|---|
AND x y z |
赋值为 和 按位与的结果 | |
OR x y z |
赋值为 和 按位或的结果 | |
XOR x y z |
赋值为 和 按位异或的结果 | |
SH x y z |
赋值为 循环左移 位,具体为 | , |
SET x y z |
将 赋值为 | ,, |
执行完所有指令后,必须对任意矩阵 及任意 满足 。操作次数越少,可能取得的分数越高。
输入格式
一行一个整数 ,表示矩阵的大小。初始矩阵的值不会提供给选手程序。
输出格式
第一行输出一个整数 ,表示指令数,。
接下来 行,每行按题面格式输出一条指令。
样例
1
0
当 时,矩阵已经等于自身的转置。
数据范围与原赛计分
原赛四个测试点的 分别是 ,分值分别为 。前 3 个测试点中,合法输出即可获得该点满分。
第 4 个测试点中,合法输出的原赛得分为
$$\left\lfloor 30\log_{10}\left(\frac{5\times10^5}{\max(m,52000)-47000}\right)\right\rfloor.$$