โปรแกรมค้นหาจำนวนลำดับของเทียนที่มีสีสันเพิ่มขึ้นอย่างเคร่งครัดมีอยู่ใน Python

สมมติว่ามีเทียน n เล่มเรียงจากซ้ายไปขวา เทียนแท่งที่ i จากด้านซ้ายมีความสูง h[i] และสี c[i] นอกจากนี้เรายังมีเลขจำนวนเต็ม k ซึ่งแสดงว่ามีสีอยู่ในช่วง 1 ถึง k เราต้องค้นหาว่ามีลำดับของขนมที่มีสีสันเพิ่มขึ้นอย่างเข้มงวดมากน้อยเพียงใด? ลำดับที่เพิ่มขึ้นจะได้รับการตรวจสอบโดยพิจารณาจากความสูง และมีการกล่าวถึงลำดับว่ามีสีสัน หากมีเทียนแต่ละสีอย่างน้อยหนึ่งแท่งในช่วง 1 ถึง K หากคำตอบมีขนาดใหญ่เกินไป ให้คืนค่า mod ผลลัพธ์ 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)
• คืนสินค้า
• กำหนดฟังก์ชั่น update() นี่จะใช้เวลา T, i, v
• ในขณะที่ฉัน <=50010 ทำ
  • T[i] :=T[i] + v
  • T[i] :=T[i] mod 10^9+7
  • i :=i +(i AND -i)
• รีเทิร์นวี
• จากวิธีหลัก ให้ทำดังต่อไปนี้ −
• L :=2^k, R :=0, N :=size of h
• สำหรับฉันในช่วง 0 ถึง L - 1 ทำ
  • T :=อาร์เรย์ขนาด 50009 และเติม 0
  • t :=0
  • สำหรับ j ในช่วง 0 ถึง N - 1 ให้ทำ
    • ถ้า (ฉันหลังจากขยับบิต (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