题意整理：

基本题意

有一个长度为 $n$ 的序列 $\{a_i\}(i=0,1,2,\ ...\ ,n-1)$ ，每个下标 $i$ 表示了一个区间 $[i, a_{i})$ 。

最开始所有的下标都没有标记，现在，每次从没有标记过的下标中等概率随机选取一个下标 $i$ ，然后把落在区间 $[i, a_{i})$ 上的下标打上标记。

问期望多少次操作能把下标 $0, 1, 2, . . ., n - 1$ 全部打上标记。

求答案在模 $998244353$ 意义下的值。

数据范围与性质

$n\le 2\times 10^5, i< a_i \le n$ 。保证 $a_{0} = n$ 。

对于任意的 $i < j$ ，要么 $a_{i} - 1 < j$ ，要么 $a_i \ge a_j$ 。也就是说对于这 $n$ 个区间，他们两两之间的关系是，要么不交，要么包含。

题意的转化

我们定义在 $[0, n - 1]$ 中的任意两个整数 $i < j$ ，如果满足区间 $[i, a_{i})$ 包含了区间 $[j, a_{j})$ ，并且不存在任意的整数 $i < k < j$ 满足区间 $[k, a_{k})$ 也包含区间 $[j, a_{j})$ ，则称 $i$ 是 $j$ 的父亲结点。

根据这个定义可以说明， $0$ 没有父亲结点，并且 $1, 2, . . ., n - 1$ 都具有唯一的父亲结点，因此我们建立了一个具有 $n$ 个结点的，并且以 $0$ 为根的树模型。

在执行题目中的打标记操作的时候，假设选中了 $i$ ，我们发现区间 $[i, a_{i})$ 中的结点在树模型中，一定是以 $i$ 为根的一颗子树。这是因为题目限定了区间之间不能有部分交集的关系，所以范围 $[i, a_{i})$ 内每个点代表的区间一定被包含在 $[i, a_{i})$ 中。

因此我们得到了转化题意：给出一棵树，每次随机选择一个没有被删除的点，把以这个点为根的子树删除，问期望多少次能把整颗树删掉，求答案在模 $998244353$ 意义下的值。

这是一个比较经典的概率期望问题。

样例的树模型建立：

n=6
a=[6,4,3,4,6,6]

对应6个区间：

下标	表示区间	父亲结点
0	[0,6)	无
1	[1,4)	0
2	[2,3)	1
3	[3,4)	1
4	[4,6)	0
5	[5,6)	4

建树如下：

图片说明

图 1

方法一：

【知识点】树，概率与期望，数学，乘法逆元

【算法】差分，逆元求解，基于费马小定理的快速幂解法

结论与分析

结论如下：

对于上文提到的树模型，我们定义 $d e p (i)$ 表示结点 $i$ 的深度，也就是从 $i$ 出发到根结点的路径上经历过的结点个数，例如图 $1$ 中， $d e p (0) = 1, d e p (2) = 3$ 。

那么此题求解的答案其实就是：

\sum_{i=0}^{n-1} \frac{1}{dep(i)} \pmod {998244353}

证明如下：

考虑树上每个点对删除次数的贡献：如果在删点的过程中，一个点是被自己删除的，那么它对答案的贡献就是 $1$ ，如果它是被自己的祖先删除的，那么它的贡献就是 $0$ 。

假设结点 $i$ 有 $p_{i}$ 的概率被自己删除，那么就有 $1 - p_{i}$ 的概率被其祖先删除，那么在数学期望上，结点 $i$ 对答案的贡献就是 $e_i = 1\times p_i + 0\times (1-p_i) = p_i$ ，那么答案也就是 $\sum_{i=0}^{n-1} p_i$ 了。

考虑 $p_{i}$ 是什么。我们发现，在任何一种情况下，如果点 $i$ 没有被删除，那么其所有祖先一定也没有被删除。假如接下来的一次操作会把 $i$ 删除，那么接下来删除的点就有 $d e p (i)$ 种可能，其中有 $d e p (i) - 1$ 种情况是选中了 $i$ 的祖先（如图 2）。

