题解 | #序列取反问题#

题意整理

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

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

1.解题思路

对于任意均满足条件：若，则这两个条件一定满足其中1个。
所以，如果，要么，此时不包含j；要么，此时一定包含。可以推断，这一定是一个树形结构。

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

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

动图展示：

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数组的时间复杂度为，快速幂运算的时间复杂度为，总共循环n次，所以时间复杂度为。
• 空间复杂度：需要额外大小为n的d数组，所以空间复杂度为。

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

1.解题思路

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

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

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数组的时间复杂度为，快速幂运算的时间复杂度为，总共循环n次，所以时间复杂度为。
• 空间复杂度：需要额外大小为n的d数组，所以空间复杂度为。