题解 | #序列取反问题#

题意整理

给定一个序列，序列中每个下标对应一个值，选定一个下标i，则从i到 $a_i-1$ 的区间所有数都做一个标记。
最后的目标是将所有的数都打上标记，问所有可能的方案中期望步数是多少。

方法一（排列+费马小定理+快幂法）

1.解题思路

对于任意 $i,j$ 均满足条件：若 $i<j$ ，则 $a_i-1<j，a_i>=a_j$ 这两个条件一定满足其中1个。
所以，如果 $i<j$ ，要么 $a_i-1<j$ ，此时 $[i,a_i-1]$ 不包含j；要么 $a_i>=a_j$ ，此时 $[i,a_i-1]$ 一定包含 $[j,a_j-1]$ 。可以推断，这一定是一个树形结构。

确定树形结构之后，再考虑一个点被标记的概率，为了让一个点被标记，它之前一定没被标记，从而它一定要在其前置节点之前被标记上，只要找到其前置节点的个数（不包括它本身，记为k-1），则此节点可以放在所有前置节点之间的k个空中，由于放在第一个空时，才能被标记，所以概率是 $1/k$ 。于是只要找到所有节点对应的k，即可计算出期望步数，公式为： $图片说明$ 。
基本步骤：

定义数组d，用于记录对应下标前置节点个数（包括自身）。
遍历a数组，统计前置节点个数。
根据之前分析的公式，求期望步数。
由于存在除法操作，可能产生精度问题，所以需要通过费马小定理将除法操作转化为乘方再取余。
根据费马小定理， $(k)^{mod-1}\%mod=1$ ，所以两边同时除以 $k$ 再互换位置，得： $1/k=k^{mod-2}\%mod$

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    int mod=998244353;
    public int ret (int n, int[] a) {
        //声明结果变量
        long res=0;
        //记录对应下标前置节点个数（包括自身）
        int[] d=new int[n];
        for(int i=0;i<n;i++){
            for(int j=i;j<a[i];j++){
                d[j]++;
            }
        }
        for(int i=0;i<n;i++){
            //费马小定理求逆元
            res=(res+fastpow(d[i],mod-2))%mod;
        }

        return (int)res;

    }

    //快幂法计算乘方，防溢出
    private long fastpow(long n,long k){
        long res=1L;
        while(k>0){
            if(k%2==1){
                res=(res*n)%mod;
            }
            n=(n*n)%mod;
            k/=2;
        }
        return res;
    }
}

3.复杂度分析

时间复杂度：预处理d数组的时间复杂度为 $O(n^2)$ ，快速幂运算的时间复杂度为 $O(log_2mod)$ ，总共循环n次，所以时间复杂度为 $O(n*log_2mod+n^2)$ 。
空间复杂度：需要额外大小为n的d数组，所以空间复杂度为 $O(n)$ 。

方法二（差分+前缀和+排列+费马小定理+快幂法）

1.解题思路

思路与方法一差不多，但是较大程度优化了计算 $d$ 数组的过程。

定义数组 $d$ ，用于记录对应下标前置节点个数（包括自身）。
将下标 $i$ 处对应值加一，表示 $i$ 到 $a[i]-1$ 之间的值都会通过后面前缀累加的方式填上。同时将下标 $a[i]$ 处对应值减一，表示a[i]及以后的值，通过相减的方式抵消掉，不会被后面操作累加到。
前缀和累加的方式还原 $d$ 数组。
根据之前分析的公式，求期望步数。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    int mod=998244353;
    public int ret (int n, int[] a) {
        //声明结果变量
        long res=0;
        //记录对应下标前置节点个数
        int[] d=new int[n+1];
        //通过差分求前置节点个数
        for(int i=0;i<n;i++){
            //表示i到a[i]-1之间的值都会通过后面前缀累加的方式填上
            d[i]++;
            //a[i]及以后的值，通过相减的方式抵消掉
            d[a[i]]--;
        }
        //前缀和方式还原d数组
        for(int i=1;i<n;i++){
            d[i]+=d[i-1];
        }
        for(int i=0;i<n;i++){
            //费马小定理求逆元
            res=(res+fastpow(d[i],mod-2))%mod;
        }

        return (int)res;

    }

    //快幂法计算乘方，防溢出
    private long fastpow(long n,long k){
        long res=1L;
        while(k>0){
            if(k%2==1){
                res=(res*n)%mod;
            }
            n=(n*n)%mod;
            k/=2;
        }
        return res;
    }
}

3.复杂度分析

时间复杂度：预处理d数组的时间复杂度为 $O(n)$ ，快速幂运算的时间复杂度为 $O(log_2mod)$ ，总共循环n次，所以时间复杂度为 $O(n*log_2mod+n)$ 。
空间复杂度：需要额外大小为n的d数组，所以空间复杂度为 $O(n)$ 。