在 Python 中查找相邻 k 次交换和至多 k 次交换后的序列数的程序

假设我们有一个包含前 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
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))

输入

3, 2

3, 6