题目陈述

大意：给定一排牛牛，一开始都是不快乐的牛牛，每次等概率选择一个当前不快乐的牛牛，将$[i,a[i\left]\right)[i,a[i])$[i,a[i])中的牛牛都变为快乐，最后所有的牛牛都变为快乐的在$modmod$mod $mm$m意义下，的期望步数是多少？

前置知识

• 这题是一个ACM竞赛中很经典的树上期望问题，在该模型上做出一定变形的题目
• 相信我讲完这个树上期望问题的模型，大家会更加容易理解

模型

给定一颗树，然后每次随机删除一个节点，删除它的同时他的子树都会消失，每次删除的节点等概率，问删除掉所有节点的期望步数

解释模型

• 此处我解释一下模型的题意

• 如果给定了一下这棵树

• 有两种删除这棵树的方法，

• 第一种方案：第一次就选择了$11$1，整棵树直接被删除，概率为${\displaystyle \frac{1}{2}}\backslash cfrac\{1\}\{2\}$21​，执行的步骤为$11$1次，所以该方案的期望为$1\ast {\displaystyle \frac{1}{2}}={\displaystyle \frac{1}{2}}1*\backslash cfrac\{1\}\{2\}=\backslash cfrac\{1\}\{2\}$1∗21​=21​次

• 第二种方案：第一次选择了$22$2，第二次选择了$11$1，因为第一选择$22$2的概率为${\displaystyle \frac{1}{2}}\backslash cfrac\{1\}\{2\}$21​，第二次只有一个节点，选择到$11$1的概率为$100\%100\backslash \%$100%，故整个方案被实现的概率为${\displaystyle \frac{1}{2}}\backslash cfrac\{1\}\{2\}$21​，执行的步骤为$22$2次，该方案的步骤为$2\ast {\displaystyle \frac{1}{2}}=12*\backslash cfrac\{1\}\{2\}=1$2∗21​=1

• 总的期望步骤为所有方案的期望之和${\displaystyle \frac{1}{2}}+1=1.5\backslash cfrac\{1\}\{2\}+1=1.5$21​+1=1.5

• 如果给定了如下这棵树

• 经过了上一个例子，相信你已经有一定感觉了

方案 被实现的概率 执行的步骤
1 1/3 1
2 1 1/6 2
3 1 1/6 2
2 3 1 1/6 3
3 2 1 1/6 3

• 最后总的期望步骤为${\displaystyle \frac{1}{3}}\ast 1+{\displaystyle \frac{1}{6}}\ast 1+{\displaystyle \frac{1}{6}}\ast 2+{\displaystyle \frac{1}{6}}\ast 3+{\displaystyle \frac{1}{6}}\ast 3=2\backslash cfrac\{1\}\{3\}*1+\backslash cfrac\{1\}\{6\}*1+\backslash cfrac\{1\}\{6\}*2+\backslash cfrac\{1\}\{6\}*3+\backslash cfrac\{1\}\{6\}*3=2$31​∗1+61​∗1+61​∗2+61​∗3+61​∗3=2步

算法思路

• 首先我们考虑这样一个问题，对于一个节点，它什么时候会对我们的答案有贡献？
• 对于一个节点，在一整个完整的操作过程中，无非是有被选到和没有被选到，分别对应于$00$0和$11$1，我们用$a_{i}a\_i$ai​来表示这个值
• 我们假设第$ii$i个点被选择到的概率为$p_{i}p\_i$pi​，那么最后它对答案的贡献$E_i=0\ast (1-p_i)+1\ast p_i=p_{i}E\_i=0*(1-p\_i)+1*p\_i=p\_i$Ei​=0∗(1−pi​)+1∗pi​=pi​，总得答案就是$E={\sum }_{i=1}^n{E}_{i}E=\backslash sum\_\{i=1\}^\{n\}E\_i$E=∑i=1n​Ei​
• 那么一个点被选到的概率有是多少呢？
• 我们知道，一个节点被删除掉的情况，只有他的任意一个祖先被选择到，或者他自身被选择到的时候，他就会删除掉。
• 换言之，反过来，它被选择到的时候，就说明它的任意一个祖先节点都还在
• 接下来我们用标记为黑色代表删除
• 我们随机生成一个由$11$1到$nn$n组成的$nn$n个数的操作序列，我们首先找到第一个未被染成黑色的节点，然后将这个节点，，即其子树都染成黑色，重复上述操作，直至整个序列都是黑色。
• 对于节点$ii$i，他能被选择到，则说明它的任意一个祖先节点都在它的后面
• 因为$ii$i节点有$deep\left[i\right]-1deep[i]-1$deep[i]−1个祖先，仅看$ii$i节点和它的祖先的情况，考虑插空法，每个祖先前面都有一个空，最后一个祖先后面也有一个空，总共有$deep\left[i\right]deep[i]$deep[i]个空位可以插入。
• 只有第一个空位是满足该节点会被选择到的，即概率$p_i={\displaystyle \frac{1}{deep\left[i\right]}}p\_i=\backslash cfrac\{1\}\{deep[i]\}$pi​=deep[i]1​
• 故最后的期望为$E={\sum }_{i=1}^n{\displaystyle \frac{1}{deep\left[i\right]}}E=\backslash sum\_\{i=1\}^\{n\}\backslash cfrac\{1\}\{deep[i]\}$E=∑i=1n​deep[i]1​

