P4707 重返现世题解

依旧拖题解。

非常好题目！

不妨考虑全部集齐的时候怎么做，即 的情况。

考虑 min-max 反演，即

证明可以考虑排名为 的数。大于这个数的数一共有 个，这个数会在 个子集中做贡献。对于 的情况，其中一半为正，另一半为负，因此贡献是 。对于 的情况，贡献就是 。

需要注意这个式子在期望意义下也是成立的，利用线性性质展开即可。

另 表示第一次每个元素的时间，放在这个题目，考虑其组合意义。

是我们要求的，最后一个元素被第一次访问时的期望时间。 是第一次到达 中元素的期望时间。

我们主要到，这个时间是好求的。每次实验的成功概率是 。那么期望就是其倒数，也就是 。

然而枚举子集的复杂度仍然不能接受。我们注意到，对于一个子集 ，我们关心的只有其大小的奇偶性和 ，而 和奇偶性范围都不大。因此我们可以一个背包求出来方案数。

不妨令 表示前 个元素中，选出若干个元素组成集合 ，满足 时， 的值。

转移是枚举选或者不选，不选就直接继承，选的话就乘上 ，加回来。相当于做一个背包。也就是下面这个东西：

• 。
• 。

最后枚举最终集合的大小，计算 就是答案了。

不过问题来了，如果 怎么办？

相当于求第 大元素的期望，我们有以下结论（请注意 从 开始编号）：

求最大值的时候，就是相当于将 带入 。

但是，我们仍然不好暴力记录这个式子啊？刚刚的做法只适用于 的情况。

我们发现难点在于组合数的处理，增加元素的时候，组合数也会发生对应的变化，不过每次只会变化 。考虑将组合数拆一下：

你发现，增加新元素的时候，我们只需要同时维护系数是 和 的值就能进行转移了！

我们将 DP 状态修改一下，现在让 表示前 个元素中选出若干个元素组成集合 ，满足 时， 的值。

每次转移的时候，我们就把系数是 和 的位置乘上 ，累加到当前的位置即可。

也就是：

• 。
• 。

需要注意的是，在 DP 的一开始我们需要设计合适的初值。一开始只有空集，大小为 ，系数就是 。我们不妨定义 当且仅当 为偶数，否则为 。这样就可以保证递推在 的位置也是正确的。

别忘了 的系数。

参考代码：

#include <iostream>
#include <vector>

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

namespace maths {
template <ull mod, class int_type = ll, class uint_type = uint>
class modular {
  private:
    uint_type x;
    void norm() { x -= mod * (x >= mod); }

  public:
    modular() : x(0) {}
    modular(int_type _x) {
        if (_x < 0) {
            x = _x % (int_type)mod + (int_type)mod;
        }
        else {
            x = _x % mod;
        }
        norm();
        return;
    }
    friend modular operator+(const modular &lhs, const modular &rhs) {
        modular ret;
        ret.x = lhs.x + rhs.x;
        ret.norm();
        return ret;
    }
    friend modular operator-(const modular &lhs, const modular &rhs) {
        modular ret;
        ret.x = lhs.x + mod - rhs.x;
        ret.norm();
        return ret;
    }
    friend modular operator*(const modular &lhs, const modular &rhs) {
        return modular(int_type(lhs.x) * rhs.x);
    }
    modular operator-() const {
        modular ret;
        ret.x = mod - x;
        return ret;
    }
    modular operator-=(const modular &b) { return *this = *this - b; }
    modular operator+=(const modular &b) { return *this = *this + b; }
    modular operator*=(const modular &b) { return *this = *this * b; }
    bool operator==(const modular &b) const { return x == b.x; }
    uint_type val() const { return x; }
    friend std::istream &operator>>(std::istream &is, modular &rhs) {
        is >> rhs.x;
        rhs.x %= mod;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const modular &rhs) {
        os << rhs.val();
        return os;
    }
};
} // namespace maths

namespace maths {
template <class T>
T quick_pow(T a, ull b, T id = T()) {
    T ret = id;
    for (; b; b >>= 1, a = a * a) {
        if (b & 1) {
            ret = a * ret;
        }
    }
    return ret;
}

template <class T>
T quick_pow(T a, const std::string &s, T id = T()) {
    T ret = id;
    for (size_t i = 0; i < s.size(); i++, a = a * a) {
        if (s[i] == '1') {
            ret = a * ret;
        }
    }
    return ret;
}

} // namespace maths

namespace solve {
const uint mod = 998244353;
using mll = maths::modular<mod>;
void solve() {
    uint n, k, m;
    std::cin >> n >> k >> m;

    std::vector<uint> poss(n);
    for (size_t i = 0; i < n; i++) {
        std::cin >> poss[i];
    }

    std::vector<std::vector<mll>> dp(
        m + 1, std::vector<mll>(n - k + 1)); // 第 k 大。从 0 开始。

    dp[0][0] = ((n - k) & 1) ? 1 : mod - 1;

    for (size_t i = 1; i <= n - k; i++) {
        dp[0][i] = dp[0][i - 1] * (-1);
    }

    for (size_t i = 0; i < n; i++) {
        std::vector<std::vector<mll>> nxt(m + 1, std::vector<mll>(n - k + 1));
        for (size_t j = 0; j <= m; j++) {
            if (poss[i] + j <= m) {
                nxt[poss[i] + j][0] += -dp[j][0];
            }
            nxt[j][0] += dp[j][0];
        }

        for (size_t rank = 1; rank <= n - k; rank++) {
            for (size_t j = 0; j <= m; j++) {
                if (poss[i] + j <= m) {
                    nxt[poss[i] + j][rank] += -(dp[j][rank] + dp[j][rank - 1]);
                }
                nxt[j][rank] += dp[j][rank];
            }
        }

        dp = nxt;
    }

    mll ans = 0;

    for (size_t i = 1; i <= m; i++) {
        ans += dp[i][n - k] * m * maths::quick_pow<mll>(i, mod - 2, 1);
    }

    std::cout << ans << std::endl;
}
} // namespace solve

int main() {
    solve::solve();
    return 0;
}