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