মান লেট n নোড বিশিষ্ট একটি অ dirig গ্রাফ G আছে। এখন একটি সিম্পল অ dirig গ্রাফের কস্ট হল তার নোডগুলোর কস্টের যোগফল। এবং একটি নোডের কস্ট D^k, যেখানে D হল তার ডিগ্রি। এখন আমাদের n এবং k মান দেয়া আছে। আমাদের n নোড বিশিষ্ট সব সম্ভাব্য সিম্পল অ dirig গ্রাফের কস্টের যোগফল বের করতে হবে। রেজাল্ট খুব বড় হতে পারে, তাই রেজাল্ট মডুলো 1005060097 রিটার্ন করুন।
তাহলে, যদি ইনপুট হয় n = 3 k = 2, তবে আউটপুট হবে 36 কারণ, ৩ নোড বিশিষ্ট আটটি সিম্পল গ্রাফ আছে।
- শুধু ৩টি এজ বিশিষ্ট একটি গ্রাফ, এর কস্ট 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 পর্যন্ত, ১ কমানো করে, করুন
- 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
আউটপুট
36
