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

มีเทียน n แท่ง เรียงซ้ายไปขวา เทียน i มีความสูง h[i] และสี c[i] (สี 1..k) ต้องการนับลำดับย่อยที่เพิ่มขึ้นอย่างเคร่งครัดตามความสูง และมีสีครบทุกสี 1..k อย่างน้อย 1 แท่ง โมดุลอ 10^9+7

ตัวอย่าง: K=3, h=[1,3,2,4], c=[1,2,2,3] → ผลลัพธ์ 2 (ลำดับ [1,2,4] และ [1,3,4])

ขั้นตอนการแก้ปัญหา

ใช้ Inclusion-Exclusion บนเซตสี และ Fenwick Tree (BIT) สำหรับนับ LIS ต่อสี:

1. วนลูปทุก subset ของสี (bitmask i จาก 0 ถึง 2^k-1)
2. สำหรับแต่ละ subset ใช้ BIT นับจำนวน increasing subsequences ที่ใช้เฉพาะสีใน subset
3. รวมผลลัพธ์ด้วยเครื่องหมาย (-1)^{|subset| - k} (Inclusion-Exclusion)

ตัวอย่างโค้ด Python

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

# ทดสอบ
k = 3
h = [1, 3, 2, 4]
c = [1, 2, 2, 3]
print(solve(k, h, c))  # ผลลัพธ์: 2

อินพุตตัวอย่าง

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

เอาต์พุตตัวอย่าง

2