CF1060H Sophisticated Device
题目描述
给你两个正整数 $d$ 和 $p$,$p$ 是质数。
你还有一个神奇的机器,有很多个格子,每个格子有一个 0 到 $p-1$ 的整数。它还支持两种操作:求和与求 $d$ 次幂。 **结果都对 $p$ 取模。**
这些格子编号分别为 $1,2,3,\ldots,5000$,一开始第一、二个格子分别存储 $x,y(0\leq x,y\leq p-1)$,其余格子存储 1。
你不能直接访问格子里面的变量,你也**不知道** $x,y$ 为多少(但你知道它们分别存在前两格)。你应该使用给定的指令编写程序,让一个格子里面出现 $xy\mod p$。你的程序必须可以应对任何可能的 $x,y$。
加法指令把两个格子里面的数之和放进第三个格子。这个指令形如 `+ e1 e2 to`,用途是将第 $e1$ 格与第 $e2$ 格之和放入第 $to$ 格。$e1,e2,to$ 可以相等。
第二个指令将一个格子里的数的 $d$ 次幂放进另一个格子。这个指令形如 `^ e to`,用途是将第 $e$ 格数字的 $d$ 次幂放入第 $to$ 格。$e,to$可以相等,这时第 $e$ 格的数字将被覆盖。
最后一个指令返回答案。这个指令形如 `f target`,用途是表示第 $target$ 格就是所求的 $xy\mod p$。这之后不应有任何指令。
编写程序求出 $xy\mod p$。指令总数不应超过 5000 条,包括返回答案的指令在内。
保证有解。
输入格式
无
输出格式
无
说明/提示
本题**没有样例**。下面是个例子。注意这不是任何一个数据的解,仅仅为了说明格式。
```text
+ 1 1 3
^ 3 3
+ 3 2 2
+ 3 2 3
^ 3 1
f 1
```
|步骤 |格1 |格2 |格3 |
| :-----------: | :-----------: | :-----------: | :-----------: |
|最初 |$x$ |$y$ |$1$ |
|`+ 1 1 3`|$x$ |$y$ |$2x$ |
|`^3 3` |$x$ |$y$ |$(2x)^d$ |
|`+3 2 2` |$x$ |$y+(2x)^d$ |$(2x)^d$ |
|`+ 3 2 3` |$x$ |$y+(2x)^d$ |$y+2*(2x)^d$ |
|`^ 3 1` |$(y+2*(2x)^d)^d$ |$y+(2x)^d$ |$y+2*(2x)^d$ |