AND Segments (Codeforces 1327F)
Tags: DP, bitmasks

You are given three integers $$$n$$$, $$$k$$$, $$$m$$$ and $$$m$$$ conditions $$$(l_1, r_1, x_1), (l_2, r_2, x_2), \dots, (l_m, r_m, x_m)$$$.Calculate the number of distinct arrays $$$a$$$, consisting of $$$n$$$ integers such that:   $$$0 \le a_i < 2^k$$$ for each $$$1 \le i \le n$$$;  bitwise AND of numbers $$$a[l_i] \& a[l_i + 1] \& \dots \& a[r_i] = x_i$$$ for each $$$1 \le i \le m$$$. Two arrays $$$a$$$ and $$$b$$$ are considered different if there exists such a position $$$i$$$ that $$$a_i \neq b_i$$$. The number can be pretty large so print it modulo $$$998244353$$$.

Input: The first line contains three integers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \le n \le 5 \cdot 10^5$$$, $$$1 \le k \le 30$$$, $$$0 \le m \le 5 \cdot 10^5$$$) — the length of the array $$$a$$$, the value such that all numbers in $$$a$$$ should be smaller than $$$2^k$$$ and the number of conditions, respectively.Each of the next $$$m$$$ lines contains the description of a condition $$$l_i$$$, $$$r_i$$$ and $$$x_i$$$ ($$$1 \le l_i \le r_i \le n$$$, $$$0 \le x_i < 2^k$$$) — the borders of the condition segment and the required bitwise AND value on it.

Output: Print a single integer — the number of distinct arrays $$$a$$$ that satisfy all the above conditions modulo $$$998244353$$$.

Note: You can recall what is a bitwise AND operation here.In the first example, the answer is the following arrays: $$$[3, 3, 7, 6]$$$, $$$[3, 7, 7, 6]$$$ and $$$[7, 3, 7, 6]$$$.

Sample Inputs:
4 3 2
1 3 3
3 4 6

5 2 3
1 3 2
2 5 0
3 3 3

Sample Outputs:
3

33

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, k, m) = map(int, input().split())
mod = 998244353
lrx = [tuple(map(int, input().split())) for _ in range(m)]
ans = 1
p = 1
for _ in range(k):
    u = [0] * (n + 2)
    v = [0] * (n + 2)
    for (l, r, x) in lrx:
        if x & p:
            u[l] += 1
            u[r + 1] -= 1
        else:
            v[r] = max(l, v[r])
    for i in range(1, n + 2):
        u[i] += u[i - 1]
    for i in range(1, n + 2):
        u[i] = u[i - 1] + min(1, u[i])
    dp = [0] * (n + 3)
    dp[0] = 1
    ml = 0
    for i in range(1, n + 2):
        if not u[i] - u[i - 1]:
            dp[i] = dp[i - 1] - dp[ml - 1]
            dp[i] %= mod
        ml = max(ml, v[i])
        dp[i] += dp[i - 1]
        dp[i] %= mod
    ans *= dp[n + 1] - dp[n]
    ans %= mod
    p *= 2
    if not ans:
        break
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    mod = 998244353
    (N, K, M) = map(int, input().split())
    cond = []
    for _ in range(M):
        cond.append(tuple(map(int, input().split())))
    ans = 1
    for k in range(K):
        one = [0] * (N + 1)
        zero_cond = [0] * (N + 1)
        for (l, r, x) in cond:
            if x >> k & 1:
                one[l - 1] += 1
                one[r] -= 1
            else:
                zero_cond[r] = max(zero_cond[r], l)
        for i in range(N):
            one[i + 1] += one[i]
        dp = [0] * (N + 1)
        dp[0] = 1
        cs = [0] * (N + 2)
        cs[1] = 1
        R = 0
        for i in range(N):
            if not one[i]:
                dp[i + 1] = (cs[i + 1] - cs[R]) % mod
            cs[i + 2] = (cs[i + 1] + dp[i + 1]) % mod
            R = max(R, zero_cond[i + 1])
        ans = ans * (cs[-1] - cs[R]) % mod % mod
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from itertools import accumulate
(n, k, m) = map(int, input().split())
Q = [tuple(map(int, input().split())) for i in range(m)]
mod = 998244353
S = 1
for keta in range(k):
    ANS = [0] * (n + 5)
    QK = [n + 3] * (n + 5)
    for (l, r, x) in Q:
        l -= 1
        r -= 1
        if x & 1 << keta != 0:
            ANS[l] += 1
            ANS[r + 1] -= 1
        else:
            QK[l] = min(QK[l], r + 1)
    ANS = tuple(accumulate(ANS))
    for i in range(n + 3, -1, -1):
        QK[i] = min(QK[i], QK[i + 1])
    PLUS = [0] * (n + 5)
    PLUS[0] = 1
    PLUS[1] = -1
    for i in range(n + 1):
        PLUS[i] = (PLUS[i] + PLUS[i - 1]) % mod
        if ANS[i - 1] == 0:
            last = QK[i]
            PLUS[i + 1] = (PLUS[i] + PLUS[i + 1]) % mod
            PLUS[last + 1] = (PLUS[last + 1] - PLUS[i]) % mod
    S = S * (PLUS[n] + PLUS[n + 1]) % mod
print(S)