厳密に増加するカラフルなキャンドルシーケンスの数を見つけるプログラムがPythonにあります

左から右に並べられたn本のろうそくがあるとします。左側からi番目のキャンドルの高さはh[i]、色はc[i]です。また、整数kがあり、1からkの範囲の色があることを表します。厳密に増加しているカラフルなキャンディーのシーケンスがいくつあるかを見つける必要がありますか？増加するシーケンスは高さに基づいてチェックされ、1からKの範囲の各色のキャンドルが少なくとも1つある場合、シーケンスはカラフルであると言われます。答えが大きすぎる場合は、結果mod 10 ^ 9+7を返します。

したがって、入力がK =3 h =[1,3,2,4] c =[1,2,2,3]の場合、シーケンス[1,2,4]があるため、出力は2になります。および[1,3,4]。

これを解決するには、次の手順に従います-

• 関数read（）を定義します。これにはTがかかります、私
• s：=0
• i> 0の間、do
  • s：=s + T [i]
  • s：=s mod 10 ^ 9 + 7
  • i：=i-（i AND -i）
• return s
• 関数update（）を定義します。これにはT、i、vが必要です
• i <=50010の間、do
  • T [i]：=T [i] + v
  • T [i]：=T [i] mod 10 ^ 9 + 7
  • i：=i +（i AND -i）
• return v
• メインの方法から、次の手順を実行します-
• L：=2 ^ k、R：=0、N：=hのサイズ
• 0からL-1の範囲のiの場合、do
  • T：=サイズ50009の配列で、0で埋めます
  • t：=0
  • 0からN-1の範囲のjの場合、do
    • （ビット（c [j]-1）回右にシフトした後のi）が奇数の場合、
      • t：=t + update（T、h [j]、read（T、h [j]-1）+ 1）
      • t：=t mod 10 ^ 9 + 7
  • if（iのビット数）mod2がkmod 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