পাইথনে অজব সিকোয়েন্স থেকে সাবসিকোয়েন্স বেছে নেওয়ার উপায় গণনা করা

একটি অদ্ভুত ভাষা 'Ajob' আছে যার অসীম অক্ষর। প্রথম শব্দ ১ অক্ষরের, দ্বিতীয় ২ অক্ষরের, এভাবে n-তম শব্দ n অক্ষরের। প্রতিটি শব্দের সব অক্ষর ইউনিক। n শব্দ থেকে যেকোনো একটি বেছে নিয়ে সাবসিকোয়েন্স বানাতে হবে যেন সাবসিকোয়েন্সের দৈর্ঘ্য মূল শব্দের দৈর্ঘ্য থেকে k কম হয় (L - k)। যদি শব্দের দৈর্ঘ্য k-র চেয়ে ছোট হয় তবে সেটি বেছে নেওয়া যাবে না। দুটি সাবসিকোয়েন্স ভিন্ন হলে যদি দৈর্ঘ্য ভিন্ন হয় অথবা একই পজিশনে ভিন্ন ক্যারেক্টার থাকে। ফলাফল p দিয়ে মডুলো করতে হবে (p প্রাইম)।

উদাহরণ

ইনপুট: n = 6, k = 5, p = 11

আউটপুট: 7

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

মেমোইজেশন ডিকশনারি memo তৈরি করুন।
n := n + 1, k := k + 1
ফ্যাক্টোরিয়াল অ্যারে fact বানান m প্যারামিটার দিয়ে।
মডুলার ইনভার্স ফ্যাক্টোরিয়াল inv_fact বানান (লুকাস থিওরেম ব্যবহার করে)।
লুকাস থিওরেম দিয়ে C(n, k) mod p ক্যালকুলেট করুন।

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

memo = {}

def solve(n, k, p):
    n += 1
    k += 1
    fact = [1]
    for i in range(1, p):
        fact.append(fact[-1] * i % p)
    if p in memo:
        inv_fact = memo[p]
    else:
        inv = [0, 1]
        for i in range(2, p):
            inv.append(p - p // i * inv[p % i] % p)
        inv_fact = [1]
        for i in range(1, p):
            inv_fact.append(inv_fact[-1] * inv[i] % p)
        memo[p] = inv_fact
    ret = 1
    while n > 0:
        n1 = n % p
        k1 = k % p
        if k1 > n1:
            return 0
        ret = ret * fact[n1] * inv_fact[k1] * inv_fact[n1 - k1] % p
        n //= p
        k //= p
    return ret

# টেস্ট
n = 6
k = 5
p = 11
print(solve(n, k, p))  # আউটপুট: 7

ইনপুট

6, 5, 11