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

मान लीजिए कि 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
• जबकि मैं> 0, करते हैं
  • s :=s + T[i]
  • s :=s mod 10^9+7
  • i :=i -(i AND -i)
• वापसी
• एक फ़ंक्शन अपडेट () को परिभाषित करें। इसमें टी, आई, वी
. लगेगा
• जबकि मैं <=50010, करते हैं
  • टी[i] :=टी[i] + वी
  • टी[i] :=टी[i] मॉड 10^9+7
  • i :=i +(i AND -i)
• वापसी वी
• मुख्य विधि से, निम्न कार्य करें -
• एल:=2^के, आर:=0, एन:=एच का आकार
• मैं के लिए 0 से एल -1 की सीमा में, करो
  • T :=50009 आकार की एक सरणी और 0 से भरें
  • टी:=0
  • जे के लिए 0 से एन -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 mod 10^9+7
  • अन्यथा,
    • R :=(R + 10^9+7) - t
    • R :=R mod 10^9+7
• रिटर्न आर

उदाहरण

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

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