ধরুন আজব ভাষা বলে একটা অদ্ভুত ভাষা আছে। এতে অসীম সংখ্যক অক্ষর রয়েছে। আমরা এই ভাষায় n শব্দ জানি। প্রথম শব্দটি একটি অক্ষর দীর্ঘ, দ্বিতীয়টি দুটি অক্ষর দীর্ঘ ইত্যাদি। এবং একটি শব্দের সমস্ত অক্ষর অনন্য। যদি আমরা n শব্দের যেকোনো একটি নির্বাচন করি এবং এটি থেকে একটি অনুগামী গঠন করি। পরবর্তী শব্দের দৈর্ঘ্য মূল শব্দের দৈর্ঘ্যের চেয়ে k কম হওয়া উচিত। উদাহরণস্বরূপ, যদি নির্বাচিত শব্দের দৈর্ঘ্য L বলা হয়, তাহলে পরবর্তী শব্দের দৈর্ঘ্য (L - k) হওয়া উচিত। যদি k-এর থেকে ছোট দৈর্ঘ্যের কোনো শব্দ, তাহলে, আপনি অবশ্যই সেই শব্দটি বেছে নেবেন না। এবং দুটি অনুবর্তন একে অপরের থেকে ভিন্ন হয় যখন তাদের দৈর্ঘ্য ভিন্ন হয় বা একই অবস্থানে বিভিন্ন অক্ষর থাকে। আমাদের ফলাফল মডিউল p, এবং p i a prime বের করতে হবে।
সুতরাং, যদি ইনপুট হয় n =6, k =5, p =11, তাহলে আউটপুট হবে 7।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি খালি অভিধান মেমো তৈরি করুন
- n :=n + 1, k :=k + 1
- তথ্য :=একটি উপাদান 1 সহ একটি তালিকা
- আমি 1 থেকে p - 1 রেঞ্জের জন্য, কর
- সত্যের শেষে সন্নিবেশ করুন (তথ্যের শেষ উপাদান * i mod p)
- যদি মেমোতে p উপস্থিত থাকে, তাহলে
- inv_fact :=মেমো[p]
- অন্যথায়,
- inv :=দুটি উপাদান 0 এবং 1 সহ একটি তালিকা
- আমি 2 থেকে p - 1 রেঞ্জের জন্য, কর
- ইনসার্ট (p - ফ্লোর এর p/i * inv[p mod i] mod p) inv এর শেষে
- inv_fact :=একটি উপাদান 1 সহ একটি তালিকা
- আমি 1 থেকে p - 1 রেঞ্জের জন্য, কর
- inv_fact এর শেষে সন্নিবেশ (inv_fact * inv[i] mod p এর শেষ উপাদান)
- মেমো[p] :=inv_fact
- ret :=1
- যখন n> 0, do
- n1 :=n mod p
- k1 :=k mod p
- যদি k1> n1 হয়, তাহলে
- রিটার্ন 0
- ret :=ret * fact[n1] * inv_fact[k1] * inv_fact[n1 - k1] mod p
- n :=(n/p) এর ফ্লোর
- k :=k/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)) ইনপুট
6, 5, 11
আউটপুট
7
