मान लीजिए हमारे पास 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 के लिए range n से n-k तक, 1 से घटाकर, करें
- product := product * i
- i के लिए range 1 से k तक, करें
- product := product / i
- product को पूर्णांक के रूप में वापस करें
- util() फ़ंक्शन परिभाषित करें। यह d, n लेगा
- choose(n-1, d) * 2 ^(choose(n-1, 2)) वापस करें
- मुख्य मेथड से, निम्नलिखित करें:
- total := 0
- d के लिए range 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
आउटपुट
36
