# CodeForces 1327F - AND Segments

2020-03-26 16:37 CST

## Problem

• 当前位置是否必须为1；
• 当前位置左边结束的最后一个按位与为0的区间从哪里开始。

## Solution

#include <iostream>
#include <cstring>
using namespace std;
const long long mod = 998244353;

int n = 0, k = 0, m = 0;
pair<pair<int, int>, unsigned> seg[500005] = {};
int pre[500005] = {};
int one[500005] = {};
long long dp[500005] = {};

long long solve(unsigned bit) {
memset(pre, 0, sizeof(pre));
memset(one, 0, sizeof(one));
memset(dp, 0, sizeof(dp));

unsigned mask = 1U << bit;
for (int s = 0; s < m; ++s) {
int l = seg[s].first.first;
int r = seg[s].first.second;
++one[l], --one[r + 1];
} else {
pre[r + 1] = max(pre[r + 1], l);
}
}

int left = 0, count = 0;
for (int i = 1; i <= n + 1; ++i) {
long long cur = 0;
count = count + one[i];
left = max(left, pre[i]);
if (count > 0) {
cur = 0;
} else {
if (left == 0) {
cur = dp[i - 1] + 1;
} else {
cur = dp[i - 1] - dp[left - 1];
}
}
dp[i] = (dp[i - 1] + cur) % mod;
}
return (dp[n + 1] - dp[n] + mod) % mod;
}

int main() {
scanf("%d %d %d", &n, &k, &m);
for (int i = 0; i < m; ++i) {
auto &p = seg[i];
scanf("%d %d %u", &p.first.first, &p.first.second, &p.second);
}

long long ans = 1;
for (unsigned bit = 0; bit < k; ++bit) {
ans = (ans * solve(bit)) % mod;
}
printf("%lld\n", ans);
return 0;
}

<EOF>