【题解】UR #19 通用测评号 容斥，求导 – UOJ#514

题面

UOJ# #514.【UR #19】通用测评号

给定 $n$ 个燃料舱，容量为 $a$ 升 。每次会往没有满的燃料舱里面加 $1$ 升油，直到所有的燃料舱都至少包含 $b$ 升油。求最后满了的燃料舱个数期望。

数据范围：$n, a, b \le 250$。

题解

感觉这题的思想十分巧妙 qwq

对于第一个燃料舱，计算他满的时候还有燃料舱没有达到 $b$ 的概率，最后再把答案乘以 $n$。

有燃料舱没有到达 $b$ 这个条件可以通过二项式反演计算，$f_j$ 表示在第一个燃料舱到达 $a$ 时，我们钦定有 $j$ 个没有达到 $b$ ，其他随便的概率。

思考 $f_i$ 怎么算？

由于其他的一些燃料舱是随便选的，那么我们可以只考虑这 $i + 1$ 个燃料舱的情况。

于是问题就转化成了一些操作，最后一次操作恰好让第一个燃料舱的油变成了 $a$，且除了第一个燃料舱外的所有燃料舱的油量都没有到达 $b$。

这个容易用 $\rm EGF$ 计算。让 $B(x) = \sum\limits_{i = 0}^{b – 1} \frac{x^i}{i!}$，$f_i = \sum\limits_{j = 0}^{i b} \frac{(a + j – 1)!}{(a – 1)!} (\frac{1}{i + 1})^{j + a} [x^j] B(x)^i$

这个的复杂瓶颈在计算 $B(x)^i$。发现 $B(x)$ 和 $e^x$ 很像，我们可以考虑 求导。

$B(x) – B(x)’ = \frac{x^{b – 1}}{(b – 1)!}$

$(B(x)^t)’ = t B(x)’ B(x)^{t – 1} = t B(x) B(x)^{t – 1} – t (B(x) – B'(x)) B(x)^{t – 1} = t(B(x)^t – \frac{B(x)^{t – 1} x^{b – 1}}{(b – 1)!})$

考虑提取 $[x^{k – 1}]$ 次项，让 $f(x) = B(x)^t$，$g(x) = B(x)^{t – 1}$，

$$k f_{k} = t(f_{k – 1} – \frac{g_{k – b}}{(b – 1)!})$$

$$f_k = \frac{t}{k} (f_{k – 1} – \frac{g_{k – b}}{(b – 1)!})$$

时间复杂度 $\Theta(n^2 b + na)$ 。

代码

实现不是很优秀 /kk

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = j, i##E = k; i <= i##E; i++)
#define R(i, j, k) for(int i = j, i##E = k; i >= i##E; i--)
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int, int>
#define mkp make_pair
#define sz(a) ((int) a.size())
using namespace std;
const int N = 254, M = N * N, mod = 998244353;
int n, a, b, f[N], dp[N][M], ans;
int fac[M], ifac[M], inv[M];
int qpow(int x, int y = mod - 2) {
    int res = 1;
    for(; y; x = (ll) x * x % mod, y >>= 1) if(y & 1) res = (ll) res * x % mod;
    return res;
}
int C(int x, int y) {
    return (ll) fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
void init(int x) {
    fac[0] = ifac[0] = inv[1] = 1;
    L(i, 2, x) inv[i] = (ll) inv[mod % i] * (mod - mod / i) % mod;
    L(i, 1, x) fac[i] = (ll) fac[i - 1] * i % mod, ifac[i] = (ll) ifac[i - 1] * inv[i] % mod;
}
int fpow(int x) {
    return x % 2 == 1 ? mod - 1 : 1;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> a >> b, init(n * a + 1);
    L(i, 0, n - 1) dp[i][0] = 1;
    L(i, 1, n - 1) 
        L(j, 1, i * (b - 1)) 
            dp[i][j] = (ll) i * (dp[i][j - 1] - (j >= b ? (ll) ifac[b - 1] * dp[i - 1][j - b] % mod : 0) + mod) % mod * inv[j] % mod;
    L(i, 0, n - 1) 
        L(j, 0, i * (b - 1)) 
            (f[i] += (ll) qpow(inv[i + 1], j + a) * ifac[a - 1] % mod * fac[a + j - 1] % mod * dp[i][j] % mod) %= mod;
    L(i, 0, n - 1) f[i] = (ll) f[i] * C(n - 1, i) % mod;
    L(i, 0, n - 1) (ans += (ll) f[i] * fpow(i) % mod) %= mod;
    ans = (mod + 1 - ans) % mod, ans = (ll) ans * n % mod;
    cout << ans << "\n";
    return 0;
}