P6678 [COCI 2019/2020 #2] Popcount

Miniature Algebraic Natural Relay is the latest technical progress in small programmable devices. You can write your own programs for this device using MalnarScript.

The program requirements are as follows: - The input of the program is a single non-negative integer strictly less than $2^n$. - The output of the program is a single non-negative integer strictly less than $2^n$. - When programming in MalnarScript, you may only use one $n$-bit unsigned integer variable $a$. At the beginning of the program, this variable stores the input, and the value of it at the end of the program is regarded as the output of the program. - The MalnarScript source code may contain at most $k$ commands of the form $\texttt{a = }$, executed in order, and each command may contain at most $10^3$ characters. The recursive definition of the symbol $\texttt{}$ is as follows: $$\texttt{ = A | | ()}$$ In other words, the symbol $\texttt{}$ can be the variable $a$, or a value that matches the definition of $\texttt{}$, or a binary expression in parentheses, where each operand also matches the same definition of $\texttt{}$. In the definition above, the symbol $\texttt{}$ denotes a non-negative decimal integer strictly less than $2^n$. The symbol $\texttt{}$ can be $\texttt{+}$, $\texttt{-}$, $\texttt{|}$, $\texttt{\&}$, $\texttt{}$, which represent addition, subtraction, bitwise OR, bitwise AND, left shift, and right shift, respectively. In addition, the character $a$ may appear at most $5$ times in $\texttt{}$. If overflow or underflow occurs during addition or subtraction, MalnarScript performs these operations modulo $2^n$. For example, when $n = 3$, in MalnarScript, $7 + 3 = 2$, and $2 - 5 = 5$. For each command, the expression on the right-hand side is evaluated to a number, and then stored into $a$. To compute the right-hand-side expression, MalnarScript first replaces every occurrence of $a$ with its current value. Then it evaluates the expression like in any mathematical expression, i.e. parentheses first. Note that operator precedence (the order among operators) is irrelevant, because the final result is fully determined by the placement of parentheses. Your task is to write a program in MalnarScript that computes the popcount of the binary representation of the input value.

The first line contains two positive integers $n, k$, with the meanings described in **Description**.

In the first line, you should output the number of commands in the produced MalnarScript program. In the remaining lines, you should output the commands of the required program. Each command must be output on its own line and must satisfy the MalnarScript syntax described in the task statement. It is important that there are no unnecessary blank lines or extra space characters in the output. Each line (including the last line) must end with a newline (`\n`).

#### Constraints and Notes | Subtask | Score | Constraints and Notes | | :-----------: | :-----------: | :-----------: | | $1$ | $15$ | $2 \le n \le 100$, $k = n \ − \ 1$ | | $2$ | $15$ | $n = 500$, $k = 128$ | | $3$ | $35$ | $1 \le n \le 40$, $k = 7$ | | $4$ | $45$ | $100 \le n \le 500$, $k = 10$ | #### Notes **The scoring of this problem follows the original COCI problem, with full score $110$.** **Translated from [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #2](https://hsin.hr/coci/archive/2019_2020/contest2_tasks.pdf) *T4 Popcount*.** Thanks to @[Sprague_Garundy](https://www.luogu.com.cn/user/764746) for providing the SPJ, which can be downloaded from the attachments of the problem. In addition, because the `testlib` library has an issue when generating random numbers in the Luogu environment for $N = 31$, fixed pre-generated random numbers are used instead. For some test points with large $N$, the Special Judge program runs for a longer time, as follows. | Special Test Point ID | Time Limit | |:-:|:-:| | 15 | 3s | | 39 | 2s | | 40 | 3s | | 48 | 3s | The time limits above are only for the Special Judge program. Translated by ChatGPT 5