P8434 「WHOI-2」D&D

· · 题解

P8434 「WHOI-2」D&D

集合 A 的装饰子集即不被其它任何数包含的子集，a 包含 b 当且仅当 a | b = a，即 b 为 1 的位 a 也为 1。

考虑原序列的装饰子集 S，假设 x\in S，因为 x 不被任何数包含，所以对于任意子串 [l, r]，x 同样不被区间内任何数包含。因此 x 必然作为某个划分子串的装饰子集内的一个元素。所有子串的装饰子集包含 S。

考虑 x\notin S，假设存在 y\in a_i 包含 x。因 x 不可能作为 y 所在子串的装饰子集，故所有子串的装饰子集不包含 S 以外的元素。

这证明了所有子串装饰子集等于 S。

令 l_i 表示使得 [l_i, i] 包含所有 S 内元素的最大的 l_i，显然可以双指针求出。

容易得到 DP f_i 表示 [1, i] 的答案，f_1 = 0。若 l_i 存在，则有转移方程 f_i = \sum\limits_{j = 0} ^ {l_i - 1} f_j，表示将 [j, i](j\leq l_i) 划为子串。前缀和优化即可做到 \mathcal{O}(n)。

求 S 相当容易，只需对每个数 a_i 检查是否存在 a_j\neq a_i 有 a_j 包含 a_i，可以再搞个 DP 算这玩意，也可以直接高维后缀和，相当好写。

时间复杂度 \mathcal{O}(n + V\log V)。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool Mbe;
constexpr int N = 3e6 + 5;
constexpr int mod = 1e9 + 7;
void add(int &x, int y) {x += y, x >= mod && (x -= mod);}
int n, a[N], f[N], g[N], s[N], cnt, buc[N], exist[N];
bool Med;
int main() {
  fprintf(stderr, "%.4lf\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0);
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i], f[a[i]] = exist[a[i]] = 1;
  for(int d = 2, k = 1; k < 1 << 21; d <<= 1, k <<= 1)
    for(int i = 0; i < 1 << 21; i += d)
      for(int j = 0; j < k; j++)
        f[i | j] += f[i | j | k];
  for(int i = 0; i < 1 << 21; i++) cnt += f[i] == 1 && exist[i];
  g[0] = s[0] = 1;
  for(int i = 1, l = 1; i <= n; i++) {
    s[i] = s[i - 1];
    cnt -= !buc[a[i]] && f[a[i]] == 1;
    buc[a[i]]++;
    while(f[a[l]] != 1 || buc[a[l]] > 1) buc[a[l++]]--;
    if(!cnt) g[i] = s[l - 1];
    add(s[i], g[i]);
  }
  cout << g[n] << "\n";
  return cerr << "Time: " << clock() << "\n", 0;
}