#P6678. [COCI2019-2020#2] Popcount

[COCI2019-2020#2] Popcount

题目背景

Miniature Algebraic Natural Relay 是小型可编程设备的最新技术进步。 您可以使用 MalnarScript 为此设备编写自己的程序。

题目描述

程序要求如下:

  • 程序的输入是一个严格小于 2n2^n 的单个非负整数。
  • 程序的输出是一个严格小于 2n2^n 的单个非负整数。
  • 使用 MalnarScript 进行编程时,您只能使用一个 nn 位无符号整数变量 aa。在程序的开头,此变量保存输入,并且其在程序末尾的值被视为程序的输出。
  • MalnarScript 的源代码最多必须包含 kk 个格式为 a = <expr>\texttt{a = <expr>} 的命令,这些命令按顺序执行,并且每个命令最多包含 10310^3 个字符。

符号 <expr>\texttt{<expr>} 的递归定义如下:

$$\texttt{ = A | | ()} $$

换句话说,符号 <expr>\texttt{<expr>} 可以是变量 aa ,也可以符合符号 <num>\texttt{<num>} 的定义,或者在括号内表示二元表达式,其中每个操作数均符合相同的 <expr>\texttt{<expr>} 定义。

上面定义中的符号 <num>\texttt{<num>} 表示严格小于 2n2^n 的非负十进制整数。而符号 <operator>\texttt{<operator>} 可以是 +\texttt{+}-\texttt{-}|\texttt{|}&\texttt{\&}<<\texttt{<<}>>\texttt{>>},分别表示:加,减,按位或,按位与,左移和右移的运算。

此外,字符 aa<expr>\texttt{<expr>} 符号中最多出现 55 次。

在执行加减运算时出现溢出或下溢时,MalnarScript 将以 2n2^n 为模执行这些运算。例如,当 n=3n = 3 时,在 MalnarScript 中,7+3=27 + 3 = 225=52 - 5 = 5

每个命令中方程式的右侧求和为一个数字,然后将其存储到 aa 中。为了计算右侧表达式,MalnarScript 首先将每次出现的 aa 替换为其当前值。 然后,像在任何数学表达式中一样进行表达式的计算,即,括号优先。请注意,运算符的优先级(按照运算顺序)是不相关的,因为最终结果完全由括号的位置定义。

您的任务是编写一个程序,该程序在 MalnarScript 中输出程序,该程序以输入值的二进制表示形式计算一个数。

输入格式

第一行,两个正整数 n,kn, k,含义见 题目描述

输出格式

第一行中,您应该输出产生的 MalnarScript 程序的命令数。

在其余各行中,您应该输出所需程序的命令。每个命令必须在单独的行中输出,并且必须满足任务描述中所述的 MalnarScript 语法。

重要的是,输出中不要有不必要的空行或多余的空格字符。 每行(包括最后一行)必须以换行(\n)结尾。

2 2

1
A=(A-((A&2)>>1))

3 5

2
A=((A&4)|((A&3)-((A&2)>>1)))
A=((A&3)+((A&4)>>2))

提示

数据范围及约定

Subtask 分数 数据范围及约定
11 1515 2n1002 \le n \le 100k=n  1k = n \ − \ 1
22 n=500n = 500k=128k = 128
33 3535 1n401 \le n \le 40k=7k = 7
44 4545 100n500100 \le n \le 500k=10k = 10

说明

本题分值按 COCI 原题设置,满分 110110

题目译自 COCI2019-2020 CONTEST #2 T4 Popcount

感谢

https://www.luogu.com.cn/user/764746
SPJ,SPJ 可以在题目附件处下载。

另外,由于 testlib 库在洛谷环境下生成随机数在 N=31N=31 时有问题,采用固定已生成随机数。部分测试点 NN 较大,Special Judge 程序运行较久,如下。

特殊测试点编号 时限
15 3s
39 2s
40 3s
48

上述测试点时限仅用于 Special Judge 程序使用。