序列取反问题题解
想出一道期望题,就这样了。
综合题目条件,简化一下题意。
不妨将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; } };