Chương trình tìm số bộ ma thuật từ một hoán vị của n số tự nhiên đầu tiên trong Python

Giả sử chúng ta có một mảng A với n số tự nhiên đầu tiên và một hoán vị P {p1, p2, ... pn} của mảng A. Chúng ta phải kiểm tra xem có bao nhiêu tập phép thuật. Một hoán vị được cho là tập hợp ma thuật, nếu điều này thỏa mãn một số quy tắc sau -

Nếu chúng ta có k, thì các phần tử ở vị trí a [1], a [2], ... a [k] nhỏ hơn các phần tử liền kề của chúng [P [a [i] - 1]> P [a [i]]
Nếu chúng ta có l, thì các phần tử ở vị trí b [1], b [2], ... b [l] lớn hơn các phần tử liền kề [P [b [i] - 1]
P [b [i] + 1]]

Vì vậy, nếu đầu vào là n =4 k =1 l =1 k_vals =[2] l_vals =[3], thì đầu ra sẽ là 5 vì:N =4, a [1] =2 và b [1] =3. Vậy năm hoán vị là [2,1,4,3], [3,2,4,1], [4,2,3,1], [3,1,4,2], [4 , 1,3,2].

Để 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
F:=Một mảng có kích thước n + 2 và điền bằng 0
đối với mỗi a trong k_vals, thực hiện
- nếu F [a - 1] là 1 hoặc F [a + 1] là 1, thì
  - nếu F [a - 1] là 1 hoặc F [a + 1] là 1, thì
    - p:=null
  - F [a]:=1
đối với mỗi b trong l_vals, thực hiện
- nếu F [b] là 1 hoặc F [b - 1] là -1 hoặc F [b + 1] là -1, thì
  - p:=null
- F [b]:=-1
nếu p giống với null, thì
- trả về 0
nếu không,
- A:=Một mảng có kích thước n + 1 và điền bằng 0
- B:=Một mảng có kích thước n + 1 và điền bằng 0
- FF:=Một mảng có kích thước n + 1 và điền bằng null
- đối với tôi trong phạm vi từ 1 đến n, thực hiện
  - FF [i]:=F [i] - F [i - 1]
- A [1]:=1
- đối với tôi trong phạm vi từ 2 đến n, thực hiện
  - đối với j trong phạm vi 1 đến i, thực hiện
    - nếu FF [i]> 0, thì
      - B [j]:=(B [j - 1] + A [j - 1]) mod p
    - ngược lại khi FF [i] <0, thì
      - B [j]:=(B [j - 1] + A [i - 1] - A [j - 1]) mod p
    - nếu không,
      - B [j]:=(B [j - 1] + A [i - 1]) mod p
  - hoán đổi A và B
- trả về A [n]

Ví dụ

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

def solve(n, k, l, k_vals, l_vals):
   p = 10**9+7
   F = [0] * (n + 2)
   for a in k_vals:
      if F[a - 1] == 1 or F[a + 1] == 1:
         p = None
      F[a] = 1
   for b in l_vals:
      if F[b] == 1 or F[b - 1] == -1 or F[b + 1] == -1:
         p = None
      F[b] = -1
   if p == None:
      return 0
   else:
      A = [0] * (n + 1)
      B = [0] * (n + 1)
      FF = [None] * (n + 1)
      for i in range(1, n + 1):
         FF[i] = F[i] - F[i - 1]
      A[1] = 1
      for i in range(2, n + 1):
         for j in range(1, i + 1):
            if FF[i] > 0:
               B[j] = (B[j - 1] + A[j - 1]) % p
            elif FF[i] < 0:
               B[j] = (B[j - 1] + A[i - 1] - A[j - 1]) % p
            else:
               B[j] = (B[j - 1] + A[i - 1]) % p
         A, B = B, A
      return A[n]

n = 4
k = 1
l = 1
k_vals = [2]
l_vals = [3]
print(solve(n, k, l, k_vals, l_vals))

Đầu vào

4, 1, 1, [2], [3]