ধরুন আমাদের অনেকবার nCr মান গণনা করতে হবে। আমরা এই খুব কার্যকর উপায় সমাধান করতে পারেন. যদি আমরা nCr-এর নিম্ন মানগুলি সংরক্ষণ করি তবে আমরা সহজেই উচ্চ মানগুলি খুঁজে পেতে পারি। তাই যদি আমাদের n থাকে, তাহলে আমাদের nC0 থেকে nCn-এর তালিকা খুঁজে বের করতে হবে। যদি উত্তরটি খুব বড় হয় তবে সেই মডিউলটি 10^9 ফেরত দিন।
সুতরাং, যদি ইনপুট n =6 এর মত হয়, তাহলে আউটপুট হবে [1, 6, 15, 20, 15, 6, 1]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- আইটেম :=একক উপাদান 1 সহ একটি তালিকা 1 থেকে n রেঞ্জের মধ্যে r-এর জন্য,
- আইটেমের শেষে (আইটেমের শেষ উপাদান * (n-r+1) /r) এর মেঝে ঢোকান
- আইটেম[n-2] :=আইটেম[n-2] মোড 10^9 যেখানে n আইটেমের আকার হয়
- আইটেম ফেরত দিন
- করুন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
def solve(n): items = [1] for r in range(1,n+1): items.append(items[-1]*(n-r+1)//r) items[-2] %= 10**9 return items n = 6 print(solve(n))
ইনপুট
6
আউটপুট
[1, 6, 15, 20, 15, 6, 1]
