โปรแกรมหาจำนวน subset ของยอดที่มีสี ตามเงื่อนไขที่กำหนดใน Python

กำหนดอาเรย์ colors แทนสีของ n-gon แบบปกติ แต่ละยอดถูกสุ่มสีจาก n สีในอาเรย์ หาจำนวน subset พิเศษของยอดที่ตรงตามเงื่อนไข:

• ขนาด subset ต้อง ≥ 2
• ถ้านำยอดใน subset ออก (รวมขอบที่ติดกัน) ยอดและขอบที่เหลือจะเป็น path ต่อเนื่องหลายเส้น
• ไม่มี path ใดที่มียอดสีเดียวกัน 2 ยอด

นับจำนวน subset ที่ตรงเงื่อนไข ถ้าผลลัพธ์ใหญ่ คืนค่า mod 10^9+7

เช่น colors = [1,2,3,4] ผลลัพธ์คือ 11

วิธีแก้ปัญหา

• count := map ว่าง ค่าเป็น list ว่าง
• n := ขนาด colors
• ลูป i จาก 0 ถึง len(colors)-1: เพิ่ม i ลง count[colors[i]]
• answer := 0
• ลูป i จาก 2 ถึง n: answer := answer + nCr(n, i)
• สำหรับแต่ละ i ใน keys ของ count
  • l0 := count[i], n0 := len(l0)
  • ถ้า n0 > 1
    • ลูป i จาก 0 ถึง n0-2
      • ลูป j จาก i+1 ถึง n0-1
        • 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))

Input

[1,2,3,4]

Output

11