파이썬에서 처음 n개의 자연수의 순열에서 매직 세트의 수를 찾는 프로그램

<시간/>

처음 n개의 자연수가 있는 배열 A와 배열 A의 순열 P{p1, p2, ... pn}가 있다고 가정합니다. 매직 세트가 몇 개 있는지 확인해야 합니다. 순열은 다음 몇 가지 규칙을 충족하는 경우 마법 세트라고 합니다. −

k가 있는 경우 위치 a[1], a[2], ... a[k]의 요소는 인접한 요소 [P[a[i] - 1]> P[a [i]]
l이 있는 경우 위치 b[1], b[2], ... b[l]의 요소는 인접한 요소 [P[b[i] - 1] P[b[i] + 1]]

따라서 입력이 n =4 k =1 l =1 k_vals =[2] l_vals =[3]인 경우 출력은 N =4, a[1] =2 및 b[1]이기 때문에 5가 됩니다. =3. 따라서 5개의 순열은 [2,1,4,3], [3,2,4,1], [4,2,3,1], [3,1,4,2], [4]입니다. ,1,3,2].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

p :=10^9+7
F :=크기가 n+2이고 0으로 채워지는 배열
k_vals의 각각에 대해 다음을 수행합니다.
- F[a - 1]이 1이거나 F[a + 1]이 1이면
  - F[a - 1]이 1이거나 F[a + 1]이 1이면
    - p :=null
  - F[a] :=1
l_vals의 각 b에 대해 다음을 수행합니다.
- F[b]가 1이거나 F[b - 1]이 -1이거나 F[b + 1]이 -1이면
  - p :=null
- F[b] :=-1
p가 null과 같으면
- 0을 반환
그렇지 않으면
- A :=크기가 n+1이고 0으로 채워지는 배열
- B :=크기가 n+1이고 0으로 채워지는 배열
- FF :=크기가 n+1이고 null로 채워진 배열
- 1~n 범위의 i에 대해
  - FF[i] :=F[i] - F[i - 1]
- A[1] :=1
- 2~n 범위의 i에 대해 다음을 수행합니다.
  - 1~i 범위의 j에 대해
    - FF[i]> 0이면
      - B[j] :=(B[j - 1] + A[j - 1]) 모드 p
    - 그렇지 않으면 FF[i] <0일 때
      - B[j] :=(B[j - 1] + A[i - 1] - A[j - 1]) 모드 p
    - 그렇지 않으면
      - B[j] :=(B[j - 1] + A[i - 1]) 모드 p
  - A와 B 교환
- 반환 A[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))

입력

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