Cho mảng colors độ dài n (màu các đỉnh n-gon). Đếm tập con đỉnh size ≥2 sao cho: bỏ các đỉnh đó, các đường đi liên tiếp còn lại không có 2 đỉnh cùng màu.
Thuật toán
- Tổng tập con size ≥2: sum(C(n,i)) i=2..n.
- Trừ các tập con "xấu": tồn tại 2 đỉnh cùng màu trong cùng một đoạn sau khi bỏ.
- Với mỗi màu, xét các cặp vị trí (i,j). Nếu khoảng cách vòng tròn ≤ n-3 thì tập con chứa cặp đó là xấu.
Ví dụ
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, c in enumerate(colors):
count[c].append(i)
ans = sum(nCr(n, i) for i in range(2, n + 1))
for pos in count.values():
n0 = len(pos)
if n0 > 1:
for i in range(n0 - 1):
for j in range(i + 1, n0):
d1 = pos[j] - pos[i]
d2 = pos[i] - pos[j] + n
if d1 <= n - 3 or d2 <= n - 3:
ans -= 1
return ans
print(solve([1, 2, 3, 4])) # Output: 11Giải thích
colors=[1,2,3,4] (tất cả khác màu) → mọi tập con size≥2 đều tốt: 2^4 - 4 - 1 = 11.