结论

• 删除树中所有节点的期望步数步数$E={\sum }_{i=1}^n{\displaystyle \frac{1}{deep\left[i\right]}}E=\backslash sum\_\{i=1\}^\{n\}\backslash cfrac\{1\}\{deep[i]\}$E=∑i=1n​deep[i]1​，即每个点的深度的倒数之和。

算法1：概率与期望+逆元

算法思路

模型转换

• 已知了上述结论，那么跟我们的题目又有什么关系呢？
• 我们题目中所得到的序列，在一定意义上面，可以看成树的先序遍历序列（并非一定是二叉树，此处指的是先访问根，再访问其子树），更准确的说应该是一个DFS遍历序列
• 下面我们用染成黑色，来代表模型中的删除
• 为什么？因为$ii$i位置被选到了，$[i,a[i]-1][i,a[i]-1]$[i,a[i]−1]整个区间都被染色了，等价于模型中的，$ii$i节点和其子树都被染色了
• 但是，此处肯定有同学想问，为啥它必然是一棵树的dfs遍历序列？
• 我们仔细分析题目
• 第一，对于可爱值$a_{i}a\_i$ai​有，$a_i>ia\_i>i$ai​>i且特别的有$a_0=na\_0=n$a0​=n（题目中应该是写错了，写成了$a_1=na\_1=n$a1​=n）
• 这边$a_0=na\_0=n$a0​=n，选择到$i=0i=0$i=0表示染色$[0,n-1][0,n-1]$[0,n−1]，跟我们模型中，删除根节点则整棵树都被删除掉，是等价的
• 第二，对于任意$i,ji,j$i,j，均满足条件：若i<j，则ai​−1<j，ai​≥aj​这两个条件一定满足其中1个
• 我反复推敲了一下，这边的满足应该是二选一，而不是至少
• 我们这样解释这句话，对于一个大于$ii$i的数$jj$j，若满足ai​−1<j则说明，他的覆盖区间$[i,a[i]-1][i,a[i]-1]$[i,a[i]−1]无法覆盖到$jj$j位置.
• 如果满足$a_i\ge a_{j}a\_i\backslash geq\; a\_j$ai​≥aj​则说明，$[i,a[i]-1][i,a[i]-1]$[i,a[i]−1]的覆盖范围一定大于$[j,a[j]-1][j,a[j]-1]$[j,a[j]−1]，等价于我们上面的子树的限制条件
• 肯定有同学要问，如果没有这个限制条件会怎么样呢？
• 即$jj$j在$[i,a[i]-1][i,a[i]-1]$[i,a[i]−1]范围内，但是$a\left[j\right]-1a[j]-1$a[j]−1不在$[i,a[i]-1][i,a[i]-1]$[i,a[i]−1]范围内，这就相当于一种情况，产生了环
• 但是题目已经把这种情况给规避掉了，一个没有环的图，只可能是DAG（有向无环图），或者是树
• 但是题目中的限制条件约定了，只存在一个区间完全包含另一个区间，不存在一个区间和另一个区间有交集的情况，故它对于的模型也不可能是DAG（有向无环图）
• 所以最后他就可以完全等价对应我们的模型树上期望问题

求解期望

