পাইথনে কঠোরভাবে ক্রমবর্ধমান রঙিন মোমবাতির ক্রম সংখ্যা খুঁজে বের করার প্রোগ্রাম রয়েছে

ধরুন 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, do
  • s :=s + T[i]
  • s :=s মোড 10^9+7
  • i :=i -(i AND -i)
• রিটার্ন এস
• একটি ফাংশন আপডেট() সংজ্ঞায়িত করুন। এটি T, i, v
লাগবে
• যখন i <=50010, do
  • T[i] :=T[i] + v
  • T[i] :=T[i] মোড 10^9+7
  • i :=i +(i AND -i)
• রিটার্ন v
• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
• L :=2^k, R :=0, N :=h এর আকার
• আমি 0 থেকে L - 1 রেঞ্জের জন্য, কর
  • T :=50009 আকারের একটি অ্যারে এবং 0 দিয়ে পূরণ করুন
  • t :=0
  0 থেকে N - 1 এর মধ্যে j-এর জন্য
  • করুন
    • যদি (i বিট স্থানান্তর করার পরে (c[j] - 1) বার ডানদিকে) বিজোড় হয়, তাহলে
      • t :=t + আপডেট(T, h[j], read(T, h[j] - 1) + 1)
      • t :=t মোড 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