用 Python 编写程序，查找相邻 k 次交换后和最多 k 次交换后的序列数

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

假设我们有一个包含前 n 个自然数的数组 A。我们必须找出在 A 上进行精确的 k 次相邻交换后可以得到多少个序列 (S1)?在 A 上进行最多 k 次交换后可以得到多少个序列 (S2)?此处相邻交换是指在索引 i 和 i+1 处交换元素。

因此，如果输入为 n = 3 k = 2，则输出将为 3, 6，因为 −

原始数组为 [1, 2, 3]

2 次相邻交换后:我们可以得到 [1, 2, 3], [2, 3, 1], [3, 1, 2]，因此 S1 = 3
最多 2 次交换后:
- 0 次交换后:[1, 2, 3]
- 1 次交换后:[2, 1, 3], [3, 2, 1], [1, 3, 2]。
- 2 次交换后:[1, 2, 3], [2, 3, 1], [3, 1, 2]

所以 S2 = 6

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

p = 10^9+7
A := 只有一个元素 1 的数组
C := 只有一个元素 1 的数组
对于 n 在 2 到 n+1 范围内，执行
- B := A, A := 只有一个元素 1 的数组
- D := C, C := 只有一个元素 1 的数组
- 对于 x 在 1 到(k+1 和从 1 到 n 的所有数字之和)的最小值范围内
  - 插入(A 的最后一个元素 + (当 x < B 的大小时为 B[x]，否则为 0) - (当 0 <= x-n 时为 B[x-n]，否则为 0)) mod p) 在 A 的末尾
- 对于范围为 1 到 n-2 的 x，执行
  - 在 C 的末尾插入 ((D[x]+(n-1)*D[x-1]) mod p)
- 在 C 的末尾插入 (n * D 的最后一个元素) mod p
返回 A[从索引 k mod 2 到 k]) mod p 和 C[n-1 和 k 中的最小值] 的所有元素之和

示例

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

p = 10**9+7
def solve(n, k):
   A = [1]
   C = [1]
   for n in range(2,n+1):
      B = A
      A = [1]
      D = C
      C = [1]

      for x in range(1,min(k+1,n*(n-1)//2+1)):
         A.append((A[-1] + (B[x] if x<len(B) else 0) - (B[x-n] if 0<=x-n else 0)) % p )
      for x in range(1,n-1):
         C.append((D[x]+(n-1)*D[x-1]) % p)
      C.append(n*D[-1] % p)
   return sum(A[k%2:k+1:2]) % p,C[min(n-1,k)]

n = 3
k = 2
print(solve(n, k))