Codeforces Round 1120 (Div 2) - C2. Floor of MEX (Hard Version)

C2. Floor of MEX (Hard Version)

time limit per test: 2 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

This is the hard version of the problem. The difference between the versions is that in this version, you need to count how many sets satisfy the constraints. You can hack only if you solved all versions of this problem.

Let

$$f(S,x)=\text{mex}\left(\left\{\left\lfloor \frac{y}{x}\right\rfloor : y\in S\right\}\right),$$

where $S$ is a set of non-negative integers and $x$ is a positive integer. $^{\text{∗}}$

Farmer John chooses a (possibly empty) subset $A\subseteq \{0,1,\ldots,n-1\}$. He then constructs an array $a$ of length $n$, where $a_k = f(A,k)$ for every $1\le k\le n$.

Bessie, being a mischievous cow, hides the set $A$. Farmer John is left only with the array $a_1,a_2,\ldots,a_n$.

Your task is to count how many sets (including the empty set) $B \subseteq \{0,1,\ldots,n-1\}$ such that $f(B,k)=a_k$ for every $1 \le k \le n$. Since the number can be very large, output it modulo $10^9+7$. Farmer John will only give you arrays where such a $B$ exists.

$^{\text{∗}}\operatorname{mex}(c)$ denotes the minimum excluded (MEX)$^{\text{∗}}$ of the collection $c$. (in this case, the minimum non-negative integer not present in the set)

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$).

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \leq a_i \leq n$).

You will only be given arrays where there exists $B \subseteq \{0,1,\ldots,n-1\}$ such that $f(B,k)=a_k$ for every $1 \le k \le n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each testcase, output one number, the number of sets $B$ that satisfy the constraints modulo $10^9 + 7$.

Example

Input

3
6
0 3 2 2 2 1
5
2 1 1 1 1
6
1 2 1 1 1 1

Output

6
1
1

Note

For the first testcase, the $6$ subsets are

$$\{1, 2, 5\}, \{1, 3, 5\}, \{1, 2, 3, 5\}, \{1, 2, 4, 5\}, \{1, 3, 4, 5\}, \{1, 2, 3, 4, 5\}.$$

For the second testcase, the only subset that satisfies $f(B,k) = a_k$ for every $1 \le k \le n$ is $\{0, 1\}$.

题解

题目分析

给定一个长度为 $n$ 的数组 $a_1, a_2, \ldots, a_n$。要求计算有多少个子集 $B \subseteq \{0, 1, \ldots, n-1\}$，满足对所有 $1 \le k \le n$，都有：
$$f(B, k) = \text{mex}\left(\left\{ \left\lfloor \frac{y}{k} \right\rfloor : y \in B \right\}\right) = a_k$$
题目保证至少存在一个满足条件的集合 $B$。答案对 $10^9 + 7$ 取模。

---

核心观察与条件转化

根据 $\text{mex}$（最小未出现的非负整数）的定义，$f(B, k) = a_k$ 等价于以下两个条件对所有 $1 \le k \le n$ 同时成立：

1. 必须出现：对于所有 $0 \le j < a_k$，$j \in \{\lfloor y/k \rfloor : y \in B\}$，即：
   $$B \cap [j \cdot k, (j+1)k - 1] \neq \emptyset$$
   换句话说，在每个区间 $[j \cdot k, (j+1)k - 1]$ 中，$B$ 必须至少包含一个元素。

2. 禁止出现：$a_k \notin \{\lfloor y/k \rfloor : y \in B\}$，即：
   $$B \cap [a_k \cdot k, (a_k+1)k - 1] = \emptyset$$
   换句话说，任何落在区间 $[a_k \cdot k, (a_k+1)k - 1]$ 内的数都绝对不能在 $B$ 中。

对于大于 $a_k$ 的值，$\text{mex}$ 的定义对其没有直接限制（可以出现也可以不出现）。

---

解题思路

第一步：找出所有合法可选的元素

