Đếm dãy nến tăng dần đủ màu trong Python

Cho n cây nến, cây i có chiều cao h[i] và màu c[i] (1..k). Tìm số dãy con tăng dần theo chiều cao và chứa đủ k màu (colorful). Kết quả modulo 10^9+7.

Ví dụ: k=3, h=[1,3,2,4], c=[1,2,2,3] → 2 dãy: [1,2,4] và [1,3,4].

Giải thuật

• Duyệt qua tất cả tập hợp màu (bitmask từ 0 đến 2^k - 1).
• Với mỗi mask, dùng cây BIT (Fenwick) để đếm số dãy con tăng dần chỉ dùng các màu trong mask.
• Áp dụng nguyên lý bao hàm - loại trừ (inclusion-exclusion) trên các mask để lấy dãy chứa đủ k màu.

Ví dụ mã 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
    def popcount(b):
        cnt = 0
        while b:
            b &= b - 1
            cnt += 1
        return cnt
    L = 1 << k
    R = 0
    N = len(h)
    for mask in range(L):
        T = [0] * 50010
        t = 0
        for j in range(N):
            if (mask >> (c[j] - 1)) & 1:
                t = (t + update(T, h[j], read(T, h[j] - 1) + 1)) % MOD
        if popcount(mask) % 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))  # Output: 2

Đầu vào

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

Đầu ra

2