Python程式：查詢所有具有n個節點的簡單無向圖的成本總和

假設我們有一個具有n個節點的無向圖G。現在考慮一個簡單無向圖的成本是其節點成本的總和。節點的成本為D^k，其中D是其度數。現在我們有n和k值。我們必須找到所有可能的具有n個節點的簡單無向圖的成本總和。結果可能非常大，因此返回結果模1005060097。

因此，如果輸入類似於n = 3 k = 2，則輸出將為36，因為有八個具有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。

為了解決這個問題，我們將遵循以下步驟：

定義一個函式choose()。它將接收n，k
product := 1
對於i從n到n-k，遞減1，執行：
- product := product * i
對於i從1到k，執行：
- product := product / i
返回product作為整數
定義一個函式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))

輸入

3, 2

輸出

Arnab Chakraborty

更新於: 2021年10月25日

258 次檢視

開啟你的職業生涯

透過完成課程獲得認證

開始