• 既然能对应成一棵树的模型，我们已经知道了树上期望问题的求解是需要深度
• 那么我们是否需要建树?
• 答案是否定的，即不需要
• 为什么？我们考虑区间覆盖$[i,a[i]-1][i,a[i]-1]$[i,a[i]−1]，如果对于一个位置$kk$k，他能被$xx$x个区间覆盖（包括自身的区间），那么就说明他在$xx$x个节点的子树中，换言之，$kk$k位置也就是有$x-1x-1$x−1个祖先
• 即节点$kk$k的深度$deep\left[k\right]=xdeep[k]=x$deep[k]=x
• 所以我们只需要知道$kk$k位置被多少个区间给覆盖，即可知道对应的树中的深度
• 我们考虑每个区间对于某个位置$kk$k的贡献，则有

deep[k]=∑i=1n​[i≤k<a[i]](此处中括号代表表达式为真返回1，否则返回0)

• 故知道每个位置在树中对应的深度则有

$E={\sum }_{k=1}^n{\displaystyle \frac{1}{deep\left[k\right]}}E=\backslash sum\_\{k=1\}^n\; \backslash cfrac\{1\}\{deep[k]\}$E=∑k=1n​deep[k]1​

• 即

E=∑k=1n​∑i=1n​[i≤k<a[i]]1​

• 此处需要取模，用到除法，故需要逆元

逆元

• 此处讲一下费马小定理求解逆元（可能某些地方也会用拓展欧几里得、线性求逆元等方法，但是竞赛的经验就是快速幂求解逆元，的代码运行效率是最高的）

• 逆元简单理解下，就是你在模运算中除以一个数，等价乘以一个数，那么所乘的这个数，就叫做除以的这个数的逆元

• 即两数在取模$pp$p的意义下相乘等于1$a\ast inv\left[a\right]\equiv 1a*inv[a]\backslash equiv1$a∗inv[a]≡1

• 欧拉定理有$a^{\varphi \left(p\right)}\equiv 1\left(modp\right)a^\{\backslash phi(p)\}\backslash equiv\; 1\backslash pmod\; p$aϕ(p)≡1(modp)

• 其中$\varphi \left(p\right)\backslash phi(p)$ϕ(p)为欧拉函数，代表$1-p-11-p-1$1−p−1中与$pp$p互质的数个个数，$pp$p为质数的时候即得到费马小定理 $a^{p-1}\equiv 1\left(modp\right)a^\{p-1\}\backslash equiv\; 1\; \backslash pmod\; p$ap−1≡1(modp)

• 提出一个$aa$a有$a\ast a^{p-2}\equiv 1\left(modp\right)a*a^\{p-2\}\backslash equiv\; 1\; \backslash pmod\; p$a∗ap−2≡1(modp)

• 跟上面的逆元对比$a\ast inv\left[a\right]\equiv 1\left(modp\right)a*inv[a]\backslash equiv\; 1\; \backslash pmod\; p$a∗inv[a]≡1(modp)

• 即 $inv\left[a\right]\equiv a^{p-2}\left(modp\right)inv[a]\backslash equiv\; a^\{p-2\}\; \backslash pmod\; p$inv[a]≡ap−2(modp)

• 这样，我们用快速幂即可求解得到$inv\left[a\right]inv[a]$inv[a]

• 根据上面的期望表达式 E=∑k=1n​∑i=1n​[i≤k<a[i]]1​

• 即 E=∑k=1n​(∑i=1n​[i≤k<a[i]])p−2(modp)

• 现在我们即可直接求解答案了

代码实现

typedef long long LL;
class Solution {
public:
	int p = 998244353; 
	LL inv(LL a, LL b) //费马小定理，快速幂求解逆元
    {
        LL res = 1;
        while(b)
        {
            if(b & 1) //当前位为1
                res = res * a % p; //乘到答案中
            a = a * a % p; //倍增
            b >>= 1;
        }
        return res; //返回逆元
    }
    int ret(int n, vector<int>& a) {
        LL ans = 0;
        vector<int> d(n); //每一个点的深度，约定deep[root]=1
        for (int i = 0; i < n; i ++ )
            for (int j = i; j < a[i]; j ++ ) //每个点的子树区间
                d[j] ++ ; //j节点的深度加一
        for (int i = 0; i < n; i ++ )
            ans = (ans + inv(d[i], p - 2)) % p; 
            //ans += 1/deep[i]
            // ans = (ans + 1 * inv(deep[i])) % mod
            // ans = (ans + inv(deep[i])) % mod
            //费马小定理有 inv(deep[i]) = deep[i]^(mod - 2)
        return ans;       
    }
};

复杂度分析

