#P12479. [2025年福建省队集训]Diana 的梦境

    ID: 11642 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-矩阵转置坐标变换布尔电路构造异或抵消

[2025年福建省队集训]Diana 的梦境

题目描述

给定一个 n×nn\times n 的布尔矩阵 BB,你需要构造一串指令,对任意初始矩阵 BB 都能完成转置。所有下标从 00 开始。

可以使用 105+110^5+1 个长度为 nn 的布尔数组 A0,…,A105A_0,\ldots,A_{10^5}。最初,A0,…,An−1A_0,\ldots,A_{n-1} 依次等于 BB 的各行,其余数组全为 00。

允许使用以下操作。每条指令按执行前的值计算右侧结果。

指令 效果 参数限制
AND x y z AxA_x 赋值为 AyA_y 和 AzA_z 按位与的结果 0≤x,y,z≤1050\le x,y,z\le10^5
OR x y z AxA_x 赋值为 AyA_y 和 AzA_z 按位或的结果
XOR x y z AxA_x 赋值为 AyA_y 和 AzA_z 按位异或的结果
SH x y z AxA_x 赋值为 AyA_y 循环左移 zz 位,具体为 Ax,i=Ay,(i−z) mod nA_{x,i}=A_{y,(i-z)\bmod n} 0≤x,y≤1050\le x,y\le10^5,0≤z<n0\le z<n
SET x y z 将 Ax,yA_{x,y} 赋值为 zz 0≤x≤1050\le x\le10^5,0≤y<n0\le y<n,z∈{0,1}z\in\{0,1\}

执行完所有指令后,必须对任意矩阵 BB 及任意 0≤i,j<n0\le i,j<n 满足 Ai,j=Bj,iA_{i,j}=B_{j,i}。操作次数越少,可能取得的分数越高。

输入格式

一行一个整数 nn,表示矩阵的大小。初始矩阵的值不会提供给选手程序。

输出格式

第一行输出一个整数 mm,表示指令数,0≤m≤2×1050\le m\le2\times10^5。

接下来 mm 行,每行按题面格式输出一条指令。

样例

1
0

当 n=1n=1 时,矩阵已经等于自身的转置。

数据范围与原赛计分

原赛四个测试点的 nn 分别是 2,32,512,20482,32,512,2048,分值分别为 10,15,15,6010,15,15,60。前 3 个测试点中,合法输出即可获得该点满分。

第 4 个测试点中,合法输出的原赛得分为

$$\left\lfloor 30\log_{10}\left(\frac{5\times10^5}{\max(m,52000)-47000}\right)\right\rfloor.$$

原题描述 · 原输出说明 · 原计分说明