Giả sử chúng ta có một đồ thị vô hướng G với n nút. Bây giờ hãy coi chi phí của một đồ thị vô hướng đơn giản là tổng chi phí của các nút của nó. Và Chi phí của một nút là D ^ k, trong đó D là độ của nó. Bây giờ chúng ta có giá trị n và k. Chúng ta phải tìm tổng chi phí của tất cả các đồ thị vô hướng đơn giản có thể có với n nút. Kết quả có thể rất lớn, vì vậy hãy trả về resultmodulo 1005060097.
Vì vậy, nếu đầu vào là n =3 k =2, thì đầu ra sẽ là 36 vì có tám đồ thị đơn giản với 3 nút.
- Một đồ thị chỉ có 3 cạnh và chi phí của nó là 2 ^ 2 + 2 ^ 2 + 2 ^ 2 =12.
- Có các đồ thị có hai cạnh và chi phí của mỗi cạnh là 1 ^ 2 + 1 ^ 2 + 2 ^ 2 =6.
- Ba đồ thị có một cạnh và chi phí của mỗi đồ thị là 0 ^ 2 + 1 ^ 2 + 1 ^ 2 =2.
- Một biểu đồ không có cạnh và chi phí của nó là 0 ^ 2 + 0 ^ 2 + 0 ^ 2 =0.
Vì vậy, tổng là 12 * 1 + 6 * 3 + 2 * 3 + 0 * 1 =36.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định một hàm select (). Điều này sẽ mất n, k
- sản phẩm:=1
- đối với tôi trong phạm vi n đến n-k, giảm đi 1, thực hiện
- product:=product * i
- đối với tôi trong phạm vi từ 1 đến k, thực hiện
- product:=product / i
- trả về sản phẩm dưới dạng số nguyên
- Xác định một hàm dùng (). Điều này sẽ mất d, n
- return select (n-1, d) * 2 ^ (select (n-1, 2))
- Từ phương thức chính, hãy thực hiện như sau:
- tổng số:=0
- đối với d trong phạm vi từ 0 đến n - 1, thực hiện
- tổng số:=tổng cộng + dùng (d, n) * d ^ k
- tổng số:=tổng số mod 1005060097
- return (total * n) mod 1005060097
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def choose(n, k): product = 1 for i in range(n, n-k, -1): product *= i for i in range(1, k+1): product /= i return int(product) def util(d, n): return choose(n-1, d) * 2 ** (choose(n-1, 2)) def solve(n, k): total = 0 for d in range(n): total += util(d, n) * d ** k total %= 1005060097 return (total * n) % 1005060097 n = 3 k = 2 print(solve(n, k))
Đầu vào
3, 2
Đầu ra
36