ধরুন আমাদের 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।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ফাংশন নির্বাচন () সংজ্ঞায়িত করুন। এটি n, k লাগবে
- পণ্য :=1
- n থেকে n-k রেঞ্জের i এর জন্য, 1 কমিয়ে
- করুন
- পণ্য :=পণ্য * i
- আমি 1 থেকে k রেঞ্জের জন্য, কর
- পণ্য :=পণ্য / i
- পূর্ণসংখ্যা হিসাবে পণ্য ফেরত দিন
- একটি ফাংশন util() সংজ্ঞায়িত করুন। এটি d, n লাগবে
- রিটার্ন চয়ন(n-1, d) * 2 ^(choose(n-1, 2))
- প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন:
- মোট :=0
- 0 থেকে n - 1 পরিসরে d এর জন্য, করুন
- মোট :=মোট + util(d, n) * d^k
- মোট :=মোট মোড 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
