CodeForces 1327F - AND Segments
Problem
数位DP:对每一位进行DP然后求积,dp[i]
表示最后的0在第$i$位,且前面所有按位与结果为0的区间都满足。
每次DP前预处理两个内容:
- 当前位置是否必须为1;
- 当前位置左边结束的最后一个按位与为0的区间从哪里开始。
从最后那个区间的左端点开始求和即能得到当前位置的值(如果没有这样的区间则dp值+1)。由于求和太多,需要再用个前缀和。
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;
if (seg[s].second & mask) {
++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>