感谢同机房大神ql12345指导
Solution
因为位运算每一位之间是互不影响的，所以可以按位考虑然后将每一位的方案数相乘得到最终答案。
对于题目中的限制也可以按位拆成小限制，对于 ((l_i,r_i,x_i)) ，如果 (x_i) 这一位上是 (1) ，那么第 ({l_i}) 个数到第 ({r_i}) 数的这一位也全得为 (1) 。
但是 (x) 这一位是 (0) 就不好考虑了，可以考虑DP。
先要预处理出来 (pos) 和 (a) 数组，其中 (pos_i) 为 (i) 之前最靠近 (i) 的 (0) 的位置至少要填在 (pos_i)， (a_i) 为第 (i) 个数这一位是否强制为 (1) 。
其中 (pos) 预处理为：如果 (x_i) 这一位为 (0) ， (pos_{r_i+1}=max(pos_{r_i+1},l_i)) ，因为在 ((l_i,r_i)) 这个区间中至少有一个 (0) ，所以如果要 (r_i+1) 之前全部满足条件，那么至少要在 (l_i) 放一个 (0) 。然后再 (pos_i=max(pos_i,pos_{i-1})) 即可。
(a) 的预处理这里用的是差分，可以做到在 (O(n+m)) 的时间预处理出来。（详情看代码o）
预处理完了，说DP。
设 (f_{i,j}) 表示现在到 (i) 位，其中最后一个 (0) 填在 (j) 且满足条件的方案数，有三种情况的转移：
- 当 (j<pos_i) 时，因为无法满足 (pos) 的条件，所以 (f_{i,j}=0)
- 当 (pos_ileq j<i) 时，因为第 (i) 位只能填 (1) ，不然填 (0) 那么此时 (j=i) ，所以 (f_{i,j}=f_{i-1,j})
- 当 (j=i) 时，如果 (a_i=1) ，那么 (f_{i,j}=0) ，不然 (f_{i,j}=sumlimits_{x=pos_i}^{i-1}f_{i-1,x}) ，因为 (pos_i) 到 (i-1) 的每一种填法都能满足。
我们发现第一维没有什么影响，可以考虑将数组 (f_{i,j}) 简化为 (f_j) ，因为 (pos_i) 是有单调性的，所以可以维护一个 (sum) ，及时更新。
时间复杂度： (O(kcdot(n+m)))
Code
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int N=5e5+10,mod=998244353;
int n,k,m,l[N],r[N],x[N],f[N];
int pos[N],a[N];//pos表示i之前最后一个0的位置 a是这一位是否强制选1
inline int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
return x*f;
}
inline void add(int &x,const int y){ x=(x+y>=mod?x+y-mod:x+y);}
inline void sub(int &x,const int y){ x=(x<y?x-y+mod:x-y);}
inline void init(int p){ //p是你按位DP到哪一位了
for(int i=1;i<=n+1;i++) pos[i]=a[i]=0;
for(int i=1;i<=m;i++)
if((x[i]>>p)&1) ++a[l[i]],--a[r[i]+1];
else pos[r[i]+1]=max(pos[r[i]+1],l[i]);
for(int i=2;i<=n+1;i++)
a[i]+=a[i-1],pos[i]=max(pos[i],pos[i-1]);
}
inline void dp(){
for(int i=0;i<=n+1;i++) f[i]=0;
f[0]=1;
int sum=1,l=0;
for(int i=1;i<=n+1;i++){
while(l<pos[i]) sub(sum,f[l]),f[l]=0,++l;
f[i]=a[i]?0:sum,add(sum,f[i]);
}
}
int main(){
n=read(),k=read(),m=read();
for(int i=1;i<=m;i++) l[i]=read(),r[i]=read(),x[i]=read();
int ans=1;
for(int p=0;p<k;p++){
init(p);
dp();
ans=1ll*ans*f[n+1]%mod;
}
printf("%d
",ans);
return 0;
}