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;
}
#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;
}
#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;
}