#1907. Bulbel

    ID: 1907 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1962来源:qoj.ac数据:公开样例

Bulbel

Bulbel

题目描述

标题: Bulbel - Problem - QOJ.ac

#10305. Bulbel

Statistics

我们定义一个 bitset 是一个 w 位 01 串。定义一个 w×w 的 01 矩阵 M 的 bitset 表示为一个长度为 w 的 bitset 序列 b1,…,bw,其中 bi 是将 M 的第 i 行看作一个 01 串对应的 bitset,其中第 j 列的元素位于 bitset 的第 j 位。

有一个 w×w 矩阵 M 的 bitset 表示,存储在 b1,…,bw(但你不能直接访问它们的值),你需要求出其转置 MT 的 bitset 表示,最终存储在 b1,…,bw 中。你总共可以调用 b1,…,b105 这 105 个 bitset,其中 bw+1,…,b105 初始全零。你可以进行以下操作:

  • AS x y:令 bx←by。
  • AND x y z:令 bx←by∧bz,其中 ∧ 为按位与。
  • OR x y z:令 bx←by∨bz,其中 ∨ 为按位或。
  • XOR x y z:令 bx←by⊕bz,其中 ⊕ 为按位异或。
  • SET x y a v:令 bx 成为将 by 的第 a 位(a∈[0,w))修改为 v(v∈{0,1})后的结果(不改变 by)。
  • SH x y a:令 bx 成为将 by 左移 a 位(a∈(−w,w))后的结果(不改变 by,若 a<0 则为右移 −a 位,多出来的位补 0)。
  • SUB x s y:令 bx←bs+by,其中把 by 视作一个二进制数,要求 −105≤s≤105, 1≤s+by≤105。

你的得分与你的操作次数有关,详见评分标准。

输入格式

从标准输入读入数据。

第一行:一个整数 w。

输出格式

输出到标准输出。

第一行:一个整数 m,表示你的操作次数。

接下来 m 行:每行表示一个操作。操作将按照输出顺序执行。

样例

输入

2

输出

10
SET 3 3 0 1
SET 4 4 1 1
AND 5 1 3
AND 6 1 4
AND 7 2 3
AND 8 2 4
SH 9 6 -1
SH 10 7 1
OR 1 5 10
OR 2 8 9

子任务

Subtask 1(5%):w=2。

Subtask 2(10%):w=128。

Subtask 3(36%):w=256。

Subtask 4(49%):w=1024。

评分方式

令 m 为你的操作次数。

你在某个测试点上的得分为:若你的输出错误,得分为 0,否则得分为 f(m)。你在一个子任务上的得分为在其中所有测试点上得分的最小值。

对于 Subtask 1,f(m)=[m≤105]×5。

对于 Subtask 2,f(m)=[m≤105]×10。

对于 Subtask 3,f(m)={0(m>262144)83(4−m65536)2(65536<m≤262144)36−643(m65536−14)2(16384<m≤65536)36(m≤16384)。

  • 它是个连续函数。作为参考,当 f(65536)=24。

对于 Subtask 4,f(m)={0(m>80000)34000(80000−m)(40000<m≤80000)48−92282(m−35436)(35435<m≤40000)49(m≤35435)。

  • 它在 (35435,+∞) 上是个连续函数。作为参考,当 f(40000)=30, f(35436)=48。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2
10
SET 3 3 0 1
SET 4 4 1 1
AND 5 1 3
AND 6 1 4
AND 7 2 3
AND 8 2 4
SH 9 6 -1
SH 10 7 1
OR 1 5 10
OR 2 8 9