プログラムは、Pythonで指定された条件を満たすカラフルな頂点のサブセットの数を見つけます

1つの正多角形の色を表す配列色があるとします。ここで、このn-gonの各頂点は、指定された配列に存在するn個の異なる色の1つでランダムに色付けされました。これらのサブセットがこれらの条件を満たすように、ポリゴン頂点の特別なサブセットの数を見つける必要があります-

• サブセットのサイズは少なくとも2つである必要があります。
• サブセットに存在する頂点をポリゴンから削除すると（これらの頂点の隣接するエッジも削除されます）、残りの頂点とエッジはいくつかの連続したパスを形成します。
• これらのパスのいずれにも、同じ色の2つの頂点を含めることはできません。

そのようなサブセットの数を数える必要があります。答えが大きすぎる場合は、結果mod 10 ^ 9+7を返します。

したがって、入力がcolors =[1,2,3,4]の場合、出力は11になります。

これを解決するには、次の手順に従います-

• count：=すべての値が空のリストになる空のマップ。
• n：=色のサイズ
• 0から色のサイズ-1までの範囲のiの場合、実行します
  • カウントの最後にiを挿入[colors[i]]
• 回答：=0
• 2からnの範囲のiについては、
  • 回答：=回答+ nCr（n、i）
• カウントのすべてのキーのリストにある各iについて、
  • l0：=count [i]
  • n0：=l0のサイズ
  • n0> 1の場合、
    • 0からn0-2の範囲のiについては、
      • i +1からn0-1の範囲のjの場合、do
        • 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]

出力

11