题目陈述

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

前置知识

逆元

• 求某个数在某个模数下的逆元，即求，使得，因此，取模意义下的除法等价于乘该数的逆元
• 一般在题目当中是一个素数，常见的算法是费马小定理，费马小定理内容是，如果是一个质数，且不是的倍数，则，因此在为质数的情况下，的逆元为，使用快速幂进行求解，时间复杂度为，快速幂代码示例为

  // 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;
  }

期望的可加性

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

证明

解题算法

由于题目限制了区间的范围，因为本题就可以转换成另一个问题，即给定一个树，每次选择一个子树删除，求删掉整棵树的期望(CF280C)。
利用期望的可加性，设为第个节点直接被选择，则，假设节点被个区间覆盖，则，因此可得，求某个点被区间覆盖的次数可以直接差分，时间复杂度，空间复杂度

代码

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;
    }
};

一点思考

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