好题，有几个要注意的地方：
1.特判无解的情况
2.如果大区间包含一个小区间，且这两个区间and结果都是0，那么只要考虑小区间就可以了
/* 开数组f[i][j]=1表示第i个数第j位必须取1，这部分可以预处理 然后对于每一位单独考虑，可以得到一个长为n的一维数组，有些段必须为1，有些段至少要有一个0 dp[i][0|1]表示到了第i位，选择填0|1的方案数 如果i位必须选1，那么dp[i][0]=0 反之dp[i][0]=dp[i-1][0|1] 如果i==rj,即碰到了右端点，那么dp[i][1]=sum{dp[lj..i-1][0]} 即这一段必须有个0 */ #include<bits/stdc++.h> using namespace std; #define mod 998244353 #define N 500005 #define ll long long ll n,k,m,ans; struct Seg{ ll l,r,x; }s[N]; int cmp(Seg a,Seg b){ if(a.r==b.r)return a.l<b.l; return a.r<b.r; } int f[N][35],l[N]; ll dp[N][2],sum[N]; void solve(int p){ memset(dp,0,sizeof dp); memset(sum,0,sizeof sum); memset(l,0,sizeof l); int Max=0; for(int i=1;i<=m;i++)//确定所有r对应的l，只取最靠右的l if(!(s[i].x>>p & 1)) Max=max((ll)Max,s[i].l),l[s[i].r]=Max; if(f[1][p]){ dp[1][0]=0;dp[1][1]=1; }else if(l[1]){ dp[1][0]=1;dp[1][1]=0; }else dp[1][0]=dp[1][1]=1; sum[1]=dp[1][0]; for(int i=2;i<=n;i++){ if(f[i][p])dp[i][0]=0; else dp[i][0]=(dp[i-1][0])+dp[i-1][1]%mod; if(l[i])dp[i][1]=(sum[i-1]-sum[l[i]-1]+mod)%mod; else dp[i][1]=(dp[i-1][0]+dp[i-1][1])%mod; sum[i]=(sum[i-1]+dp[i][0])%mod; } ans=(dp[n][0]+dp[n][1])%mod*ans%mod; } void prework(){ for(int i=1;i<=m;i++){ for(int j=0;j<k;j++)if(s[i].x>>j & 1){ f[s[i].l][j]++; f[s[i].r+1][j]--; } } for(int i=1;i<=n;i++) for(int j=0;j<k;j++) f[i][j]+=f[i-1][j]; } map<pair<int,int>,int>mp; int main(){ cin>>n>>k>>m; int flag=0; for(int i=1;i<=m;i++){ scanf("%lld%lld%lld",&s[i].l,&s[i].r,&s[i].x); pair<int,int>p=make_pair(s[i].l,s[i].r); if(mp.find(p)!=mp.end() && mp[p]!=s[i].x){ flag=1; }else mp[p]=s[i].x; } if(flag){puts("0");return 0;} prework(); sort(s+1,s+1+m,cmp); ans=1; for(int i=0;i<k;i++) solve(i); cout<<ans<<' '; } /* 11 1 5 1 3 0 2 6 1 5 8 0 7 11 0 10 11 0 20 10 2 13 14 182 12 15 6 */