洛谷 U140360 购物清单
题目背景
光阴似箭，日月如梭。不知不觉间，时间已经快进到SeawaySeawa**y带着一家老婆小孩过上了幸福快乐的生活......
题目描述
当然，虽然生活的大体格调是幸福而快乐的，但是SeawaySeawa**y依然躲不过生活中的柴米油盐酱醋茶等琐碎小事。其中，最让他为难的便是半个月一次的采购了......
每次采购，SeawaySeawa**y要列出一份购物清单，并按清单顺序购入下半个月所需要的nn件物品。超市一共有2k2*k*种物品。为了方便，Seaway*S**e**a**w**a**y*把这些物品从0-2k-10−2k−1编号。现在问题在于，SeawaySeawa**y每次采购都要满足老婆孩子的mm条要求，这些要求形如(l,r,x)(l,r,x)。其意义是：假设SeawaySeawa**y的购物清单是一个数列aa，那么对于第ii条要求(l_i,r_i,x_i)(l**i,r**i,x**i)，SeawaySeawa**y的购物清单必须满足：a[l_i] &a[l_i+1]&cdots&a[r_i]=x_ia[l**i]&a[l**i+1]&⋯&a[r**i]=x**i。其中&&是按位与运算。SeawaySeawa**y的购物清单合法，当且仅当它能同时满足老婆孩子的mm条要求。
SeawaySeawa**y在经过严密地思考后发现，这样的清单不唯一。所以他想请你帮他统计：对于这mm条要求，有多少种清单合法。我们定义两个清单a,ba,b不同，当且仅当存在至少一个位置ii使得a_i eq b_ia**i�=b**i。答案对998,244,353998,244,353取模。
输入格式
从文件list.inlis**t.i**n中读入数据。
第一行三个整数n,m,kn,m,k，意义如题目描述所示。
接下来的mm行，每行三个整数l_i,r_i,x_il**i,r**i,x**i，描述一个限制(l,r,x)(l,r,x)。
输出格式
输出到文件list.outlis**t.out中。
输出一行一个整数ansans，表示满足条件的清单种数按要求取模后的结果。
命题背景：
这题实在是比较狗。
u1s1，一开始拿到的时候只推出来了性质，至于实现想破脑袋都没想明白。还是太菜了。
本来没想拿这道题，但是一看好像和动物园那道题挺像。位运算+DP都是热门考点，所以就拿来考了。
感觉像黑题。但是可能也只是因为我菜吧。不好意思让洛谷改评分了。所以只在自己的题里改了评分。
题解：
对于这种题目，一般都是从位运算按位独立这里入手。这题也不例外。
既然位运算相互独立，且本题只有与运算，那么很容易得出这样的一个性质：对于某个约束区间([l,r])的约束值(x)，对(x)二进制拆分，(x)的某位如果为1，那么这个区间的数的对应位全部为1。反之如果为0，那么这个区间的数的对应位至少有一个为0.
推到此处狂喜，然后觉得可以用排列组合来做，或者是个容斥什么的。但是这是不现实的，因为区间的并实在太难处理了。
但是想到排列组合却能给我们一个启发。那就是计数原理的乘法原理。既然这些位都是互相独立的，那么每位的合法方案的方案数乘到一起就是答案。
每位的合法方案数......既然排列组合容斥啥的都没戏，那就只能考虑DP，毕竟对于计数类问题我们也并没有什么其他的方法。这个不行就试那个。
设(dp[i])表示处理到前i个数，且第(i)个数的对应位为0的方案数。不需要再开一维来存第几位，每次做的时候清空即可。
那么很显然，如果某个约束条件使得一个区间内的数字的对应位为1，那么这段区间的dp值应该都为0.
这个0可以用多种方法维护，我选择的是差分。
如果某个约束条件使得一个区间内的数字的对应位至少有一个为0，这种情况该怎么办呢？
分类讨论：首先如果某个区间的右端点比当前枚举到的点大，那么这个条件已经被满足，不用考虑。
如果某个区间([l,r])的右端点比当前枚举到的点(i)小，那么这个条件要被满足，一定会在这里填一个0，所以就可以转移：
为什么要到(i-1)而不是到(r)呢？因为我们统计的(dp[i])已经被叫做合法方案，所以在这个区间的都合法，也就都要统计进来。
那么我们敏锐地发现，这样统计会导致很多区间被重复算进去。那么我们为了不重复统计，就采用一个(lmx[i])数组，表示在(i)左边最大的(l)值。这样的话每次转移只会从最大的开始累加，而前面的已经在前面的转移被累加过了。这样就完成了这道题。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=5e5+5;
const int mod=998244353;
int n,k,m;
int l[maxn],r[maxn],x[maxn];
int lmx[maxn],dp[maxn],cf[maxn];
int calc(int a)
{
memset(lmx,0,sizeof(lmx));
memset(cf,0,sizeof(cf));
memset(dp,0,sizeof(dp));
for(int i=1;i<=m;i++)
{
if(x[i]>>a&1)
cf[l[i]]++,cf[r[i]+1]--;
else
lmx[r[i]]=max(lmx[r[i]],l[i]);
}
for(int i=1;i<=n+1;i++)
{
lmx[i]=max(lmx[i],lmx[i-1]);
cf[i]+=cf[i-1];
}
int sum=1,j=0;
dp[0]=1;
for(int i=1;i<=n+1;i++)
{
if(cf[i])
{
dp[i]=0;
continue;
}
while(j<lmx[i-1])
{
sum=(sum-dp[j]+mod)%mod;
j++;
}
dp[i]=sum;
sum=(sum+dp[i])%mod;
}
return dp[n+1];
}
int main()
{
scanf("%d%d%d",&n,&k,&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&l[i],&r[i],&x[i]);
int ans=1;
for(int i=0;i<k;i++)
ans=1ll*ans*calc(i)%mod;
printf("%d
",ans);
return 0;
}