पायथन में अजॉब सीक्वेंस से अनुक्रम का चयन करने के कई तरीकों को खोजने के लिए कार्यक्रम

मान लीजिए कि एक अजीब भाषा है जिसे अजॉब भाषा कहा जाता है। इसमें अनंत संख्या में अक्षर हैं। हम इस भाषा में n शब्द जानते हैं। पहला शब्द एक वर्ण लंबा है, दूसरा दो वर्ण लंबा है और इसी तरह। और एक शब्द के सभी अक्षर अद्वितीय होते हैं। यदि हम n शब्दों में से किसी एक का चयन करते हैं और उसका एक क्रम बनाते हैं। बाद की लंबाई मूल शब्द की लंबाई से 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 के लिए
- तथ्य के अंत में (तथ्य का अंतिम तत्व * i mod p) डालें
यदि मेमो में p मौजूद है, तो
- inv_fact :=मेमो[p]
अन्यथा,
- आमंत्रण:=दो तत्वों 0 और 1 के साथ एक सूची
- 2 से p-1 की श्रेणी में i के लिए
  - आमंत्रण के अंत में (p - तल p/i * inv[p mod i] mod p) डालें
- inv_fact :=एक तत्व 1 वाली सूची
- 1 से p-1 की श्रेणी में i के लिए
  - inv_fact के अंत में (inv_fact * inv[i] mod p का अंतिम तत्व) डालें
- ज्ञापन[p] :=inv_fact
सेवानिवृत्त:=1
जबकि n> 0, करें
- n1 :=n मॉड 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