UOJ69 新年的QAQ 题解

题意：

春节期间， cxy 订购了一台高端电脑。结果买回来一看，果然高端：每秒能进行 $10^{20}$ 次计算，从此腰也不酸了腿也不疼了。

在这台电脑上有一种编程语言名叫 QAQ，它的代码由 $N$ 行组成，这台电脑会从第 $1$ 行开始，从上到下依次执行。

这种编程语言有 $26$ 个 32 位整数型变量，分别叫做 $a, \dots, z$。

有这样几种语句：

input c 从标准输入读入一个整数并存储在 $c$ 中。$c$ 可以是 $a$ 到 $z$ 的任意变量。

output c 输出一个整数 $c$。$c$ 可以是 $a$ 到 $z$ 的任意变量。

c = b 把 $b$ 的值赋给 $c$。$b$ 可以是 32 位整数或 $a$ 到 $z$ 的任意变量，$c$ 可以是 $a$ 到 $z$ 的任意变量。

c = a op b 把 $a$ 和 $b$ 进行 op 运算并把值赋给 $c$。$a, b$ 可以是 32 位整数或 $a$ 到 $z$ 的任意变量，$c$ 可以是 $a$ 到 $z$ 的任意变量。op 有下面几种取值：

算术运算符

+ 表示 $a$ 和 $b$ 的加法。

- 表示 $a$ 和 $b$ 的减法。

* 表示 $a$ 和 $b$ 的乘法。

/ 表示 $a$ 和 $b$ 的除法，会按 C++ 习惯向 0 取整。

% 表示 $a$ 除以 $b$ 的余数。

逻辑运算符

== $a$ 和 $b$ 相等则为 $1$ 否则为 $0$。

!= $a$ 和 $b$ 不相等则为 $1$ 否则为 $0$。

< $a$ 小于 $b$ 则 $1$ 否则为 $0$。

> $a$ 大于 $b$ 则 $1$ 否则为 $0$。

<= $a$ 小于等于 $b$ 则 $1$ 否则为 $0$。

>= $a$ 大于等于 $b$ 则 $1$ 否则为 $0$。

if c goto t 如果 $c$ 不为 $0$ 则跳到第 $t$ 行继续执行（也就是说下一次就会执行第 $t$ 行的语句）。$c$ 可以是 32 位整数或 $a$ 到 $z$ 的任意变量，$t$ 可以是任意正 32 位整数。

当程序试图执行的语句的行号大于 $N$ 时程序结束。

由于要展望新的一年的发展前景， cxy 需要用这台电脑算出斐波那契数列的第 $n$ 项对 $m$ 取模后的结果。

但是很快 cxy 发现了问题。这台电脑竟然有一定概率算错！仔细分析后 cxy 得到了如下结论：

在进行计算算术运算 +、-、*、/、% 时，有 $\frac{1}{8}$ 的概率返回一个 32 位随机整数。

在进行计算逻辑运算 ==、!=、<、>、<=、>= 时，有 $\frac{1}{8}$ 的概率将返回的结果反转。即 $0$ 变 $1$，$1$ 变 $0$。

其它语句一定会正确执行。

这可难坏了 cxy ，她想请你帮她写一个程序能够以极高的概率算对斐波那契数列的第 $n$ 项对 $m$ 取模后的结果。

所以，请你写一个程序，输出 “一份能够完成任务的 QAQ 源代码”。

斐波那契数列 $f$ 的定义为：$f_0 = 0, f_1 = 1$，对于任意 $n \geq 2$ 的整数 $n$ 有 $f_n = f_{n - 1} + f_{n - 2}$。

出题人写了一个 QAQ 的解释器，见解释器下载。

数据范围：

$n \le 200, 2\le m\le 10^9$

如果一遍算不对，就多算几遍。

1. c = a op b
2. y = a op b
3. z = c - y
4. if z goto 1

每次出错的概率约为 $\dfrac{1}{2^{32}}$ ，重复 $600$ 次后出错率还是很低的（$2\times 10^{-7}$）

QAQ代码：

 1. input n
 2. input m
 3. a = 0
 4. b = 1
 5. c = a + b
 6. y = a + b
 7. z = c - y
 8. if z goto 5
 9. d = c % m
10. y = c % m
11. z = d - y
12. if z goto 9
13. a = b
14. b = d
15. x = n - 1
16. y = n - 1
17. z = x - y
18. if z goto 15
19. n = x
20. if n goto 5
21. output a

AC代码：

#include <iostream>
using std::cout,std::endl;
signed main()
{
    cout<<"input n"<<endl;
	cout<<"input m"<<endl;
	cout<<"a = 0"<<endl;
	cout<<"b = 1"<<endl;
	cout<<"c = a + b"<<endl;
	cout<<"z = c - a"<<endl;
	cout<<"z = z - b"<<endl;
	cout<<"if z goto 5"<<endl;
	cout<<"x = c % m"<<endl;
	cout<<"y = c / m"<<endl;
	cout<<"z = y * m"<<endl;
	cout<<"z = z + x"<<endl;
	cout<<"z = z - c"<<endl;
	cout<<"if z goto 9"<<endl;
	cout<<"c = x"<<endl;
	cout<<"a = b"<<endl;
	cout<<"b = c"<<endl;
	cout<<"c = n - 1"<<endl;
	cout<<"z = c + 1"<<endl;
	cout<<"z = z - n"<<endl;
	cout<<"if z goto 18"<<endl;
	cout<<"n = c"<<endl;
	cout<<"if n goto 5"<<endl;
	cout<<"output a"<<endl;
    return 0;
}