题目链接
题意分析
由于这道题只涉及了二进制运算中的按位与运算 这种情况一般都是对于每一位进行方案统计
由于是方案统计 所以我们可以使用dp计数
首先 对于一个限制(li,ri,xi) 如果对于一位p(0≤p<k)
xi在这一位是1 那么序列a在这一位满足[li,ri]均为1
xi在这一位是0 那么序列a在这一位满足[li,ri]至少有一个是0
第一种情况好做 第二种情况不好处理
第一种情况 我们使用差分进行区间覆盖 然后判断这一位是否必须填1
第二种情况
我们预处理出来一个数组pos pos[i]表示第i位(不包括i)之前最靠近i的填0的位置至少要在pos[i]这个位置
一开始的时候 如果一个限制(li,ri,xi)中xi这一位是0 那么pos[ri+1]=max(pos[ri+1],li)
因为我们要求[li,ri]之间至少一位是0 所以ri+1前面填0的话至少需要在li
同时由于可能存在多个区间共用右端点的情况 所以我们需要共同取max
接下来 我们还需要做一遍pos[i]=max(pos[i],pos[i-1]) 为了针对如下的情况
我们用dp[i][j]表示序列第i位 i之前最靠右的填0的位置是j的合法方案数
1.j<pos[i] dp[i][j]=0
2.pos[i]≤j<i dp[i][j]=dp[i-1][j]
3.j=i 如果当前i这一位必须填1 那么dp[i][j]=0 否则的话
\[dp[i][j]=\sum_{k=pos[i]}^{j-1}dp[i-1][k]
\]
我们发现 其实dp[i][j]第一维i只和i-1有关 所以我们可以删第一维 同时由于pos[i]单调递增 所以使用一个变量sum维护区间和
CODE:
#include<bits/stdc++.h>
#define M 1008611
#define MOD 998244353
using namespace std;
int n,m,k;
struct Line
{
int le,ri,val;
}e[M];
int d[M],num[M];
int pos[M];
long long dp[M];
long long ans=1LL;
long long solve(int x)
{
for(int i=1;i<=n+1;++i)
{
d[i]=num[i]=0;pos[i]=0;dp[i]=0;
}
for(int i=1;i<=m;++i)
if(e[i].val&(1<<x)) d[e[i].le]++,d[e[i].ri+1]--;
else pos[e[i].ri+1]=max(pos[e[i].ri+1],e[i].le);
for(int i=1;i<=n;++i)
{
d[i]+=d[i-1];
if(d[i]>0) num[i]=1;
}
for(int i=1;i<=n+1;++i) pos[i]=max(pos[i],pos[i-1]);
long long tmp=1;int nowat=0;
dp[0]=1LL;
for(int i=1;i<=n+1;++i)
{
while(nowat<pos[i]) tmp=(tmp-dp[nowat]+MOD)%MOD,dp[nowat++]=0;
dp[i]=(num[i] ? 0:tmp),tmp=(tmp+dp[i])%MOD;
}
// printf("now is %lld\n",dp[n+1]);
return dp[n+1];
}
int main()
{
scanf("%d%d%d",&n,&k,&m);
for(int i=1;i<=m;++i) scanf("%d%d%d",&e[i].le,&e[i].ri,&e[i].val);
for(int i=0;i<k;++i) ans=ans*solve(i)%MOD;
printf("%lld\n",ans);
return 0;
}