2018 Multi-University Training Contest 1 H - RMQ Similar Seq

发布时间：2020-12-14 04:21:31 所属栏目：大数据来源：网络整理

导读：题意：对于一个序列a，构造一个序列b，使得两个序列，对于任意的区间 [l,r] 的区间最靠近左端点的那个最大值的位置，并且序列 b 满足 0 bi 1。给定一个序列 a,求序列 b 中所有元素的和的期望。 ? Sample Input331 2 331 2 151 2 3 2 1Sample Output2500000

题意：

对于一个序列a，构造一个序列b，使得两个序列，对于任意的区间 [l,r] 的区间最靠近左端点的那个最大值的位置，并且序列 b 满足 0 < bi < 1。

给定一个序列 a,求序列 b 中所有元素的和的期望。

Sample Input
3
3
1 2 3
3
1 2 1
5
1 2 3 2 1

Sample Output
250000002
500000004
125000001

题解：

若满足题意，则 a 和 b 的笛卡尔树同构。

因为 bi 在 0 到 1 之间，故 bi 的期望值为 1/2 ，所以 b 序列的和的期望值为 n/2。
对于笛卡尔树的每一棵子树，若用sz[i]表示以 i 为根节点的子树的大小，则满足其根节点是子树的最大值的概率为 1/sz[i] 。

所以整棵树满足条件的概率为1 / Πsz[i]。

故总期望值为两个的乘积 n / 2Πsz[i]。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
typedef long long LL;
const int maxn = 1000010;
const int MOD = 1e9+7;

int a[maxn],lson[maxn],rson[maxn],fa[maxn];
LL dp[maxn],inv[maxn];
LL tmp;

LL DP(int id)
{
    if (id == 0) return 0;
    if (dp[id]) return dp[id];
    dp[id] = DP(lson[id]) + DP(rson[id]) + 1;
    return dp[id];
}

void getinv()
{
    inv[1] = 1;
    for (int i = 2; i < maxn; i++)
        inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
}

int main()
{
    int t,n;
    scanf("%d",&t);
    getinv();
    for (int ca = 1; ca <= t; ca++)
    {
        scanf("%d",&n);
        for (int i = 1; i <= n; i++) scanf("%d",&a[i]);

        stack<int> st;
        for (int i = 1; i <= n; i++)
            lson[i] = rson[i] = fa[i] = dp[i] = 0;

        for (int i = 1; i <= n; i++)
        {
            if (!st.empty() && a[st.top()] < a[i])
            {
                while (!st.empty() && a[st.top()] < a[i])
                    tmp = st.top(),st.pop();
                lson[i] = tmp,fa[tmp] = i;
            }
            if (!st.empty()) rson[st.top()] = i,fa[i] = st.top();
            st.push(i);
        }

        for (int i = 1; i <= n; i++) if (!fa[i]) DP(i);

        LL ans = n * inv[2] % MOD;
        for (int i = 1; i <= n; i++) ans = ans * inv[dp[i]] % MOD;

        printf("%lldn",ans);
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!