图片说明

图 2

因为选点是等概率随机的，因此就有 $\frac{1}{dep(i)}$ 的概率让 $i$ 被自己删除，有 $dep(i)-1\over dep(i)$ 的概率让 $i$ 被自己祖先删除。因为在每个随机过程中都具有此性质，故 $p_i=\frac{1}{dep(i)}$ 。

所以求解答案为：

\sum_{i=0}^{n-1} \frac{1}{dep(i)} \pmod {998244353}

实现细节

考虑如何求解这个式子，首先我们需要求出所有的 $d e p (i)$ 。

我们把每个结点自己也看作自己的祖先。那么 $d e p (i)$ 就等于 $i$ 的祖先数目。根据我们开始的分析，结点 $x$ 一定是 $[x, a_{x})$ 范围中所有结点的祖先，因此，结点 $x$ 对 $j\in[x,a_x)$ 的结点 $j$ 的 $d e p$ 的贡献为 $1$ 。于是，我们先令 $dep(i) ,i\in[0,n)$ 都为 $0$ ，然后考虑每个结点 $i$ ，对 $[i, a_{i})$ 区间的 $d e p$ 值进行一次 $+ 1$ ，那么最后就可以求出所有的 $d e p (i)$ 了。

这里的区间加法可以采用差分标记法，令 $b_{i} = d e p (i) - d e p (i - 1)$ ，那么在给区间 $[l, r]$ 做 $+ 1$ 时只会让 $b_{l}$ 变为 $b_{l} + 1$ ，以及 $b_{r+1}$ 变为 $b_{r+1}-1$ 。所以可以 $O (1)$ 完成一个区间加法的处理。最后把差分数组的前缀和求出来，就得到了 $d e p (i)$ 数组。

这里的时空间复杂度都是 $O (n)$ 。

接下来，考虑求 $1\over dep(i)$ 在模意义下的值，也就是 $d e p (i)$ 的逆元。由费马小定理可知，因为模数 $p = 998244353$ 是质数， $dep(i) \le n < p$ ，所以 $dep^{-1}(i) \equiv dep^{p-2}(i) \pmod p$ ，可以用快速幂求取逆元。这一步的时间复杂度是 $O(n\log p)$ 。

最后把所有 $d e p (i)$ 的逆元求和取模即可，总时间复杂度 $O(n+n\log p)$ ，空间复杂度 $O (n)$ 。

参考代码

//c++
class Solution {
public:
    static const int MOD = 998244353;
    static const int MAXN = 200010;
    int b[MAXN],dep[MAXN];//b是差分数组，dep是深度数组
    
    int qpow(int x,int y)//快速幂，经典写法，用于求解逆元
    {
        int ret=1;
        while(y)
        {
            if(y&1)ret=1ll*ret*x%MOD;
            x=1ll*x*x%MOD;
            y>>=1;
        }
        return ret;
    }
  
    int ret(int n, vector<int>& a) {
        
        int ret=0;
        memset(b,0,sizeof(b));//清空，初始化
        
        for(int i=0;i<n;i++)//对 [i,ai) 进行区间 +1 ，维护差分数组
        {
            b[i]++;
            b[a[i]]--;
        }
        dep[0]=b[0];
        for(int i=0;i<n;i++)//求解差分数组的前缀和，得到 dep 数组，并将答案累加
        {
            if(i)dep[i]=b[i]+dep[i-1];//dep[i]是b[i]的前缀和
            ret=(ret+qpow(dep[i],MOD-2))%MOD;
        }
        return ret;
    }
};

方法二：

【算法】前缀积线性求解逆元

上述方法最终的时间复杂度为 $O(n\log p)$ ，空间复杂度是 $O (n)$ 。其中 $p$ 是模数 $998244353$ 可以发现时间复杂度的瓶颈在于逆元的求解，所以在方法二我们尝试优化一下逆元求解的复杂度。

