2021-11-12 11:32 已编辑 AAAAA Beauty Academy (Peoria) 后端

关注

题解 | #序列取反问题#

序列取反问题

http://www.nowcoder.com/practice/4e14684f12d04a6a9a6aaf2287493a75

题意：

给你一个长度为 $n$ 的序列，第 $i$ 个数字代表了一段连续的区间 $[i,a_i)$ ，

其中这些区间满足要么完全覆盖，要么不相交，

现在每次等概率地随机选择一个点 $i$ ，并且将区间 $[i,a_i)$ 全部打上标记，

问期望多少次能将整个序列都打上标记（答案对998244353取模）？

解法一（问题转化+暴力求解）

做这道题我们需要注意到这个性质：『其中这些区间满足要么完全覆盖，要么不相交』

一个区间可以被另外一个区间完全覆盖，我们可以想到『父-子』级关系，再加上两个区间完全不相交，我们可以想到两棵子树完全不相交

那么我们可以根据题目给的序列，构建出一棵树，其中第 $i$ 个节点若被标记，则以第 $i$ 个节点为根节点的整棵子树都会被标记

那么我们可以将题意转化为：给你一棵有 $n$ 个节点的树，每次你会等概率随机选择一棵子树全部打上标记，问期望多少次整棵树都会被标记？

例如这道题样例我们可以构建出如下的一棵树：

我们考虑一个点 $i$ 什么时候会被打上标记：

1. 以点 $i$ 为根节点将子树打上标记

2. 以点 $i$ 的上级节点为根节点将子树打上标记

如果一个节点是『自己标记自己』，那么这个节点对答案的贡献显然为1

如果一个节点是『被别的节点标记的』，那么这个节点对答案的贡献显然为0

我们设 $d[i]$ 表示节点的深度（根节点的深度为1）

那么节点 $i$ 在被标记的前提下，『自己标记自己』的概率为 $\frac{1}{d[i]}$ ，那么节点 $i$ 对答案的贡献为 $\frac{1}{d[i]}$

那么最后的答案为： $\sum_{i=0}^{n-1}\frac{1}{d[i]}$

实现上，我们可以从左到右枚举，对于节点 $i$ ，我们可以往前寻找『最后一个覆盖当前节点的点』，显然这个点是当前节点的父节点，然后找到父节点后我们就可以计算深度了

接下来我们考虑如何求解 $\sum_{i=0}^{n-1}\frac{1}{d[i]} mod P$ 的值（本题中 $P=998244353$ ）

对于 $\frac{1}{d[i]}$ ，我们需要找到一个值 $x$ ，使得 $(d[i]*x)mod P=1$ ，也就是 $d[i]$ 模 $P$ 意义下的乘法逆元

找到这个值后， $\frac{1}{d[i]}modP=(1*x)modP$

对于求乘法逆元，我们可以用费马小定理来求解

费马小定理：若 $a$ 和 $P$ 互质，则 $a^{P-1}modP=1$

本题中由于 $P$ 是一个质数，且 $d[i]<P$ ，故显然 $d[i]$ 和 $P$ 互质

于是我们可以改写一下上面的式子： $a^{P-1}modP=1 \Rightarrow (a*a^{P-2})modP=1$

故 $a^{P-2}modP$ 就是 $a$ 在模 $P$ 意义下的乘法逆元

求解 $a^{P-2}modP$ 我们可以用乘法快速幂算法来求解

下面介绍乘法快速幂算法：

首先我们知道任何一个数字都可以进行二进制分解，那么我们考虑对指数进行二进制分解

假如我们要求解 $a^x$ ：

我们假设 $x=2^{k_n}+2^{k_{n-1}}+...+2^{k_{1}}$

那么我们可得： $a^x=a^{2^{k_n}}*a^{2^{k_{n-1}}}*...*a^{2^{k_1}}$

那么接下来我们只要考虑如何递推求解出 $a^{2^{n}}$

显然我们知道： $a^{2^n}=a^{2^{n-1}+2^{n-1}}=a^{2^{n-1}}*a^{2^{n-1}}$

于是我们就可以根据前一项的 $a^{2^{n-1}}$ 递推到后一项的 $a^{2^n}$ 了

于是我们求解 $a^x$ 就可以从朴素的 $O(x)$ 优化到 $O(logx)$ 了

代码：

class Solution {
public:
    const int mod=998244353;
    int ksm(int a,int b){
        //快速幂
        int res=1;
        //刚开始的a代表a^{2^0}
        while(b){
            if(b&1){
                res=1ll*res*a%mod;//如果指数当前位对答案有贡献
            }
            a=1ll*a*a%mod;//递推下一项的a^{2^n}
            b>>=1;
        }
        return res;
    }
    int ret(int n, vector<int>& a) {
        vector<int> d(n,0);
        d[0]=1;//根节点深度
        for(int i=1;i<n;i++){
            for(int j=i-1;j>=0;j--){
                if(a[j]-1>=i){
                    //当前节点深度为父节点深度+1
                    d[i]=d[j]+1;
                    break;
                }
            }
        }
        int ans=0;
        for(int i=0;i<n;i++){
            ans+=ksm(d[i],mod-2);//费马小定理
            ans%=mod;
        }
        return ans;
    }
};

时间复杂度： $O(n^2+nlogP)$ ，对于每个节点，向前寻找父节点最坏情况时间复杂度为 $O(n)$ ，快速幂的时间复杂度为 $O(logP)$ ，故计算答案的时间复杂度为 $O(nlogP)$ ，故总的时间复杂度为 $O(n^2+nlogP)$

空间复杂度： $O(n)$ ，数组 $d$ 是 $O(n)$ 级别大小的，故总的空间复杂度为 $O(n)$

解法二（差分优化）

解法一的时间瓶颈主要是计算每个节点的深度

我们可以换一种方法考虑，对于一个点 $i$ ，一定是点 $[i+1,a_i)$ 的上级节点，故点 $i$ 对点 $[i+1,a_i)$ 的深度贡献为 $1$

于是我们可以利用差分+前缀和的方法，计算每个点的深度

代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @return int整型
     */
    const int mod=998244353;
    int ksm(int a,int b){
        //快速幂
        int res=1;
        while(b){
            if(b&1){
                res=1ll*res*a%mod;
            }
            a=1ll*a*a%mod;
            b>>=1;
        }
        return res;
    }
    int ret(int n, vector<int>& a) {
        vector<int> d(n,0);
        for(int i=0;i<n;i++){
            d[i]++;//差分
            if(a[i]<n)d[a[i]]--;//差分
        }
        for(int i=1;i<n;i++){
            d[i]=d[i-1]+d[i];//前缀和
        }
        int ans=0;
        for(int i=0;i<n;i++){
            ans+=ksm(d[i],mod-2);//费马小定理
            ans%=mod;
        }
        return ans;
    }
};

1、时间复杂度： $O(nlogP)$ ，计算差分和前缀和的复杂度为 $O(n)$ ，计算答案的复杂度为 $O(nlogP)$

2、空间复杂度： $O(n)$ ，数组 $d$ 都是 $O(n)$ 级别大小的，故总的空间复杂度为 $O(n)$