AT_agc038_e Gachapon 题解

非常好题目。

和 P4707 类似的，假设 表示第 种物品满足条件的时间，那么我们就是要求 。

通常来说可以考虑枚举一个时间 ，求 并相加。但是问题在于这个 可以很大。因为可能出现一直抽到同一个元素，导致其余元素迟迟不能满足条件的情况。

因此直接求 的做法是比较困难的。此时的一个常见思路就是考虑使用 反演将 转化成 来计算。

具体的，我们有以下式子。

对于外层套一个期望的情况下也同样适用（因为期望的线性性）。

因而我们要求的就是右边一坨。

令 。考虑如何求解单个 。不妨先对于全集 求解 。

此时我们可以使用开头提到的做法。枚举一个 ，求 ，并对于每个 相加。与 版本不同的是， 有一个上界。令 中所有元素的 之和为 ，那么在 步之后至少会有一个元素满足条件。

因此我们这个做法只需要枚举到 即可。

考虑对于一个 ，如何计算这个答案。由于 ，因此集合内每个元素被抽到的次数都没有达到对应的 。我们考虑枚举每个元素被抽中了几次，假设是 次，假设之前已经用掉了 个元素，那么首先有 种选择位置的方案，这个元素对每个方案的发生概率的贡献是乘上 （）。

因而我们可以考虑设计一个 DP 求解 。令 表示考虑了前 个元素，还剩下 个位置可用，发生概率是 。转移就是上面所说的枚举一个 ，乘上 进行转移，最后取 就是答案。

你发现我们要对每个 都重新跑一遍，最后只取 这点十分浪费。注意到大部分计算实际上是重复的。我们不妨反过来考虑，令前 表示考虑了前 个元素，选择了 个位置，此时我们在枚举一个 ，转移是乘上一个 合并成一个长度为 的序列，然后乘上 表示发生的概率进行转移。求大于 的答案只需要取出 即可。

不过，问题在于我们如何对于一个严格子集 求解这个 。

我们可以考虑这样计算。定义中一次奖表示一次抽奖抽到了 中的元素。考虑期望下中几次奖才会使得 集合内至少有一个元素满足条件，而我们发现这个问题和我们刚才讨论全集的情况是一样的，我们直接把算法搬过来即可。接着把这个答案乘上中一次奖的期望就可以得到期望要抽几次才能让 集合内至少有一个元素满足条件了。

形式化的，定义随机变量 表示 这个元素满足条件时， 中的元素一共被抽中的次数。我们先求 ，接着把它乘上抽到一次 中元素的期望次数就可以得到我们的 了。

这个东西看上去显然正确！

但是我们还是考虑证明一下。

考察以下命题。

INFO 命题
三个事件 。 发生时候可能导致 发生， 发生可能导致 发生。这个发生可能不是一个以 概率发生不发生之类的，可能经过一个复杂的随机过程。这里我们都不在意，但是保证这两个过程是独立的，并且保证每次 发生时， 的随机过程会回到初始状态。

定义随机变量 表示“时间 第一次发生时， 的发生次数”， 表示时间“ 第一次发生时， 的发生次数”， 表示“ 第一次发生时， 的发生次数”。

那么我们有

形式化一下。考虑 表示第 次 发生时距离第 次发生了几次 事件，特别的， 定义为事件 第一次发生时 发生的次数，也就是 。并且保证所有 概率分布相同且独立。所有 和 也独立。

那么有

我们想要证明

如果 是一个普通整数，那么我们可以使用期望的线性性质轻松展开。但是问题在于 这里是随机变量。

我们考虑根据定义来计算 。

有

考虑如何计算 。考虑全概率公式。如果第一次发生 是在 ，那么第 次 肯定也导致了一次 的发生，然后这个 导致了 的发生。我们考虑枚举这一次 是发生的第几次 ，记作 。

把 放进来。

由于是概率，因此右侧肯定全是正的。根据 Tonelli 定理，我们可以交换两个求和号。

提出和 无关的 一项。

此时考虑右侧 一项。我们有 和 独立，因此这个其实就是 。

然后这个东西其实就是 。

注意此时 就是一个普通的正整数了。

期望线性性展开。

同分布，因此这个东西就是 。把和 无关的 提出。

里面就是 。证毕。

这个东西就是 Wald 恒等式。

因此我们这样的计算方法是正确的。

接下来考虑如何同时对所有子集 进行计算。

我们发现阻止我们推广的主要有两点。

一是，转移需要 ，但是如果不事先知道和的话，没办法求出 。