• 时间复杂度，统计深度为$O\left(n{\sum }_{i=1}^n\right(a\left[i\right]-i\left)\right)O(n\backslash sum\_\{i=1\}^n\; (a[i]-i))$O(n∑i=1n​(a[i]−i))，最坏情况$a\left[i\right]=na[i]=n$a[i]=n，为$O\left(n^2\right)O(n^2)$O(n2)级别；计算答案中，快速幂为$\log p\backslash log\; p$logp，总共$nn$n次，为$O(n\log p)O(n\; \backslash log\; p)$O(nlogp)级别，最后总的时间复杂度为$O\left(n^2\right)O(n^2)$O(n2)
• 空间复杂度,定义了深度数组$dd$d[]，为$O\left(n\right)O(n)$O(n)

算法2：概率与期望+逆元+差分约束

算法思路

• 整道题目的思路基本在上面都讲完了
• 此处算是一个较大的一个优化
• 我们可以发现上面的统计贡献，是区间，即对于位置$ii$i，它的覆盖区间$[i,a[i]-1][i,a[i]-1]$[i,a[i]−1]整体的贡献都$+1+1$+1
• 我们此处用差分约束，来优化区间修改
• 它的大致思路比较简单，就是差值+前缀和
• 大致是这样的，对于一个数组$a\left[\right]=2,3,4,5a[]=\{2,3,4,5\}$a[]=2,3,4,5
• 我们可以先构造$d\left[0\right]=a\left[0\right],d\left[i\right]=a\left[i\right]-a[i-1],i\ge 1d[0]=a[0],d[i]=a[i]-a[i-1],i\backslash geq\; 1$d[0]=a[0],d[i]=a[i]−a[i−1],i≥1，然后我们计算$d\left[\right]d[]$d[]的前缀和数组，是不是就是$a\left[\right]a[]$a[]数组了？
• 那么现在我们就可以用$d\left[\right]d[]$d[]数组来替代$a\left[\right]a[]$a[]数组
• 我们要将$[l,r][l,r]$[l,r]这个区间的东西都加上1，我们会发现对于$i\in [l-1,r]i\backslash in\; [l-1,r]$i∈[l−1,r]这个区间$d\left[i\right]d[i]$d[i]都不改变,因为$[l,r][l,r]$[l,r]集体加一了
• $d\left[l\right]d[l]$d[l]会增加$11$1，$d[r+1]d[r+1]$d[r+1]会减少$11$1
• 故我们只需要修改两个值，就可以替代原本的$r-l+1r-l+1$r−l+1次修改
• 最后在求一遍前缀和还原$a\left[\right]a[]$a[]数组即可

代码实现

typedef long long LL;
class Solution {
public:
	int p = 998244353; 
	LL inv(LL a, LL b) //费马小定理，快速幂求解逆元
    {
        LL res = 1;
        while(b)
        {
            if(b & 1) //当前位为1
                res = res * a % p; //乘到答案中
            a = a * a % p; //倍增
            b >>= 1;
        }
        return res; //返回逆元
    }
    int ret(int n, vector<int>& a) {
        LL ans = 0;
        vector<int> d(n); //每一个点的深度，约定deep[root]=1
        for (int i = 0; i < n; i ++ ) //区间[i,a[i]),左闭右开
            d[i] ++ , d[a[i]] -- ; //左端点+1,右端点-1
        for (int i = 1; i < n; i ++ )
            d[i] += d[i - 1]; //差分约束,维护差分数组
        for (int i = 0; i < n; i ++ )
            ans = (ans + inv(d[i], p - 2)) % p;
            //ans += 1/deep[i]
            // ans = (ans + 1 * inv(deep[i])) % mod
            // ans = (ans + inv(deep[i])) % mod
            //费马小定理有 inv(deep[i]) = deep[i]^(mod - 2)
        return ans;       
    }
};

复杂度分析

• 时间复杂度，预处理差分数组为$O\left(n\right)O(n)$O(n)，计算差分数组为$O\left(n\right)O(n)$O(n)最坏情况$a\left[i\right]=na[i]=n$a[i]=n；计算答案中，快速幂为$\log p\backslash log\; p$logp，总共$nn$n次，为$O(n\log p)O(n\; \backslash log\; p)$O(nlogp)级别，最后总的时间复杂度为$O(n\log p)O(n\backslash log\; p)$O(nlogp)
• 空间复杂度,定义了深度数组$dd$d[]，为$O\left(n\right)O(n)$O(n)