मान लीजिए कि हमारे पास n नोड्स के साथ एक अप्रत्यक्ष ग्राफ G है। अब विचार करें कि एक साधारण अप्रत्यक्ष ग्राफ की लागत इसके नोड्स की लागत का योग है। और एक नोड की लागत डी^के है, जहां डी इसकी डिग्री है। अब हमारे पास 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 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक फ़ंक्शन को परिभाषित करें चुनें() । इसमें n, k . लगेगा
- उत्पाद:=1
- n से n-k की श्रेणी में i के लिए, 1 से घटाएं
- उत्पाद:=उत्पाद * मैं
- 1 से k की श्रेणी में i के लिए, करें
- उत्पाद:=उत्पाद / मैं
- उत्पाद को पूर्णांक के रूप में लौटाएं
- उपयोग() फ़ंक्शन को परिभाषित करें। इसमें d, n . लगेगा
- वापसी चुनें (एन -1, डी) * 2 ^ (चुनें (एन -1, 2))
- मुख्य विधि से, निम्न कार्य करें:
- कुल :=0
- डी रेंज 0 से n -1 के लिए, करो
- कुल:=कुल + उपयोग(डी, एन) * डी^के
- कुल:=कुल मॉड 1005060097
- वापसी (कुल * n) मॉड 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