任何属于某个禁止区间的元素都不能选入 $B$。
由于每个 $k \in [1, n]$ 至多贡献一个禁止区间 $[a_k \cdot k, (a_k+1)k - 1] \cap [0, n-1]$，一共有至多 $n$ 个禁止区间。
我们可以利用差分数组（Difference Array）在 $O(n)$ 时间内标记出所有被禁止的数。

标记完成后，将所有未被禁止的数按升序排列，记为数组 $\text{allowed} = [x_1, x_2, \ldots, x_m]$，其大小为 $m$（$m \le n$）。

• 特殊情况：若 $m = 0$，根据题目保证一定有解，唯一的解为空集 $B = \emptyset$（此时必有所有 $a_k = 0$），答案为 $1$。

第二步：将条件转化为下标区间覆盖

对于每个 $k \in [1, n]$ 以及每个 $0 \le j < a_k$（满足 $j \cdot k < n$），我们需要 $B$ 至少包含一个落在原区间 $[L, R] = [j \cdot k, \min(n-1, (j+1)k - 1)]$ 的元素。

注意到 $\text{allowed}$ 数组是有序的，原区间 $[L, R]$ 内的所有可选元素在 $\text{allowed}$ 中必定占据一个连续的下标区间 $[l, r]$（$1 \le l \le r \le m$）：

• $l$ 是落在 $[L, R]$ 中的第一个可选元素的下标；
• $r$ 是落在 $[L, R]$ 中的最后一个可选元素的下标。

我们可以预处理出：

• $\text{next\_allowed}[x]$：大于等于 $x$ 的第一个可选元素的下标；
• $\text{prev\_allowed}[x]$：小于等于 $x$ 的最后一个可选元素的下标。

从而每个限制条件都可以在 $O(1)$ 时间内转化为：在 $\text{allowed}$ 数组的下标区间 $[l, r]$ 内至少选一个元素。

区间数量上界：
因为 $B \subseteq \{0, 1, \ldots, n-1\}$，所以 $\lfloor y/k \rfloor \le \lfloor (n-1)/k \rfloor$。因此集合中的最大值不超过 $\lfloor (n-1)/k \rfloor$，这说明 $\text{mex} \le \lfloor (n-1)/k \rfloor + 1$。
因此每个 $k$ 最多产生 $O(n/k)$ 个必须覆盖的区间。区间总数为：
$$\sum_{k=1}^n a_k \le \sum_{k=1}^n \left(\frac{n}{k} + 1\right) = O(n \log n)$$

第三步：动态规划计数

现在问题转化为：

给定 $m$ 个点 $1, 2, \ldots, m$，以及若干个区间 $[l_i, r_i]$，求有多少个子集 $S \subseteq \{1, \ldots, m\}$，使得每个区间都至少包含 $S$ 中的一个点。

引入虚拟端点 $0$ 和 $m+1$，令 $p_0 = 0, p_{k+1} = m+1$，设选中的下标集合为：
$$0 = p_0 < p_1 < p_2 < \dots < p_k < p_{k+1} = m + 1$$
一个区间 $[l_i, r_i]$ 没有被覆盖，当且仅当它完全掉进某个相邻两点的空隙中，即存在某个 $t$ 使得：
$$p_t < l_i \le r_i < p_{t+1}$$
因此，选出的序列合法当且仅当：对于每一对相邻元素 $u < v$，都不存在区间满足 $u < l_i \le r_i < v$。
对固定的 $v$，这要求所有满足 $r_i < v$ 的区间必须有 $u \ge l_i$。即：
$$u \ge L(v) = \max \{ l_i : r_i < v \}$$
（若没有满足 $r_i < v$ 的区间，则 $L(v) = 0$）。

定义 $dp[v]$ 为以 $v$ 结尾的合法序列方案数，则状态转移方程为：
$$dp[v] = \sum_{u = L(v)}^{v - 1} dp[u]$$
初始状态为 $dp[0] = 1$，最终答案为 $dp[m + 1]$。

