프로그램은 Python에서 주어진 조건을 충족하는 다채로운 꼭짓점의 하위 집합 수를 찾습니다.

<시간/>

하나의 일반 n-gon에 대한 색상을 나타내는 배열 색상이 있다고 가정합니다. 여기에서 이 n-gon의 각 정점은 주어진 배열에 존재하는 n개의 다른 색상 중 하나로 무작위로 색상이 지정되었습니다. 우리는 폴리곤 꼭짓점의 특수한 부분집합의 수를 찾아야 하며, 이러한 부분집합이 다음 조건을 충족하도록 합니다. −

하위 집합의 크기는 2개 이상이어야 합니다.
폴리곤에서 하위 집합에 있는 정점을 제거하면(해당 정점의 인접한 가장자리도 제거됨) 나머지 정점과 가장자리는 일부 연속 경로를 형성합니다.
이러한 경로에는 같은 색상의 정점이 두 개 포함되어서는 안 됩니다.

우리는 그러한 하위 집합의 수를 계산해야 합니다. 답이 너무 크면 결과 모드 10^9 + 7을 반환합니다.

따라서 입력이 색상 =[1,2,3,4]와 같으면 출력은 11이 됩니다.

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

count :=모든 값이 빈 목록이 되는 빈 지도입니다.
n :=색상 크기
0 ~ 색상 크기 - 1 범위의 i에 대해
- count[colors[i]] 끝에 i 삽입
답변 :=0
2~n 범위의 i에 대해 다음을 수행합니다.
- answer :=답변 + nCr(n, i)
count의 모든 키 목록에 있는 각 i에 대해 do
- l0 :=count[i]
- n0 :=l0의 크기
- n0> 1이면
  - 0에서 n0-2 사이의 i에 대해 다음을 수행합니다.
    - i+1 ~ n0 - 1 범위의 j에 대해
      - d1 :=l0[j] -l0[i]
      - d2 :=l0[i] -l0[j] + n
      - d1 <=n-3 또는 d2<=n-3이면
        
        답변 :=대답 - 1
반환 응답

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

from collections import defaultdict
from math import factorial

def nCr(n, i):
   if n==1:
      return 1
   return factorial(n)//factorial(i)//factorial(n-i)

def solve(colors):
   count = defaultdict(list)
   n = len(colors)

   for i in range(len(colors)):
      count[colors[i]].append(i)
   answer = 0

   for i in range(2, n+1):
      answer += nCr(n, i)

   for i in count.keys():
      l0 = count[i]
      n0 = len(l0)

      if n0 > 1:
         for i in range(n0-1):
            for j in range(i+1, n0):
               d1 = l0[j] -l0[i]
               d2 = l0[i] -l0[j] + n
               if d1 <= n-3 or d2<= n-3:
                  answer -=1

   return answer

colors = [1,2,3,4]
print(solve(colors))

입력

[1,2,3,4]