पायथन में सख्ती से बढ़ते रंगीन मोमबत्ती अनुक्रमों की संख्या खोजने का प्रोग्राम

मान लीजिए n मोमबत्तियां हैं जो बाएं से दाएं संरेखित हैं। बाईं ओर से iवीं मोमबत्ती की ऊंचाई h[i] और रंग c[i] है। हमारे पास एक पूर्णांक k भी है, जो दर्शाता है कि 1 से k की रेंज में रंग हैं। हमें पता लगाना है कि कितने सख्ती से बढ़ते रंगीन मोमबत्ती अनुक्रम हैं? बढ़ता हुआ अनुक्रम ऊंचाई के आधार पर जांचा जाता है, और एक अनुक्रम को रंगीन कहा जाता है यदि रेंज 1 से K में प्रत्येक रंग की कम से कम एक मोमबत्ती उपलब्ध है। यदि उत्तर बहुत बड़ा है, तो परिणाम मॉड 10^9 + 7 लौटाएं।

तो, यदि इनपुट K = 3, h = [1,3,2,4], c = [1,2,2,3] है, तो आउटपुट 2 होगा क्योंकि इसमें अनुक्रम [1,2,4] और [1,3,4] हैं।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

• एक फ़ंक्शन read() परिभाषित करें। यह T, i लेगा
• s := 0
• जब तक i > 0, करें
  • s := s + T[i]
  • s := s mod 10^9+7
  • i := i -(i AND -i)
• s लौटाएं
• एक फ़ंक्शन update() परिभाषित करें। यह T, i, v लेगा
• जब तक i <= 50010, करें
  • T[i] := T[i] + v
  • T[i] := T[i] mod 10^9+7
  • i := i +(i AND -i)
• v लौटाएं
• मुख्य विधि से, निम्न कार्य करें:
• L := 2^k, R := 0, N := h का आकार
• i को 0 से L - 1 तक की रेंज में, करें
  • T := आकार 50009 की एक सरणी जिसे 0 से भरा गया है
  • t := 0
  • j को 0 से N - 1 तक की रेंज में, करें
    • यदि (i को (c[j] - 1) बार दाएं शिफ्ट करने के बाद) विषम है, तो
      • t := t + update(T, h[j], read(T, h[j] - 1) + 1)
      • t := t mod 10^9+7
  • यदि (i में बिट्स की संख्या) mod 2, k mod 2 के समान है, तो
    • R := R + t
    • R := R mod 10^9+7
  • अन्यथा,
    • R := (R + 10^9+7) - t
    • R := R mod 10^9+7
• R लौटाएं

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

def solve(k, h, c): def read(T, i): s = 0 while i > 0: s += T[i] s %= 1000000007 i -= (i & -i) return s def update(T, i, v): while i <= 50010: T[i] += v T[i] %= 1000000007 i += (i & -i) return v def number_of_bits(b): c = 0 while b: b &= b - 1 c += 1 return c L = 2 ** k R = 0 N = len(h) for i in range(L): T = [0 for _ in range(50010)] t = 0 for j in range(N): if (i >> (c[j] - 1)) & 1: t += update(T, h[j], read(T, h[j] - 1) + 1) t %= 1000000007 if number_of_bits(i) % 2 == k % 2: R += t R %= 1000000007 else: R += 1000000007 - t R %= 1000000007 return R k = 3 h = [1,3,2,4] c = [1,2,2,3] print(solve(k, h, c))

इनपुट

3, [1,3,2,4], [1,2,2,3] 

आउटपुट

2