有 \(m\) 个限制 \((l, r, x)\)。
要计算满足以下条件的长度为 \(n\) 的序列 \(a\) 的数量：
- \(\forall i \in [1, n], 0 \le a_i < 2^k\)。
- \(\forall i \in [1, m], a_{l_i} \operatorname{and} a_{l_i + 1} \operatorname{and} \cdots \operatorname{and} a_{r_i} = x\)。
\(n, m \le 10^5, k \le 30\)。
首先要想到分别计算二进制下每一位的方案数然后乘起来就是答案。
然后现在问题就变成了有若干个限制表示 \(a\) 在 \([l_i, r_i]\) 中的数的按位与为 0/1，要计算 01 序列 \(a\) 的数量。
将每个限制挂到右端点上，然后 dp 计算方案数。
因为是按位与，所以值只与最后一个 0 的位置有关。所以设 \(f_{i, j}\) 表示考虑了前 \(i\) 个位置，最后一个 0 的位置为 \(j\) 时的方案数。
可以发现，对于每条限制，其实是限制了最后一个 0 的位置一定是在一个区间里。具体地说，如果有一个限制 \((l, r, 0)\)，就说明在 \([l, r]\) 一定有一个 0，也就是当 \(i = r\) 时，最后一个 0 一定是在 \([l, r]\) 中；如果有一个限制 \((l, r, 1)\)，就说明在 \([l, r]\) 中一定全是 1，也就是当 \(i = r\) 时，最后一个 0 一定是在 \([0, l - 1]\) 中。
转移就是先考虑没有限制的时候：对当前位置填 0 还是填 1 分别考虑：
\[f_{i, j} \leftarrow f_{i - 1, j} \\ f_{i, i} \leftarrow \sum_{j \in [0, i)} f_{i - 1, j} \]再考虑加上限制:
- 如果有一个限制 \((l, r, 0)\)：
- 如果有一个限制 \((l, r, 1)\)：
把第一维滚掉之后我们要做的就是单点改、前缀推平成 0、求前缀和，这个记一下前缀和和最长前缀推平长度就行了。
时间复杂度 \(O(nk)\)。
constexpr int MAXN = 5e5 + 9;
int n, k, m, ans = 1, f[MAXN], a[MAXN];
vector<pair<int, int> > lim[MAXN];
int calc(int bit) {
for (int i = f[0] = 1; i <= n; i ++) f[i] = 0, a[i] = 0;
for (int r = 1; r <= n; r ++) for (auto [l, x] : lim[r])
if (x >> bit & 1) a[l] ++, a[r + 1] --;
for (int i = 1; i <= n; i ++) a[i] += a[i - 1];
int sum = 1, pre = 0;
for (int i = 1; i <= n; i ++) {
int pos = 0;
for (auto [l, x] : lim[i])
if ((x >> bit & 1) == 0) cmax(pos, l);
if (!a[i]) f[i] = sum, cadd(sum, f[i]);
while (pre < pos) cdel(sum, f[pre]), pre ++;
}
return sum;
}
void slv() {
n = Read<int>(), k = Read<int>(), m = Read<int>();
for (int i = 1; i <= m; i ++) {
int l = Read<int>(), r = Read<int>(), x = Read<int>();
lim[r].emplace_back(l, x);
}
for (int i = 0; i < k; i ++) cmul(ans, calc(i));
Write(ans, '\n');
return;
}