SP17779 CHARCHOC - Charlie and the Chocolate Factory
题目描述
查理和他的巧克力工厂
查理·巴克特是一个善良的男孩，他与父母和四位卧床不起的祖父母生活在贫困中。在街道的另一端，有一家威利·旺卡的巧克力工厂，这家工厂因美味的巧克力和独特的工厂而闻名。经过多年的经营，旺卡终于决定为他的工厂选一个继承人。
为了找到合适的人选，旺卡决定举办一场编程竞赛，从中选出五位候选人，最后再给他们一个难题，最先解出难题的人将成为继承人。
经过比赛，旺卡选出了五位候选人，查理是其中之一。在抛出最终难题之前，旺卡给出了两个提示。
第一个提示是一段伪代码算法：
```
# `array` 是从1开始编号的数组
def MakeNewArray(array, d):
if d == 1:
return array
else:
array = MakeNewArray(array, d-1)
new_array = [array[array[i]] for i in 1..inf]
return new_array
```
例如，如果 `array = [2, 3, 5, 7, 11, ...]`，那么 `MakeNewArray(array, 2)` 的结果是 `[3, 5, 11, ...]`。
第二个提示是**库杜斯**数组。**库杜斯**数组是由 **库杜斯**数排序而成。**库杜斯**数是可以表示为两个不同正整数的平方和的质数。例如，5 可以表示为 $1^2 + 2^2$ ，因此它是一个 **库杜斯** 数。同理，13 是因为 $3^2 + 2^2$，17 因为 $4^2 + 1^2$。因此，**库杜斯**数组的前几个数是 5、13、17 等。
接下来是决定继承人的难题：有 **n** 个盒子，初始状态下每个盒子都是空的（没有巧克力）。在比赛中，每一步旺卡都会进行一组操作。操作通过一个整数 **op** 表示：
1. **op = 1**，加法操作，后跟整数 **a, b**。表示在第 **a** 号盒子中添加 **b** 块巧克力。
2. **op = 2**，乘法操作，同样后跟整数 **a, b**。表示将第 **a** 号盒子中的巧克力乘以 **b**。
3. **op = 3**，交换操作，后跟整数 **a, b**。表示交换第 **a** 和第 **b** 号盒子的巧克力。
4. **op = 4**，清空操作，后跟整数 **a**。表示清空第 **a** 号盒子的所有巧克力。
有两组操作：一组是**普通**操作，另一组是**特殊**操作。在一般步骤中，按顺序执行**普通**操作。在特殊步骤中，按顺序执行**特殊**操作。特殊步骤的编号存储在一个叫做 **Special** 的数组中。
具体来说，**Special** 是一个无限长的有序数组。它的元素分别是 **Special\[1\]**、**Special\[2\]**、**Special\[3\]**，以此类推。因而，旺卡只会在特殊步骤 **Special\[i\]**（i=1,2,3,...）时执行特殊操作。
现在，
**Special := MakeNewArray(Kuddus, d).**
这里的 **MakeNewArray** 和 **Kuddus** 数组已在前面描述。**d** 是输入中的一个整数。最后，旺卡会告知总共有 **s** 步。
查理因为忙于其他事情，需要你的帮助。你需要计算 **s** 步之后，所有盒子中巧克力的总数（即每个盒子里的巧克力之和）。
输入格式
输入包含最多 15 个测试用例。
每个测试用例以两个整数 **n (≥2)** 和 **d (1≤d≤5)** 开头。然后是一个整数 **op1**，表示普通步骤的操作数。接下来的 **op1** 行，每行包含一个整数 **op (1≤op≤4)**，如果 **op≤3**，则后面跟着两个整数 **a** 和 **b**，否则（**op=4**）后面跟着一个整数 **a**。接着是另一个整数 **op2**，表示特殊步骤的操作数，接下来的 **op2** 行��入格式与 **op1** 相同。最后是一个整数 **s (1≤s≤10^8)**。
所有输入都是非负整数，不超过 1000，并且没有非法输入（即不会在不存在的盒子上执行操作）。同时保证每个位可能的 **d** 值，都有相同比例的测试用例，并且 **n ≤ 2 * d^2**。
输出格式
对于每个测试用例，输出一行，表示在 **s** 步之后所有盒子里的巧克力总数。你需要输出 **答案 % 2^64**。
**样例输入**
```
2 1
5
1 1 1
1 2 1
2 1 2
2 2 3
3 1 2
3
1 1 1
1 2 1
3 1 2
4
2 1
5
1 1 1
1 2 1
2 1 2
2 2 3
3 1 2
3
1 1 1
1 2 1
3 1 2
5
```
**样例输出**
```
119
121
```
**本翻译由 AI 自动生成**