由于 $L(v) = \max(L(v - 1), \max_{\{i : r_i = v - 1\}} l_i)$ 单调不降，转移区间 $[L(v), v - 1]$ 是连续的，可以使用前缀和优化在 $O(1)$ 时间内完成每次转移！

---

复杂度分析

• 时间复杂度：
  • 差分找禁止元素与预处理：$O(n)$。
  • 枚举所有要求覆盖的区间：$O(\sum_{k=1}^n a_k) = O(n \log n)$。
  • 动态规划求解：$O(m) = O(n)$。
  • 总体时间复杂度为 $O(n \log n)$，在 $\sum n \le 10^5$ 的限制下，运行时间在 0.05 秒以内，极其高效。
• 空间复杂度：$O(n)$。

---

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 1000000007;

void solve() {
    int n;
    if (!(cin >> n)) return;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 1. 利用差分数组标记所有禁止出现的元素
    vector<int> diff(n + 2, 0);
    for (int k = 1; k <= n; ++k) {
        long long ak = a[k - 1];
        long long start = ak * k;
        if (start < n) {
            long long end = min((long long)n - 1, (ak + 1) * k - 1);
            diff[start]++;
            diff[end + 1]--;
        }
    }

    vector<bool> forbidden(n, false);
    int cur = 0;
    for (int i = 0; i < n; ++i) {
        cur += diff[i];
        if (cur > 0) {
            forbidden[i] = true;
        }
    }

    // 2. 提取所有可选元素并离散化为 1-based 索引
    vector<int> allowed;
    allowed.reserve(n);
    for (int i = 0; i < n; ++i) {
        if (!forbidden[i]) {
            allowed.push_back(i);
        }
    }

    int m = allowed.size();
    if (m == 0) {
        // 只能选空集，且题目保证有解
        cout << 1 << "\n";
        return;
    }

    vector<int> val_to_idx(n, -1);
    for (int i = 0; i < m; ++i) {
        val_to_idx[allowed[i]] = i + 1; // 1-based 索引
    }

    // 预处理每个位置之后/之前的第一个可选元素对应的下标
    vector<int> next_allowed(n, -1);
    int last = -1;
    for (int i = n - 1; i >= 0; --i) {
        if (!forbidden[i]) {
            last = val_to_idx[i];
        }
        next_allowed[i] = last;
    }

    vector<int> prev_allowed(n, -1);
    last = -1;
    for (int i = 0; i < n; ++i) {
        if (!forbidden[i]) {
            last = val_to_idx[i];
        }
        prev_allowed[i] = last;
    }

    // 3. 转化所有限制区间：求每个右端点 r 对应的最大左端点 max_left[r]
    vector<int> max_left(m + 2, 0);
    for (int k = 1; k <= n; ++k) {
        int ak = a[k - 1];
        for (int j = 0; j < ak; ++j) {
            long long L = 1LL * j * k;
            if (L >= n) break;
            long long R = min((long long)n - 1, 1LL * (j + 1) * k - 1);
            int l_idx = next_allowed[L];
            int r_idx = prev_allowed[R];
            if (l_idx != -1 && l_idx <= r_idx) {
                if (l_idx > max_left[r_idx]) {
                    max_left[r_idx] = l_idx;
                }
            }
        }
    }

    // 4. 前缀和优化 DP
    vector<int> dp(m + 2, 0);
    vector<int> pref(m + 2, 0);
    dp[0] = 1;
    pref[0] = 1;

    int cur_max = 0;
    for (int v = 1; v <= m + 1; ++v) {
        cur_max = max(cur_max, max_left[v - 1]);
        int l_b = cur_max;
        int r_b = v - 1;
        if (l_b <= r_b) {
            int ways = pref[r_b];
            if (l_b > 0) {
                ways = (ways - pref[l_b - 1] + MOD) % MOD;
            }
            dp[v] = ways;
        } else {
            dp[v] = 0;
        }
        pref[v] = (pref[v - 1] + dp[v]) % MOD;
    }

    cout << dp[m + 1] << "\n";
}

int main() {
    // 快速 I/O
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}