题目描述

难度分:$2500$

输入$n(1 \leq n \leq 5 \times 10^5)$，$k(1 \leq k \leq 30)$，$m(0 \leq m \leq 5 \times 10^5)$。

然后输入$m$行，每行输入三个数$L$，$R(1 \leq L \leq R \leq n)$，$x(0 \leq x \lt 2^k)$，表示一个约束：

$a[L]$AND$a[L+1]$AND…AND$a[R]=x$

其中AND表示按位与。

输出有多少个长为$n$的数组$a$，满足上述这$m$个约束，且元素值在$[0, 2^k)$内。注意数组下标从$1$开始。

答案模$998244353$。

输入样例$1$

4 3 2
1 3 3
3 4 6

输出样例$1$

3

输入样例$2$

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

输出样例$2$

33

算法

今天在做这道题的时候不止一次感觉快要开出来了，但最终以失败告终，还是看了灵佬的题解。看来实力还远不够把一周的茶全部都做出来，需要继续努力。

动态规划+双指针

这个题比较容易看出来的一点就是各位都是独立的，按位来计算方案数，然后把每一位的方案数乘起来就是最终答案。对于某个特定的二进制位，我们用动态规划来计算它的合法方案数。

我们先将所有的操作$(l,r,x)$存入数组$d$，并遍历$x$的位。如果$x$在某一位为$1$，说明子数组$[l,r]$中的所有元素在这一位都应该是$1$，在$[l,r]$区间上加$1$，用差分数组$a$来记录；如果这一位是$0$，那子数组$[l,r]$中的元素就有可能在这一位是$0$（至少有一个$0$）。

求完差分之后再原地求前缀和，这样$a[i]$就是要求数组第$i$个元素在当前二进制位为$1$的条件有多少个（一共有$m$个条件）。

状态定义

$f[i]$表示考虑前$i$个数，第$i$个数在当前二进制位填$0$的方案数（因为方案数就取决于在什么位置可以填$0$，这个状态定义我这种菜鸡是真想不出来）。

规定$f[0]=1$，表示$[1,i-1]$在当前位全部是$1$，有一种方案。

状态转移

如果下标$i$必须填$1$，则$f[i]=0$；否则枚举上一个$0$的位置$j$（即子数组$(j,i)$内所有元素在当前位都是$1$）。设最小的$j$为$minJ$则有状态转移方程$f[i]=f[minJ]+f[minJ+1]+…+f[i-1]$，接下来考虑$i$的转移来源$minJ$。

• 如果$i-1$恰好是某个约束区间$[l,r]$的右端点，且这个区间内至少要有一个$0$，那么转移来源不能小于$l$，否则$[l,r]$就全部是$1$了。
• 如果$i-1$不是某个约束区间$[l,r]$的右端点，那么$f[i]$对应的$minJ$和$f[i-1]$对应的$minJ$相同。

预处理出来一个$maxL[r]$数组，表示至少要有一个$0$的约束区间右端点为$r$时，左端点$l$的最大值。接下来我们只要能够快速得到$f[minJ]+f[minJ+1]+…+f[i-1]$的值就行了，注意到$minJ$是不会回退的，所以用双指针做滑动窗口的优化，用一个变量$sum$来维护这个和即可。

复杂度分析

时间复杂度

一共有$k$位，每位里仅存在有限几次$O(n)$级别的算法（差分数组预处理、前缀和、动态规划+双指针），因此算法整体的时间复杂度为$O(kn)$（这里认为$m$和$n$一个级别，都是$O(n)$）。

空间复杂度

差分数组/前缀和数组$a$、DP数组$f$，以及操作数组$d$都是$O(n)$级别的空间消耗，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 500010, MOD = 998244353;
int n, k, m, a[N], f[N];
vector<PII> d[N];

int main() {
    scanf("%d%d%d", &n, &k, &m);
    for(int i = 1; i <= n; i++) {
        d[i].clear();
    }
    for(int i = 1; i <= m; i++) {
        int l, r, x;
        scanf("%d%d%d", &l, &r, &x);
        d[r].push_back({l, x});
    }
    int ans = 1;
    for(int i = 0; i < k; i++) {
        for(int j = 1; j <= n; j++) {
            f[j] = a[j] = 0;
        }
        f[0] = 1;
        for(int r = 1; r <= n; r++) {
            for(auto&pir: d[r]) {
                int l = pir.first, x = pir.second;
                if(x>>i&1) {
                    // [l,r]必须全1
                    ++a[l], --a[r + 1];
                }
            }
        }
        for(int j = 1; j <= n; j++) {
            a[j] += a[j - 1];
        }
        int p = 0, maxL = 0, sum = 1;
        for(int r = 1; r <= n; r++) {
            while(p < maxL) {
                sum = (sum - f[p++] + MOD)%MOD;
            }
            if(!a[r]) {
                f[r] = sum;
                sum = (sum + f[r]) % MOD;
            }
            for(auto&pir: d[r]) {
                int l = pir.first, x = pir.second;
                if(!(x>>i&1)) {
                    maxL = max(maxL, l);
                }
            }
        }
        int temp = 0;
        for(int j = maxL; j <= n; j++) {
            temp = (temp + f[j]) % MOD;
        }
        ans = (LL)ans*temp%MOD;
    }
    printf("%d\n", ans);
    return 0;
}