题意

给定数组 满足

  1. ，特别地， 。
  2. 或 。

起初这些数均未被标记。每次可以在未标记的数中任选一个 ，并标记下标在 中的所有数。求将所有数均标记所需的期望次数。

解法1：状压DP（MLE+TLE）

我们用一个 位二进制数 表示 中元素被标记的状态（第 位的 表示 被标记， 表示 不被标记）。

用 表示标记过程中出现 状态的概率， 表示出现 状态所需的期望步数。

设 为 状态中 的个数， 为选择 时可标记的集合，则有转移方程

转移方程中出现分数，因此需要利用逆元计算。
线性递推逆元的公式为

代码

const int mod = 998244353;
const int N = 22;
int inv[N];
int f[1<<N], dp[1 << N];
class Solution {
   public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @param a int整型vector
     * @return int整型
     */
    void init(int n) {
        inv[1] = 1;
        for (int i = 2; i <= n; i++) {
            inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod; // 线性递推逆元
        }
    }
    int ret(int n, vector<int>& a) {
        // write code here
        init(n);
        for (int mask = 0; mask < (1 << n); mask++) f[mask] = dp[mask] = 0;
        f[0] = 1;
        for (int mask = 0; mask < (1 << n); mask++) {
            int room = n - __builtin_popcount(mask); // 0的个数
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) continue;
                int cover = (1 << a[i]) - (1 << i);
                f[mask | cover] =
                    (f[mask | cover] + 1ll * f[mask] * inv[room]) % mod;
                dp[mask | cover] =
                    (dp[mask | cover] + 1ll * (dp[mask] + f[mask]) * inv[room]) % mod;
            }
        }
        return dp[(1 << n) - 1];
    }
};

复杂度分析

空间复杂度：逆元部分 ，DP部分 ，共
时间复杂度：逆元部分 ，DP部分需要扫描每个子集， ，共

解法2：DFS

注意题目中的第2个性质，不难发现所有区间两两不相交。
因此可以转化为一棵树。
如数据 6,[6,4,3,4,6,6] 可以转化为

图片说明

该问题即转化为：每次随机选一个点删除以它为根的子树，求将它删光所需删除次数的期望。
由于点是等概率选取的，因此可以考虑 的所有排列，依次删除（遇到已删除的点即跳过）。因此，一个子树被删除的概率是它的根的深度的倒数。
因此，我们需要求的就是所有点的倒数之和。
可以利用dfs实现。

代码

const int mod = 998244353;
const int N = 22;
int inv[N];
int f[1<<N], dp[1 << N];
class Solution {
   public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @param a int整型vector
     * @return int整型
     */
    void init(int n) {
        inv[1] = 1;
        for (int i = 2; i <= n; i++) {
            inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
        }
    }
    int dfs(int u, int dep, vector<int>& a){
        int ret = inv[dep]; // 深度的倒数
        for(int v=u+1; v<a[u]; v=a[v]){ // 子节点
            ret = (ret + dfs(v, dep+1, a)) % mod;
        }
        return ret;
    }
    int ret(int n, vector<int>& a) {
        // write code here
        init(n);
        return dfs(0, 1, a);
    }
};

复杂度分析

空间复杂度：逆元部分，DFS部分，共
时间复杂度：逆元部分，DFS部分，共

解法3：差分

我们可以发现，点 对下标在 中的所有点的深度均有 点贡献。
因此我们可以维护一个数组 ，对于每个 ，将 增加 ， 减少 。最后再对 做一次前缀和，便可以直接得到每个点的深度了。

代码

const int mod=998244353;
const int N=200005;
int inv[N];
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @return int整型
     */
    void init(int n){
        inv[1] = 1;
        for(int i = 2; i <= n; i++){
            inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
        }
    }
    int ret(int n, vector<int>& a) {
        // write code here
        init(n);
        vector<int> b(n + 1, 1);
        for(int i = 0; i < n; i++){
            --b[a[i]]; //贡献的差分
        }
        for(int i = 1; i < n; i++){
            b[i] += b[i - 1]; // 前缀和
        }
        int ans = 0;
        for(int i = 0; i < n; i++){
            ans = (ans + inv[b[i]]) % mod;
        }
        return ans;
    }
};

复杂度分析

空间复杂度：逆元部分，差分部分，共
时间复杂度：逆元部分，差分部分，共