RMQ Similar Sequence(笛卡尔树)

描述

传送门:2018 Multi-University Training Contest 1 - Problem H

Chiaki has a sequence $A={a_1,a_2,\dots,a_n}$. Let $\mathbf{RMQ}(A, l, r)$ be the minimum $i$ ($l \le i \le r$) such that $a_i$ is the maximum value in $a_l, a_{l+1}, \dots, a_{r}$.

Two sequences $A$ and $B$ are called RMQ Similar, if they have the same length n and for every $1 \le l \le r \le n$, $\mathbf{RMQ}(A, l, r) = \mathbf{RMQ}(B, l, r)$.

For a given the sequence $A={a_1,a_2,\dots,a_n}$, define the weight of a sequence $B={b_1,b_2,\dots,b_n}$ be $\sum\limits_{i=1}^{n} b_i$ (i.e. the sum of all elements in $B$) if sequence $B$ and sequence $A$ are RMQ Similar, or $0$ otherwise. If each element of $B$ is a real number chosen independently and uniformly at random between $0$ and $1$, find the expected weight of $B$.

Input

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($1 \le n \le 10^6$) – the length of the sequence.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) denoting the sequence.
It is guaranteed that the sum of all $n$ does not exceed $3 \times 10^6$.

Output

For each test case, output the answer as a value of a rational number modulo $10 ^ 9 + 7$.
Formally, it is guaranteed that under given constraints the probability is always a rational number pq ($p$ and $q$ are integer and coprime, $q$ is positive), such that $q$ is not divisible by $10 ^ 9 + 7$. Output such integer a between $0$ and $10 ^ 9 + 6$ that $p −aq$ is divisible by $10 ^ 9 + 7$.

Sample Input

1
2
3
4
5
6
7
3
3
1 2 3
3
1 2 1
5
1 2 3 2 1

Sample Output

1
2
3
250000002
500000004
125000001

思路

  • 考虑到$B$中的元素是实数,因此元素相同的概率为$0$。可以假设是一个排列。
  • $[0,1]$内随机一个实数的期望是$\frac{1}{2}$,那么一个排列的期望就是$\frac{n}{2}$。
  • 问题等价于:$B$为$n$的一个全排列,满足RMQ形态和$A$相同的方案数$s$。那么答案就是$\frac{s}{n!} \times \frac{n}{2}$。
  • RMQ形态相同即两者的笛卡尔树形态相同。
  • 符合条件的数量就是$B$数组元素的全序数量,即树的拓扑序的数量:$\frac{n!}{\prod sz_i}$。
  • 于是答案为:$\frac{n}{2\prod sz_i}$ ($sz_i$表示以$i$为根的子树的大小)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
const int N = 1 << 20;

int main()
{
vector<int> inv(N, 1);
for (int i = 2; i < N; i++) inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
int T;
scanf("%d", &T);
while (T--)
{
int n;
scanf("%d", &n);
vector<int> a(n);
for (auto& t : a) scanf("%d", &t);
vector<int> lson(n, -1), rson(n, -1), fa(n, -1);
stack<int> s;
for (int i = 0; i < n; i++)
{
int last = -1;
while (!s.empty() && a[i] > a[s.top()]) last = s.top(), s.pop();
if (!s.empty()) rson[s.top()] = i, fa[i] = s.top();
lson[i] = last;
if (~last) fa[last] = i;
s.push(i);
}

vector<int> sz(n, 1);
int res = inv[2];
function<void(int)> dfs = [&](int u) {
if (~lson[u]) dfs(lson[u]), sz[u] += sz[lson[u]];
if (~rson[u]) dfs(rson[u]), sz[u] += sz[rson[u]];
res = 1LL * res * inv[sz[u]] % mod;
};

int rt;
for (int i = 0; i < n; i++)
if (!~fa[i]) rt = i;
dfs(rt);
int ans = 1LL * n * res % mod;
printf("%d\n", ans);
}
}
捐助作者
0%