Python에서 인접한 k 스왑 및 최대 k 스왑 후 시퀀스 수를 찾는 프로그램

처음 n개의 자연수가 있는 배열 A가 있다고 가정합니다. A에서 정확히 k개의 인접 스왑 후에 얻을 수 있는 시퀀스(S1)의 수를 찾아야 합니까? 그리고 A에서 기껏해야 k 스왑 후에 몇 개의 시퀀스(S2)를 얻을 수 있습니까? 여기서 인접 스왑은 인덱스 i와 i+1의 요소를 바꾸는 것을 의미합니다.

따라서 입력이 n =3 k =2와 같으면 출력은 -

원래 배열은 [1, 2, 3]

• 2번의 인접한 스왑 후:[1, 2, 3], [2, 3, 1], [3, 1, 2]를 얻을 수 있으므로 S1 =3
• 최대 2번의 교환 후:
  • 0 스왑 후:[1, 2, 3]
  • 1회 교환 후:[2, 1, 3], [3, 2, 1], [1, 3, 2].
  • 2번의 교환 후:[1, 2, 3], [2, 3, 1], [3, 1, 2]

따라서 S2 =6

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

• p =10^9+7
• A :=요소가 하나만 있는 배열 1
• C :=요소가 하나만 있는 배열 1
• 2~n+1 범위의 n에 대해
  • B :=A, A :=요소가 하나만 있는 배열 1
  • D :=C, C :=요소가 하나만 있는 배열 1
  • 범위 1에서 (k+1 및 1에서 n까지의 모든 숫자의 합) 최소값까지 x의 경우
    • insert(A의 마지막 요소 + (B[x] 일 때 x
  • 1에서 n-2 사이의 x에 대해 다음을 수행합니다.
    • C 끝에 ((D[x]+(n-1)*D[x-1]) mod p) 삽입
  • C 끝에 (n * D의 마지막 요소) mod p 삽입
• A[인덱스 k mod 2에서 k까지]) mod p 및 C[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