मान लीजिए एक अजीब भाषा है जिसे अजॉब भाषा कहते हैं। इसमें अनंत संख्या में अक्षर हैं। हम इस भाषा में n शब्द जानते हैं। पहला शब्द एक अक्षर लंबा है, दूसरा दो अक्षर लंबा है और इसी तरह। और एक शब्द के सभी अक्षर अद्वितीय हैं। यदि हम n शब्दों में से किसी एक को चुनते हैं और उससे एक सबसीक्वेंस बनाते हैं। सबसीक्वेंस की लंबाई मूल शब्द की लंबाई से k कम होनी चाहिए। उदाहरण के लिए, यदि चुने गए शब्द की लंबाई L है, तो सबसीक्वेंस की लंबाई (L - k) होनी चाहिए। यदि k से छोटी लंबाई वाला कोई शब्द है, तो आपको वह शब्द नहीं चुनना चाहिए। और दो सबसीक्वेंस एक-दूसरे से भिन्न होते हैं जब उनकी लंबाई भिन्न होती है या उनमें समान स्थिति पर अलग-अलग वर्ण होते हैं। हमें परिणाम मॉड्यूलो p खोजना है, और p एक अभाज्य संख्या है।
तो, यदि इनपुट n = 6, k = 5, p = 11 है, तो आउटपुट 7 होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- एक खाली डिक्शनरी memo बनाएं
- n := n + 1, k := k + 1
- fact := एक तत्व 1 वाली सूची
- i को 1 से p - 1 तक की रेंज में, करें
- (fact के अंतिम तत्व * i mod p) को fact के अंत में डालें
- यदि p, memo में मौजूद है, तो
- inv_fact := memo[p]
- अन्यथा,
- inv := दो तत्वों 0 और 1 वाली सूची
- i को 2 से p - 1 तक की रेंज में, करें
- (p - p/i के फ्लोर * inv[p mod i] mod p) को inv के अंत में डालें
- inv_fact := एक तत्व 1 वाली सूची
- i को 1 से p - 1 तक की रेंज में, करें
- (inv_fact के अंतिम तत्व * inv[i] mod p) को inv_fact के अंत में डालें
- memo[p] := inv_fact
- ret := 1
- जब तक n > 0, करें
- 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 का फ्लोर
- ret लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
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