[ HDU6305 ] RMQ Similar Sequence

        题意:定义一个数列A的\(RMQ(A,l,r)\)为使得\(a_i\)为\(a_l,a_{l+1},a_{l+2}, \cdots ,a_r\)中最大数的最小的i。

        对于两个数列A与B,定义它们RMQ相似当且仅当两数列元素个数相等且对于所有的\(1 \leq l \leq r \leq n\),有\( RMQ(A,l,r)=RMQ(b,l,r)\)。

        现在给你一个正整数数列\(\{a_i\}\),其中\(1 \leq a_i \leq n\),对于实数数列\(\{b_i\}\),其中\(b_i\)为\([0…1]\)中随机的一个实数,当数列A与B  RMQ相似时,B的权值为\(\sum{b_i}\),否则为0,求B权值的期望。(答案对\(10^9 + 7\)取模)(\(1 \leq n \leq 10^6\))

        题解:首先要观察两个序列RMQ相似的条件。当数列A是一个1..n的全排列时,两个序列RMQ相似当且仅当B中元素的大小顺序和A相同。此时答案为\(\frac{n}{2} \cdot \frac{1}{n!}\)(其中\(\frac{n}{2}\)表示的是B中元素之和的期望,\(\frac{1}{n!}\)表示的是B中元素大小顺序满足条件的概率)。

        问题主要是在于当A中含有相同元素的时候的答案。由于不同的A的全排列所对应的满足条件的B是互不相交的(元素间大小关系不同),所以我们要求出与A  RMQ相似的n排列的个数,答案就是这个乘上上面所说的一个排列所对应的答案。接下来找符合条件的全排列(记为C)的个数。

        考虑A的一个区间\([l..r]\),设\(m=RMQ(A,l,r)\),那么我构造的\(c_m\)一定是C中该区间中的最大值,\(c_m\)的值可以确定下来。可以发现,当取任意的\(l \leq l_0 \leq m\)与\(m \leq r_0 \leq r\)的时候,\(RMQ(C,l_0,r_0)=RMQ(A,l_0,r_0)\)肯定是等于m的,也就是说此时m左右两边的数无论大小关系如何都互不影响,那么我们可以任意分配\(m-l\)个数给左边的区间,\(r-m\)个数给右边的区间,方案数为\(C_{r-l}^{m-l}\),然后递归处理左右两个区间,最后再乘上两个区间的答案就好了。

        由于n有\(10^6\),直接DFS会爆栈。不过BFS写也不麻烦。求区间RMQ我直接用线段树来写了(ST表被卡内存),1200ms勉强还是跑过去了。


page views : 3 views

发表评论

电子邮件地址不会被公开。 必填项已用*标注