自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:39:01，当前版本为作者最后更新于2022-07-10 13:55:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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