题目陈述

简介：给定一个数组，每次选择一个区间 $[i,a[i])$ 染色，保证区间不存在相交，只有相离和包含两种关系，问将整个数组染色的期望，答案对 $998244353$ 取模。

前置知识

逆元

求某个数 $a$ 在某个模数 $MOD$ 下的逆元，即求 $x$ ，使得 $a*x \% MOD\equiv1$ ，因此，取模意义下的除法等价于乘该数的逆元
一般在题目当中是一个素数，常见的算法是费马小定理，费马小定理内容是，如果是一个质数，且不是的倍数，则，因此在为质数的情况下，的逆元为，使用快速幂进行求解，时间复杂度为，快速幂代码示例为
```
// x^y % MOD
int qpow(int x,int y)
{
  int ret=1;
  for(int i=y;i;i>>=1)
  {
      if(i&1)
          ret=1LL*ret*x%MOD;
      x=1LL*x*x%MOD;
  }
  return ret;
}
```
p.s. 逆元还可以使用扩展欧几里德算法，复杂度相同，此处不做赘述
逆元可以进行线性递推，假设求在质数下的逆元，假设，，则，所以，则，进一步变换可得，将和带入可得，，实现代码如下
```
inv[1]=1;
for(int i=2;i<MAXN;i++)
{
  inv[i]=((1LL*(MOD-MOD/i)%MOD)*(inv[MOD%i]%MOD))%MOD;
}
```

期望的可加性

两个（或多个）随机变量的和的期望等于期望的和

证明

$\begin{aligned} \mathrm{E}(X+Y) &=\sum_{x} \sum_{y}(x+y) \mathbb{P}(X=x, Y=y) \\ &=\sum_{x} \sum_{y} x \mathbb{P}(X=x, Y=y)+\sum_{x} \sum_{y} y \mathbb{P}(X=x, Y=y) \\ &=\sum_{x} x \sum_{y} \mathbb{P}(X=x, Y=y)+\sum_{y} y \sum_{x} \mathbb{P}(X=x, Y=y) \\ &=\sum_{x} x \mathbb{P}(X=x)+\sum_{y} y \mathbb{P}(Y=y) \\ &=\mathrm{E}(X)+\mathrm{E}(Y) \end{aligned}$

解题算法

由于题目限制了区间的范围，因为本题就可以转换成另一个问题，即给定一个树，每次选择一个子树删除，求删掉整棵树的期望(CF280C)。
利用期望的可加性，设 $X_i$ 为第 $i$ 个节点直接被选择，则 $ans=\sum_{0}^{n-1} E(X_i)$ ，假设节点 $i$ 被 $d$ 个区间覆盖，则 $P(X_i)=1/d$ ，因此可得 $ans=\sum_{0}^{n-1} 1/d_{i}$ ，求某个点被区间覆盖的次数可以直接差分，时间复杂度 $O(n)$ ，空间复杂度 $O(n)$

代码

const int MOD=998244353;
const int MAXN=2e5+5;
typedef long long ll;
int inv[MAXN],sum[MAXN];
class Solution {
public:
    int ret(int n, vector<int>& a) {
        inv[1]=1;
        for(int i=2;i<MAXN;i++)
        {
            inv[i]=((1LL*(MOD-MOD/i)%MOD)*(inv[MOD%i]%MOD))%MOD;
        }
        for(int i=0;i<n;i++)
        {
            sum[i+1]++;
            sum[a[i]+1]--;
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            sum[i]+=sum[i-1];
            ans=(1LL*ans+inv[sum[i]])%MOD;
        }
        return ans;
    }
};

一点思考

由于在证明的过程当中并没有要求 $X$ 和 $Y$ 是独立事件，因此题目里的“若 $i<j$ ，则 $a_i-1<j$ ， $a_i \geq a_j$ 这两个条件一定满足其中1个”这个条件不成立时，~~貌似本题依然可解？~~，如果想的不对欢迎来喷。

题解 | #序列取反问题#

题目陈述

前置知识

逆元

期望的可加性

证明

解题算法

代码

一点思考