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;
}