用 Python 编写程序，找出无限序列生成的向量的标量积

pythonserver side programmingprogramming更新于 2026/1/26 15:08:17

假设我们得到了三个整数 c、m 和 n。我们必须生成一个无限序列，其中第一个值为 0，第二个值为 c，从第三个值开始，它等于 ki = (ki-2 + ki-1) mod m。我们必须生成序列中直到项 k2n+1 的所有值。现在从序列的值中；我们取序列中的两个连续值作为二维向量的 x 和 y 坐标，并生成 n 个向量。需要注意的是，我们使用序列中从第三个值开始的值。还有另一个集合 S，其中每个值都是向量 i 和向量 j 的标量积，其中 1 <= i，j <= n 且 i != j。我们必须找出集合 S 中不同残基的数量。如果该值非常大，我们将其乘以 m。

因此，如果输入为 5、6、4，则输出为 3

生成的序列为:[0、5、5、4、3、1、4、5、3、2]。

向量为:(5, 4)、(3, 1)、(4, 5)、(3, 2)。

从向量的标量积来看，集合 S 中只有三个残基值 mod 6。

因此结果是 3 mod 6 = 3。

为了解决这个问题，我们将遵循以下步骤 −

如果 n 与 1 相同，则
- 返回0
否则，
- temp_arr:= 一个大小为 2*n+2 的新列表，用 0 初始化
- temp_arr[0] := 0
- temp_arr[1] := c
- arr2 := 一个新列表
- 对于 2 到 2 * n+2 范围内的 i，执行
  - temp_arr[i] :=(temp_arr[i - 1] + temp_arr[i - 2]) mod m
- 对于 2 到 2 * n-2 范围内的 i，增加 2，执行
  - temp :=(temp_arr[i] * temp_arr[i + 2] + temp_arr[i + 1] * temp_arr[i + 3]) mod m
  - 在 arr2 末尾插入 temp
  - temp :=(temp_arr[i] * temp_arr[i+4] + temp_arr[i+1] * temp_arr[i+5]) mod m
  - 在 arr2 末尾插入 temp
- temp :=(temp_arr[2 * n-2] * temp_arr[2 * n] + temp_arr[2 * n-1] * temp_arr[2 * n+1]) mod m
- 在 arr2 末尾插入 temp
- 从 arr2 中删除重复项
- 返回 arr2 的大小

示例

让我们看看下面的实现以便更好地理解 −

def solve(c, m, n):
   if (n == 1):
      return 0
   else:
      temp_arr=[0 for i in range(2 * n+2)]
      temp_arr[0] = 0
      temp_arr[1] = c
      arr2 = []
      for i in range(2, 2 * n+2):
         temp_arr[i] = (temp_arr[i - 1] + temp_arr[i - 2]) % m
      for i in range(2, 2 * n-2, 2):
         temp = (temp_arr[i] * temp_arr[i + 2] + temp_arr[i + 1] * temp_arr[i + 3]) % m
         arr2.append(temp)
         temp = (temp_arr[i] * temp_arr[i+4] + temp_arr[i+1] * temp_arr[i+5]) % m
         arr2.append(temp)
      temp = (temp_arr[2 * n-2] * temp_arr[2 * n] + temp_arr[2 * n- 1] * temp_arr[2 * n+1]) % m
      arr2.append(temp)
      arr2 = set(arr2)
      return len(arr2)

print(solve(5, 6, 4))