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>