用 Python 编写程序，查找满足给定条件的彩色顶点子集的数量

pythonserver side programmingprogramming更新于 2026/2/1 13:00:17

假设我们有一个数组 colors，表示一个正 n 边形的颜色。这里，这个 n 边形的每个顶点都随机地用给定数组中存在的 n 种不同颜色之一着色。我们必须找到多边形顶点的特殊子集的数量，使得这些子集满足这些条件 −

子集的大小必须至少为 2。
如果我们从多边形中删除子集中存在的顶点(这些顶点的相邻边也将被删除)，则剩余的顶点和边将形成一些连续路径。
这些路径都不应包含两个相同颜色的顶点。

我们必须计算存在的此类子集的数量。如果答案太大，则返回结果 mod 10^9 + 7。

因此，如果输入为 colors = [1,2,3,4]，则输出为 11。

为了解决这个问题，我们将遵循以下步骤 −

count := 一个空映射，其中所有值都将是一个空列表。
n := colors 的大小
对于范围为 0 到颜色大小 - 1 的 i，执行
- 在 count[colors[i]] 的末尾插入 i
answer := 0
对于范围为 2 到 n 的 i，执行
- answer := answer + nCr(n, i)
对于每个i 在所有 count 键的列表中，执行
- 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，则
        
        answer := answer - 1
返回 answer

示例

让我们看看下面的实现以便更好地理解 −

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