Chương trình tính tổng chi phí tất cả đồ thị vô hướng đơn giản n đỉnh trong Python

Đồ thị vô hướng đơn giản n đỉnh. Chi phí đỉnh = D^k (D=bậc). Chi phí đồ thị = tổng chi phí đỉnh. Tính tổng chi phí của tất cả đồ thị có thể (2^{C(n,2)} đồ thị) mod 1005060097.

Thuật toán

• Với bậc d cố định, số đồ thị có đỉnh cụ thể bậc d: C(n-1, d) * 2^{C(n-1,2)}.
• Tổng chi phí = n * Σ_{d=0}^{n-1} C(n-1,d) * 2^{C(n-1,2)} * d^k.

Ví dụ

def choose(n, k):
    prod = 1
    for i in range(n, n - k, -1):
        prod *= i
    for i in range(1, k + 1):
        prod //= i
    return prod

def util(d, n):
    return choose(n - 1, d) * 2 ** choose(n - 1, 2)

def solve(n, k):
    MOD = 1005060097
    total = 0
    for d in range(n):
        total = (total + util(d, n) * pow(d, k, MOD)) % MOD
    return (total * n) % MOD

print(solve(3, 2))  # Output: 36

Giải thích

n=3: 8 đồ thị. Tính chi phí từng loại, tổng = 36.