Codeforces 1327F AND Segments
题目链接
https://codeforces.com/contest/1327/problem/F
题目大意
有 $m$ 个条件，$(l_i, r_i, x_i)$ ，表示 $a[l_i] \& a[l_i + 1] \& \dots \& a[r_i] = x_i$。问有多少种填写长度为 $n$ 的数组 $a$ 的方法，使得满足这 $m$ 个条件且有 $0 \le a_i < 2^k$。
题目分析
显然对于每一位都可以分开考虑，如果有 $(l, r)$ 的答案是 $1$，那么显然 $l$ 到 $r$ 所有的数字都需要填 $1$。否则的话，可以考虑使用 $DP$ 来解决问题。
设 $f[i]$ 是点 $i$ 填 $0$ 的答案个数。对于一段 $(l, r)$ 的限制，那么显然 $r + 1$ 的转移会受到限制，因为 $l$ 到 $r$ 之间必须有一个 $0$ 。因此可以使用双指针和前缀和来维护转移，这样一来就可以解决问题了。
代码
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int maxn = 5e5 + 5;
int n, m, k;
int L[maxn], R[maxn], X[maxn];
int sa[maxn];
int g[maxn], h[maxn];
long long sum[maxn], f[maxn];
long long calc(long long l, long long r){
if(l == 0) return sum[r];
return (sum[r] - sum[l - 1] + mod) % mod;
}
int main(){
int i, j;
long long ans = 1;
scanf("%d%d%d", &n, &k, &m);
for(i=1;i<=m;i++){
scanf("%d%d%d", &L[i], &R[i], &X[i]);
}
for(j=0;j<k;j++){
for(i=1;i<=n+1;i++) sa[i] = sum[i] = f[i] = h[i] = 0;
for(i=1;i<=m;i++){
if((X[i] >> j) & 1){
sa[L[i]]++;
sa[R[i] + 1]--;
}
}
for(i=1;i<=n;i++) sa[i] += sa[i - 1];
for(i=1;i<=m;i++){
if(!((X[i] >> j) & 1)){
h[R[i] + 1] = max(h[R[i] + 1], L[i]);
}
}
f[0] = 1;
sum[0] = 1;
int l = 0;
for(i=1;i<=n;i++){
l = max(h[i], l);
sum[i] = sum[i - 1];
if(sa[i]) continue;
f[i] = calc(l, i - 1);
sum[i] = (sum[i] + f[i]) % mod;
}
l = max(h[n + 1], l);
ans = ans * (calc(l, n)) % mod;
}
printf("%lld\n", ans);
return 0;
}