二是，最后要乘上一个 。

对于第一个问题，我们把所有 提出来，假设最后选出了 个元素，额外给这个乘上 即可。

第二个问题也是同理。这些的贡献都只和 有关，因此我们按照 分组，每组内一起计算。

具体的，我们考虑设计下面这个 DP。

另 表示已经考虑了前 个元素加入 集合，此时 集合内 之和是 ，已经落入集合 次。

转移有两种。

  • 不选当前元素加入 。。
  • 将当前元素加入 ，并且这个元素被抽中了 次。。

上文 表示 累加上 。

边界是 。这个是因为对于空集的情况贡献是 。

最后，对于每个 ，将其乘上 并累加进答案。

以上就是本题的做法。代码很好写，我写了一下改了一个输入格式问题就直接过了。

此时要注意不能把空集的答案统计进去。不过如果是空集的话用快速幂处理 处理出来就是 。因此用快速幂处理逆元就不用特判 了。

值得一提的是，本题的数据十分幽默，虽然题目中没有保证，但是数据中所有 和 都是相等的。你在计算的时候就算笔误打错了最后也可以通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
#include <array>
#include <iostream>
#include <numeric>
#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 = ull>
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(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;
    }
};

using modint998244353 = modular<998244353>;
using modint1000000007 = modular<1000000007>;
} // 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 maths {
constexpr bool is_prime(const ull &x) {
    for (size_t i = 2; i * i <= x; i++) {
        if (x % i) {
            continue;
        }
        return false;
    }
    return true;
}

template <ull MOD>
struct combine {
    static_assert(is_prime(MOD));

    using mll = maths::modular<MOD>;

    mll inv(const mll &x) {
        static_assert(is_prime(MOD));
        return maths::quick_pow<mll>(x, MOD - 2, 1);
    }

    mll factrial(uint n) {
        static std::vector<mll> fact{1};
        for (size_t i = fact.size(); i <= n; i++) {
            fact.push_back(fact.back() * i);
        }

        return fact[n];
    }

    mll factrial_inv(uint n) {
        static std::vector<mll> inv_fact{1};
        for (size_t i = inv_fact.size(); i <= n; i++) {
            inv_fact.push_back(inv(i) * inv_fact.back());
        }

        return inv_fact[n];
    }

    mll operator()(int n, int m) {
        if (n < 0 || m > n) {
            return 0;
        }
        else {
            return factrial(n) * factrial_inv(m) * factrial_inv(n - m);
        }
    }
};
} // namespace maths

namespace solve {
const uint MOD = 998244353;
maths::combine<MOD> cmb;
using mll = maths::modint998244353;
const uint V = 405;

void solve() {
    uint n;

    std::cin >> n;

    std::vector<uint> poss(n);
    std::vector<uint> req(n);

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

    mll sum = std::accumulate(poss.begin(), poss.end(), mll(0));

    std::vector<std::array<std::array<mll, V>, V>> dp(
        n + 1, std::array<std::array<mll, V>, V>{{}});

    dp[0][0][0] = MOD - 1;

    for (size_t i = 0; i < n; i++) {
        for (size_t sum_poss = 0; sum_poss < V; sum_poss++) {
            for (size_t cnt = 0; cnt < V; cnt++) {
                /**
                 * 不选。
                 */

                dp[i + 1][sum_poss][cnt] += dp[i][sum_poss][cnt];

                /**
                 * 去掉烦人的边界判断。反正题目保证了和不超 400。
                 */

                if (dp[i][sum_poss][cnt] == 0) {
                    continue;
                }

                /**
                 * 选。不能拿满了给。
                 */

                for (size_t take = 0; take < req[i]; take++) {
                    dp[i + 1][sum_poss + poss[i]][cnt + take] +=
                        -dp[i][sum_poss][cnt] *
                        maths::quick_pow<mll>(poss[i], take, 1) *
                        cmb(cnt + take, take);
                }
            }
        }
    }

    mll ans = 0;

    for (size_t i = 0; i < V; i++) {
        for (size_t j = 0; j < V; j++) {
            ans += dp[n][i][j] * cmb.inv(maths::quick_pow<mll>(i, j, 1)) *
                   cmb.inv(i) * sum;
        }
    }

    std::cout << ans << "\n";
}
} // namespace solve

int main() {
    solve::solve();
    std::cout << std::flush;
}
OI > 题解
AT_agc038_e Gachapon 题解
https://blogs.sving1024.top/posts/6619/
发布于
2026年8月29日
许可协议