题解 | #序列取反问题#
序列取反问题
http://www.nowcoder.com/practice/4e14684f12d04a6a9a6aaf2287493a75
题意：
给你一个长度为
的序列，第
个数字代表了一段连续的区间)
，
其中这些区间满足要么完全覆盖，要么不相交，
现在每次等概率地随机选择一个点，并且将区间全部打上标记，
问期望多少次能将整个序列都打上标记（答案对998244353取模）？
解法一（问题转化+暴力求解）
做这道题我们需要注意到这个性质：『其中这些区间满足要么完全覆盖，要么不相交』
一个区间可以被另外一个区间完全覆盖，我们可以想到『父-子』级关系，再加上两个区间完全不相交，我们可以想到两棵子树完全不相交
那么我们可以根据题目给的序列，构建出一棵树，其中第个节点若被标记，则以第个节点为根节点的整棵子树都会被标记
那么我们可以将题意转化为：给你一棵有个节点的树，每次你会等概率随机选择一棵子树全部打上标记，问期望多少次整棵树都会被标记？
例如这道题样例我们可以构建出如下的一棵树：
我们考虑一个点什么时候会被打上标记：
1. 以点为根节点将子树打上标记
2. 以点的上级节点为根节点将子树打上标记
如果一个节点是『自己标记自己』，那么这个节点对答案的贡献显然为1
如果一个节点是『被别的节点标记的』，那么这个节点对答案的贡献显然为0
我们设
表示节点的深度（根节点的深度为1）
那么节点在被标记的前提下，『自己标记自己』的概率为
，那么节点对答案的贡献为
那么最后的答案为：
实现上，我们可以从左到右枚举，对于节点，我们可以往前寻找『最后一个覆盖当前节点的点』，显然这个点是当前节点的父节点，然后找到父节点后我们就可以计算深度了
接下来我们考虑如何求解
的值（本题中
）
对于，我们需要找到一个值
，使得mod%20P%3D1)
，也就是模
意义下的乘法逆元
找到这个值后，modP)
对于求乘法逆元，我们可以用费马小定理来求解
费马小定理：若
和互质，则
本题中由于是一个质数，且
，故显然和互质
于是我们可以改写一下上面的式子：modP%3D1)
故
就是在模意义下的乘法逆元
求解我们可以用乘法快速幂算法来求解
下面介绍乘法快速幂算法：
首先我们知道任何一个数字都可以进行二进制分解，那么我们考虑对指数进行二进制分解
假如我们要求解
：
我们假设
那么我们可得：
那么接下来我们只要考虑如何递推求解出
显然我们知道：
于是我们就可以根据前一项的
递推到后一项的
了
于是我们求解就可以从朴素的)
优化到)
了
代码：
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;
}
};
时间复杂度：
空间复杂度：)
，数组
是级别大小的，故总的空间复杂度为
解法二（差分优化）
解法一的时间瓶颈主要是计算每个节点的深度
我们可以换一种方法考虑，对于一个点，一定是点)
的上级节点，故点对点的深度贡献为
于是我们可以利用差分+前缀和的方法，计算每个点的深度
代码：
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、时间复杂度：
2、空间复杂度：，数组都是级别大小的，故总的空间复杂度为
