กำหนดกราฟไม่มีทิศทาง G มี n โหนด ค่าใช้จ่ายของกราฟ = ผลรวมค่าใช้จ่ายโหนด ค่าใช้จ่ายโหนด = D^k โดย D คือ degree กำหนด n และ k หาผลรวมค่าใช้จ่ายของกราฟแบบไม่มีทิศทาง ทุกกรณีที่เป็นไปได้ mod 1005060097
เช่น n=3, k=2 ผลลัพธ์ 36 เพราะมี 8 กราฟ: - 1 กราฟ 3 ขอบ cost=12 - 3 กราฟ 2 ขอบ cost=6 แต่ละอัน - 3 กราฟ 1 ขอบ cost=2 แต่ละอัน - 1 กราฟ 0 ขอบ cost=0 รวม = 12*1 + 6*3 + 2*3 + 0*1 = 36
วิธีแก้ปัญหา
- ฟังก์ชัน choose(n, k) คำนวณ binomial coefficient
- ฟังก์ชัน util(d, n) = choose(n-1, d) * 2^(choose(n-1, 2))
- total := 0
- ลูป d จาก 0 ถึง n-1
- total := total + util(d, n) * d^k
- total := total mod 1005060097
- คืนค่า (total * n) mod 1005060097
ตัวอย่างโค้ด
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))Input
3, 2
Output
36
