Chương trình tìm số chuỗi sau k hoán đổi liền kề và nhiều nhất k hoán đổi trong Python

Giả sử chúng ta có một mảng A với n số tự nhiên đầu tiên. Chúng ta phải tìm xem chúng ta có thể nhận được bao nhiêu dãy (S1) sau khi chính xác k hoán đổi liền kề trên A? Và chúng ta có thể nhận được bao nhiêu dãy (S2) sau nhiều nhất k hoán đổi trên A? Ở đây hoán đổi liền kề có nghĩa là hoán đổi các phần tử ở chỉ mục i và i + 1.

Vì vậy, nếu đầu vào là n =3 k =2, thì đầu ra sẽ là 3, 6 vì -

Mảng ban đầu là [1, 2, 3]

• Sau 2 lần hoán đổi liền kề:chúng ta có thể nhận được [1, 2, 3], [2, 3, 1], [3, 1, 2] Vậy S1 =3
• Sau nhiều nhất 2 lần hoán đổi:
  • Sau khi hoán đổi 0:[1, 2, 3]
  • Sau 1 lần hoán đổi:[2, 1, 3], [3, 2, 1], [1, 3, 2].
  • Sau 2 lần hoán đổi:[1, 2, 3], [2, 3, 1], [3, 1, 2]

Vậy S2 =6

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• p =10 ^ 9 + 7
• A:=mảng chỉ có một phần tử 1
• C:=một mảng chỉ có một phần tử 1
• đối với n trong phạm vi 2 đến n + 1, thực hiện
  • B:=A, A:=một mảng chỉ có một phần tử 1
  • D:=C, C:=một mảng chỉ có một phần tử 1
  • cho x trong phạm vi từ 1 đến nhỏ nhất là (k + 1 và tổng của tất cả các số từ 1 đến n)
    • chèn (phần tử cuối cùng của A + (B [x] khi x
  • đối với x trong phạm vi 1 đến n-2, thực hiện
    • insert ((D [x] + (n-1) * D [x-1]) mod p) vào cuối C
  • insert (n * phần tử cuối cùng của D) mod p vào cuối C
• trả về tổng của tất cả các phần tử của A [từ chỉ số k mod 2 đến k]) mod p và C [tối thiểu của n-1 và k]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

3, 2

Đầu ra

3, 6