HDU 6305 RMQ Similar Sequence（笛卡爾樹+線性求逆元+期望）

題目連結

RMQ Similar Sequence

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 255535/255535 K (Java/Others)

Total Submission(s): 999    Accepted Submission(s): 327

Problem Description

Chiaki has a sequence A={a1,a2,…,an}. Let RMQ(A,l,r) be the minimum i (l≤i≤r) such that ai is the maximum value in al,al+1,…,ar.

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

For a given the sequence A={a1,a2,…,an}, define the weight of a sequence B={b1,b2,…,bn} be ∑i=1nbi (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≤n≤106) -- the length of the sequence.

The second line contains n integers a1,a2,…,an (1≤ai≤n) denoting the sequence.

It is guaranteed that the sum of all n does not exceed 3×106.

Output

For each test case, output the answer as a value of a rational number modulo 109+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 109+7. Output such integer a between 0 and 109+6 that p−aq is divisible by 109+7.

Sample Input

3

3

1 2 3

3

1 2 1

5

1 2 3 2 1

Sample Output

250000002

500000004

125000001

題意：

給你一個長度為n的A序列，定義了一種相似關系RMQ-similar——當對于任意的l,r，RMQ(A,l,r)=RMQ(B,l,r)，則稱A,B相似(這裡的RMQ指的是[l,r]裡面的最大值的下标，并且有多個最大值下取最小的下标)

現在B 都是[0,1]之間的實數,B也是長度為n的序列，定義序列B的權值是Σbi (i∈[1,n])，問你B與A相似的期望的權值是多少

解析:

先上大佬的題解

• 考慮到B中的元素是實數，是以元素相同的機率為0。可以假設是一個排列。
• [0,1]内随機一個實數的期望是1/2，那麼一個排列的期望就是n/2。
• 問題等價于：B為n的一個全排列，滿足RMQ形态和AA相同的方案數s。那麼答案就是

  

  。
• RMQ形态相同即兩者的笛卡爾樹形态相同。
• 符合條件的數量就是B數組元素的全序數量，即樹的拓撲序的數量s：

  

  。
• 于是答案為：

  

  (sizei表示以i為根的子樹的大小）

下面是解釋機率的東西

首先在[0,1]裡面取兩個任意實數，這兩個任意實數相等的機率為0=1/∞

那麼對于一個n個數的排列，排列的數是任意從[0,1]取一個實數。

對于取一個數的期望1/2(因為[0,1]裡面是均勻分布，從均勻分布的數學期望是(a+b)/2)

并且這裡各個位置從[0,1]内取數是互相獨立的，是以和的期望就是期望的和=n/2

1-n的全排列有n!種情況，是以任意一個全排列的機率是1/(n!)

也可以這樣了解，當取第一個數時，n個數種取一個數的機率時1/n，取第二個數時的機率時1/(n-1)......

是以1-n中的一個排列的機率是1/n!

然後假設滿足與A相似的B的排列數量是s個,那麼任意一個1-n的排列滿足條件的機率是

最後答案就是n個位置取數的期望*排列滿足條件的機率=

然後是笛卡爾樹的講解笛卡爾樹

然後聽了dls的講解，發現上面的你不知道也沒事，他直接把求滿足條件的排列的機率如何計算講出來了

也就是

這一部分，是以至于樹的拓撲序....至今也不知道是什麼東西........。

簡單概括dls說的滿足條件的機率就是每一個位置要滿足條件的機率就是1/(以該位置為根的笛卡爾樹的子樹的大小)

也就是上面那個

，然後再把笛卡爾樹的每一棵子樹的機率乘起來，就是滿足條件的排列的機率了。

#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#define mp make_pair
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
using namespace std;
typedef pair<int ,int> PII;
typedef long long ll;
const int MAXN = 1e6+100;
const ll MOD =1e9+7;
int n;
int a[MAXN];
int l[MAXN],r[MAXN],vis[MAXN];
int stk[MAXN],top;
int size=1;
ll inv[MAXN];

ll dfs(int rt)
{
	if(l[rt]==0&&r[rt]==0) return 1;
	ll num=1;
	if(l[rt]) num+=dfs(l[rt]);
	if(r[rt]) num+=dfs(r[rt]);
	size=size*inv[num]%MOD;
	return num;
}


void build() {   //O(n)建笛卡爾樹
	int top=0;
	rep(i,1,n+1) l[i]=0,r[i]=0,vis[i]=0;
	rep(i,1,n+1) {
		int k=top;
		while (k>0&&a[stk[k-1]]<a[i]) --k;
		if (k) r[stk[k-1]]=i;
		if (k<top) l[i]=stk[k];
		stk[k++]=i;
		top=k;
	}
	rep(i,1,n+1) vis[l[i]]=vis[r[i]]=1;
	int rt=0;
	rep(i,1,n+1) if (vis[i]==0) rt=i;  //找根
	dfs(rt);
}

int main()
{
	int t;
	inv[1]=1;
	rep(i,2,MAXN) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;   //O(n)求逆元
	scanf("%d",&t);
	while (t--)
	{
		size=1;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			int tmp;
			scanf("%d",&tmp);
			a[i]=tmp;
		}
		build();
		printf("%lld\n",size*inv[2]%MOD*n%MOD);
	}
	return 0;
}