পাইথনে দক্ষতার সাথে nCr মানগুলো (r=0 থেকে n) বের করা

nCr মানগুলো অনেকবার ক্যালকুলেট করতে হলে নিচের মানগুলো স্টোর করে উপরের মানগুলো সহজে বের করা যায়। n দেওয়া থাকলে nC0 থেকে nCn পর্যন্ত লিস্ট বের করতে হবে। উত্তর বড় হলে ১০⁹ দিয়ে মডুলো করুন।

উদাহরণ

ইনপুট: n = 6

আউটপুট: [1, 6, 15, 20, 15, 6, 1]

সমাধান পদ্ধতি

1. items := [1]
2. r = 1 থেকে n পর্যন্ত:
   • items.append(items[-1] * (n - r + 1) // r)
   • items[-2] %= 10⁹ (সাইজ n হলে)
3. items রিটার্ন করুন।

পাইথন ইমপ্লিমেন্টেশন

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))  # আউটপুট: [1, 6, 15, 20, 15, 6, 1]

ইনপুট

6

আউটপুট

[1, 6, 15, 20, 15, 6, 1]