用 Python 编写程序，从前 n 个自然数的排列中找出魔法集的数量

pythonserver side programmingprogramming更新于 2026/1/30 17:16:17

假设我们有一个包含前 n 个自然数的数组 A，以及数组 A 的一个排列 P{p1, p2, ... pn}。我们必须检查有多少个魔法集。如果满足以下几个规则，则排列被称为魔法集 −

如果有 k，则位置 a[1]、a[2]、... a[k] 中的元素小于其相邻元素 [P[a[i] - 1] > P[a[i]] < P[a[i] + 1]]
如果有 l，则位置 b[1]、b[2]、... b[l] 中的元素大于其相邻元素 [P[b[i] - 1] < P[b[i]] > P[b[i] + 1]]

因此，如果输入为 n = 4 k = 1 l = 1 k_vals = [2] l_vals = [3]，则输出将为 5，因为:N = 4、a[1] = 2 和 b[1] = 3。因此五个排列为 [2,1,4,3]、[3,2,4,1]、[4,2,3,1]、[3,1,4,2]、[4,1,3,2]。

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

p := 10^9+7
F := 大小为 n+2 的数组并用 0 填充
对于 k_vals 中的每个 a，执行
- 如果 F[a - 1] 为 1 或 F[a + 1] 为 1，则
  - 如果 F[a - 1] 为 1 或 F[a + 1] 为 1，则
    - p := null
  - F[a] := 1
对于 l_vals 中的每个 b，执行
- 如果 F[b] 为 1 或 F[b - 1] 为 -1 或 F[b + 1] 为 -1，则
  - p := null
- F[b] := -1
如果 p 与 null 相同，则
- 返回0
否则，
- A := 一个大小为 n+1 的数组，并用 0 填充
- B := 一个大小为 n+1 的数组，并用 0 填充
- FF := 一个大小为 n+1 的数组，并用 null 填充
- 对于范围从 1 到 n 的 i，执行
  - FF[i] := F[i] - F[i - 1]
- A[1] := 1
- 对于范围在 2 到 n 内的 i，执行
  - 对于范围在 1 到 i 内的 j，执行
    - 如果 FF[i] > 0，则
      - B[j] :=(B[j - 1] + A[j - 1]) mod p
    - 否则，当 FF[i] < 0 时，则
      - B[j] :=(B[j - 1] + A[i - 1] - A[j - 1]) mod p
    - 否则，
      - B[j] :=(B[j - 1] + A[i - 1]) mod p
  - 交换 A 和 B
- 返回 A[n]

示例

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

def solve(n, k, l, k_vals, l_vals):
   p = 10**9+7
   F = [0] * (n + 2)
   for a in k_vals:
      if F[a - 1] == 1 or F[a + 1] == 1:
         p = None
      F[a] = 1
   for b in l_vals:
      if F[b] == 1 or F[b - 1] == -1 or F[b + 1] == -1:
         p = None
      F[b] = -1
   if p == None:
      return 0
   else:
      A = [0] * (n + 1)
      B = [0] * (n + 1)
      FF = [None] * (n + 1)
      for i in range(1, n + 1):
         FF[i] = F[i] - F[i - 1]
      A[1] = 1
      for i in range(2, n + 1):
         for j in range(1, i + 1):
            if FF[i] > 0:
               B[j] = (B[j - 1] + A[j - 1]) % p
            elif FF[i] < 0:
               B[j] = (B[j - 1] + A[i - 1] - A[j - 1]) % p
            else:
               B[j] = (B[j - 1] + A[i - 1]) % p
         A, B = B, A
      return A[n]

n = 4
k = 1
l = 1
k_vals = [2]
l_vals = [3]
print(solve(n, k, l, k_vals, l_vals))