题目链接

题意

给出 m 个三元组 (l, r, x), 说明数列 \(\{a_n\}\) 满足 \(a_l\&a_{l+1}\&...\&a_r=x\), 问有多少个满足以上条件的数列, 对 998244353 取模. 数列长度为 n, 每个数小于 \(2^k\). n, m ≤ 5e5, k ≤ 30.

题解

对每个数位分别处理. 问题转化为已知一个 01 数组一定范围的按位与, 问有多少种可能结果.

如果一个区间按位与为 1, 那么每个数都是 1; 否则, 至少有 1 个 0. 从左往右扫描, \(dp_i\) 为最右边的 0 出现在位置 i, 并且前面的数字都满足要求时的结果. 特别 \(dp_0\) 为全 1 时的结果. 对于一个限制 \(a[l \& ... \& r] = 0\), \(l ≤ r < j\), \(dp_j\) 只能从 \(i ≥ l\) 的位置转移过来(本题关键点). 有多组限制时, 只考虑最大的 l 值.

最后结果取不小于 l 的位置之和(l 不存在时为全和), 恰为 \(dp_{n+1}\).

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inc(i, l, r) for (int i = l; i <= r; i++)
#define dec(i, l, r) for (int i = l; i >= r; i--)
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back

const int maxn = 1e6 + 5;
const int mod = 998244353;

int n, k, m;
int l[maxn], r[maxn], x[maxn];
ll dp[maxn], sd[maxn], res = 1;
int pre[maxn];

void solve(int d) {
    vector<int> p(n + 1, 0);
    memset(pre, 0, sizeof(pre));
    inc(i, 0, m - 1) {
        if (x[i] >> d & 1) {
            pre[l[i]]++, pre[r[i] + 1]--;
        } else {
            p[r[i]] = max(p[r[i]], l[i]);
        }
    }
    dp[0] = sd[0] = 1;
    int zero = 0, tmp = 0;
    inc(i, 1, n + 1) {
        tmp += pre[i];
        if (tmp > 0) {
            dp[i] = 0;
        } else {
            if (zero) {
                dp[i] = (sd[i - 1] - sd[zero - 1] + mod) % mod;
            } else {
                dp[i] = sd[i - 1];
            }
        }
        zero = max(zero, p[i]);
        sd[i] = (sd[i - 1] + dp[i]) % mod;
    }
    res = res * dp[n + 1] % mod;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k >> m;
    inc(i, 0, m - 1) cin >> l[i] >> r[i] >> x[i];
    inc(i, 0, k - 1) solve(i);
    cout << res << "\n";
}