Python程式:查詢經過最多k次相鄰交換後的序列數量


假設我們有一個數組A,包含前n個自然數。我們需要找到經過精確k次相鄰交換後可以得到多少個序列(S1)?以及經過最多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],[1, 3, 2],[3, 2, 1]
    • 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到min(k+1, 1+2+...+n)
      • 將((A的最後一個元素 + (如果x < B的大小,則為B[x],否則為0) - (如果0 <= x-n,則為B[x-n],否則為0)) mod p)插入到A的末尾
    • 對於x從1到n-2,執行:
      • 將((D[x] + (n-1)*D[x-1]) mod p)插入到C的末尾
    • 將(n * C的最後一個元素) mod p插入到C的末尾
  • 返回(A[從索引k mod 2到k的元素之和] mod p)和C[min(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))

輸入

3, 2

輸出

3, 6

更新於:2021年10月23日

瀏覽量:190

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告