資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學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
廣告