我们发现在这道题目中，我们只需要用到深度 $d e p (i)$ 的逆元，而深度值不会超过 $n$ ，因此我们可以先预处理出 $1,2\cdots n$ 在模 $p$ 意义下的逆元，不妨称之为 $inv(1),inv(2),\cdots inv(n)$

下面将介绍线性求解 $1,2\cdots n$ 逆元的方法。首先，我们用 $i!\ \ (i\in \N)$ 来表示 $1\times 2\times \cdots \times i$ 的乘积，也就是 $i$ 的阶乘，特别的，当 $i = 0$ 的时候规定 $0! = 1$ 。

步骤一，求解出 $n$ 以内的阶乘在模 $p$ 意义下的值，记为 $fac(i)=i! \bmod p ,\ \ 0\le i \le n$ 。这一步可以递推处理，先令 $f a c (0) = 0$ ，然后用递推式 $fac(i+1)=fac(i)\times (i+1)$ 计算。

步骤二，用费马小定理求解 $f a c (n)$ 的逆元，记为 $i n v f a c (n)$ ，表示阶乘的逆元，这一步用快速幂求解即可。

步骤三，递推处理出所有 $i n v f a c (i)$ 的值，根据递推式 $invfac(i)=invfac(i+1)\times (i+1)$ 求解。

然后，对于数字 $i$ 的逆元，因为 $\frac{1}{i}=\frac{(i-1)!}{i!}$ ，于是只需要用 $fac(i-1)\times invfac(i)\bmod p$ 计算即可。实现了 $O (1)$ 调用。

参考代码（除了优化部分，其余同方法一）

//c++
class Solution {
public:
    static const int MOD = 998244353;
    static const int MAXN = 200010;
    int b[MAXN],dep[MAXN];
    int fac[MAXN],invfac[MAXN];//阶乘和阶乘的逆元
    
    
    int qpow(int x,int y)//快速幂，用于求解逆元
    {
        int ret=1;
        while(y)
        {
            if(y&1)ret=1ll*ret*x%MOD;
            x=1ll*x*x%MOD;
            y>>=1;
        }
        return ret;
    }
  
    void init_invfac(int &n){//预处理阶乘和阶乘的逆元
        fac[0]=1;
        for(int i=1;i<=n;i++)fac[i] = 1ll * fac[i-1] * i % MOD;//递推算阶乘
        invfac[n] = qpow(fac[n],MOD-2);//计算n!的逆元
        for(int i=n-1;i>=1;i--)invfac[i] = 1ll * invfac[i+1] * (i+1) % MOD;//递推算逆元
    }
  
    int inv(int x){//预处理后，就可以 O(1) 计算逆元了
        return 1ll * fac[x-1] * invfac[x] % MOD;
    }
  
    int ret(int n, vector<int>& a) {
        
        int ret=0;
        memset(b,0,sizeof(b));
        init_invfac(n);//预处理阶乘和阶乘的逆元
        
        for(int i=0;i<n;i++)//对 [i,ai) 进行区间 +1 ，维护差分数组
        {
            b[i]++;
            b[a[i]]--;
        }
        dep[0]=b[0];
        for(int i=0;i<n;i++)//求解差分数组的前缀和，得到 dep 数组，并将答案累加
        {
            if(i)dep[i]=b[i]+dep[i-1];
            ret=(ret+inv(dep[i]))%MOD;//这里就可以直接 O(1) 算逆元了
        }
        return ret;
    }
};

可以看到，这个算法在预处理阶乘和阶乘逆元的时候，都只有 $O (n)$ 的时间复杂度，并且需要 $O (n)$ 的空间，然后只是用了一次费马小定理快速幂求逆元，这里时间复杂度 $O(\log p)$ 空间复杂度 $O (1)$ 。因此，此方法总的时间复杂度 $O(n+\log p)$ ，空间复杂度 $O (n)$ 。

题解 | #序列取反问题#