转载请注明出处:http://tokitsukaze.live/

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6305


题意:
给一个长度为n的序列A。有一个长度为n的序列B,B的每个元素都是在[0,1]内随机的实数。定义RMQ(A,l,r)为在A数组区间[l,r]内最大的那个元素的最小下标。
求满足1≤l≤r≤n,RMQ(A,l,r)=RMQ(B,l,r)的所有B数组的$\sum_{i=1}^n{b_i}$的期望。


题解:
1.考虑到B中有元素相同的概率是0(因为是实数),于是可以假设B里面元素互不相同,也就是说可以假定是一个排列。
2.[0,1]内随机一个实数的期望是0.5,那么一个排列(n个数)的期望就是n/2。
3.问题转换成:B为n的一个全排列,求满足1≤l≤r≤n,RMQ(A,l,r)=RMQ(B,l,r)的B数组的方案数,记为res。那么ans=(res/n!)*n/2。

所以现在的问题就是,怎么求满足条件的方案数。
这个条件其实就是要满足B数组的大小关系跟A数组的一致。
那么做法就是:用下标RMQ,然后分治。每次找RMQ(A,l,r),记为pos。分配给B[pos]数组持有的数的最大值,因为如果B[pos]为最大值,那么RMQ(B,l,r)也一定返回pos。然后把剩下的数分配给区间[l,pos-1]和[pos+1,r],那我们在剩下的数中选pos-l个数,分配给[l,pos-1],剩下的数就分配给[pos+1,r]。所以分配的方案数就是C(r-l,pos-l)。连乘起来就是res。然后带入那个公式就是答案。

另外注意,需要贴读入挂。还有g++会爆栈,c++扩栈但是贴读入挂也是tle,所以要手写用栈模拟dfs。

代码:

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define _GLIBCXX_PERMIT_BACKWARD_HASH
#include <ext/hash_map>
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
struct str_hash{size_t operator()(const string& str)const{return __stl_hash_string(str.c_str());}};
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-4;
const int MAX=1e6+10;
const ll mod=1e9+7;
/**************************************** head ****************************************/
struct FastIO
{
static const int S=200;
int wpos;
char wbuf[S];
FastIO():wpos(0){}
inline int xchar()
{
static char buf[S];
static int len=0,pos=0;
if(pos==len) pos=0,len=fread(buf,1,S,stdin);
if(pos==len) exit(0);
return buf[pos++];
}
inline int read()
{
int s=1,c=xchar(),x=0;
while(c<=32) c=xchar();
if(c=='-') s=-1,c=xchar();
for(;'0'<=c&&c<='9';c=xchar()) x=x*10+c-'0';
return x*s;
}
~FastIO()
{
if(wpos) fwrite(wbuf,1,wpos,stdout),wpos=0;
}
}io;
int v[MAX],maxx[MAX][22];
int pmax(int a,int b)
{
if(v[a]==v[b]) return min(a,b);
return v[a]>v[b]?a:b;
}
void RMQ(int n)
{
int i,j;
for(i=1;i<=n;i++)
{
maxx[i][0]=i;
for(j=1;1<<(j-1)<=n;j++)
{
maxx[i][j]=0;
}
}
for(j=1;1<<(j-1)<=n;j++)
{
for(i=1;i+(1<<j)-1<=n;i++)
{
int t=1<<(j-1);
maxx[i][j]=pmax(maxx[i][j-1],maxx[i+t][j-1]);
}
}
}
int query(int l,int r)
{
int j=(int)(log10(r-l+1)/log10(2))+1;
int i=r-(1<<(j-1))+1;
return pmax(maxx[l][j-1],maxx[i][j-1]);
}
ll pow2(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
ll inv(ll x)
{
return pow2(x,mod-2);
}
ll fac[MAX],invfac[MAX];
void init(int n)
{
ll i;
fac[0]=invfac[0]=1;
for(i=1;i<=n;i++)
{
fac[i]=fac[i-1]*i%mod;
invfac[i]=inv(fac[i]);
}
}
ll C(int n,int m)
{
if(m>n||m<0) return 0;
return fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
namespace DFS
{
struct node{int l,r;};
int top;
node st[MAX];
ll dfs(int mn,int mx)
{
ll res=1;
int l,r;
l=mn;
r=mx;
top=0;
st[top].l=l;
st[top++].r=r;
while(top)
{
l=st[top-1].l;
r=st[--top].r;
if(l>=r) continue;
int pos=query(l,r);
res=res*C(r-l,pos-l)%mod;
st[top].l=l;
st[top++].r=pos-1;
st[top].l=pos+1;
st[top++].r=r;
}
return res;
}
}
ll dfs(int l,int r)
{
if(l>=r) return 1LL;
int pos=query(l,r);
return dfs(l,pos-1)*dfs(pos+1,r)%mod*C(r-l,pos-l)%mod;
}
int main()
{
int n,t,i;
// scanf("%d",&t);
t=io.read();
init(MAX-10);
ll ans;
while(t--)
{
// scanf("%d",&n);
n=io.read();
for(i=1;i<=n;i++) v[i]=io.read();//scanf("%d",&v[i]);
RMQ(n);
ans=DFS::dfs(1,n)*invfac[n]%mod*n%mod*inv(2)%mod;
printf("%lld\n",ans);
}
return 0;
}