序列取反问题题解

想出一道期望题,就这样了。

综合题目条件,简化一下题意。
不妨将n对(x和ax)看做n个区间[x,ax],根据题意,这n个区间只有包含相离两种情况。
那么,一个点x被取反,当且仅当x被选或者包含x的区间被选。
单独计算每个点对答案的贡献,当一个点x自己被选,那么贡献为1,如果它没有被选,而是支配它的区间将它取反的话,贡献就是0.由于是等概率选取,假设支配x的区间有c个(包括[x,ax]),那么x的贡献就是1/c。

答案就是图片说明

问题变成了求c。
c的话,便有了一个非常简单的做法,需要知道每个点被多少区间覆盖,直接想到区间+1和区间查询。
线段树做法是O(nlogn),但这样不够优美,可以在假设区间为[x,ax],那么x处打个+1标记,ax+1处打-1标记,前缀和一下就得到c了,复杂度为O(n),加上逆元还是nlogn的,线性求逆元又变回O(n)了。

我的做法,是把序列变成树,x子树根节点,ax为子树x的最后一个节点,可以发现,这可以对应一棵树,在树上求期望也是一样的,复杂度也是O(n)。

这里权当提供一个思路,树转序列,序列转树,都是很好的呢。

参考代码(这个代码是将序列变成树之后的做的):

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @param aLen int a数组长度
     * @return int整型
     */
int ne[200010*2],t[200010*2],he[200010],d[200010],tot=0,b[200010];
long long ans;
void link(int x,int y)
{
    tot++;
    ne[tot]=he[x];
    he[x]=tot;
    t[tot]=y;
}
long long ny(long long x,int y)
{
    long long ret=1;
    while (y)
    {
        if (y&1) ret=ret*x%998244353;
        x=x*x%998244353;
        y=y>>1;
    }
    return ret;
}
void dfs(int x,int y)
{
    ans=(ans+ny(y,998244353-2))%998244353;
    for (int i=he[x];i;i=ne[i]) dfs(t[i],y+1);
}
    int ret(int n, int* a, int aLen) {
        // write code here
    //freopen("1.in","r",stdin);
        for (int i=0;i<n;i++) b[i+1]=a[i]; 
    int len=1;
    d[1]=1;
    int p=1;
    if (n==1)
    {
        return 1;
    }
    while (1)          //用栈将序列还原成树
    {
        p++;
        len++;
        d[len]=p;
        link(d[len-1],p);
        while (p==b[d[len]]) len--;
        if (!len) break;
    }
    ans=0;
    dfs(1,1);
    return ans;

    }
};
全部评论

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务