nn个燃料舱,容量均为aa,初始时均为空。

每次等概率随机选择一个没有满的燃料舱,并在其中放入11单位燃料。当所有燃料舱均包含至少bb单位的燃料时,停止该过程

求结束时期望有多少个燃料舱被填满了,答案对998244353998244353取模

1n250,1b<a2501 \le n \le 250,1 \le b < a \le 250

UOJ 514

Solution

原问题转化为:每个燃料舱容量无限,求在所有燃料舱b\ge b的时刻,燃料a\ge a的燃料舱个数的期望。

根据期望的线性性,只需要对每个燃料舱考虑,计算在它燃料=a=a的时刻存在其他燃料舱<b<b的概率(在这个局面下,最终所有燃料舱b\ge b时,该燃料舱必然a\ge a),此时概率即为期望。

而所有燃料舱等价,那么对11号燃料舱进行计算,乘上nn即为答案

考虑容斥,钦定有pp个燃料舱燃料<b< b,容斥系数为(1)p1(n1p)(-1)^{p - 1}\binom{n-1}{p}

问题转化为:有一个初始为空的序列,每次等概率随机添加一个[1,p+1][1, p + 1]的数至序列末尾,计算当序列中出现aa11时,2p+12\sim p+1的出现次数均<b< b的概率。

可以枚举xix_i表示数字ii的出现次数,先钦定序列末尾一定是11,再把剩下的a1a - 111以及2p+12 \sim p + 1这些数用多重排列统计方案数。而每个元素被选到的概率都为1p+1\frac{1}{p + 1},所以有

ans=x2,x3,,xp+1[0,b1](a1+xi)!(a1)!(xi)!(1p+1)a+xi ans = \sum\limits_{x_2,x_3,\ldots,x_{p+1} \in [0,b-1]} \frac{(a-1 + \sum x_i)!}{(a-1)!(\prod x_i)!} \left(\frac{1}{p+1}\right)^{a+\sum x_i}

注意到答案只与xi\sum x_i(xi)!(\prod x_i)!有关,于是枚举j=xij = \sum x_i后可以写成 EGF 的形式。

ans=j=0p(b1)(a1+j)!(a1)!(1p+1)a+j[xj](i=0b1xii!)p ans = \sum\limits_{j=0}^{p(b-1)} \frac{(a-1+j)!}{(a-1)!} \left(\frac{1}{p+1}\right)^{a+j} [x^j]\Big(\sum_{i=0}^{b-1}\frac{x^i}{i!}\Big)^p

可以用 NTT 求出 (i=0b1xii!)p\displaystyle \Big(\sum_{i=0}^{b-1}\frac{x^i}{i!}\Big)^p,时间复杂度为O(n3logn)O(n^3\log n)

进一步优化,令F(x)=i=0b1xii!F(x) = \sum\limits_{i=0}^{b-1}\frac{x^i}{i!},对FF求导则有

从高位到低位依次确定FiF^i的系数即可,时间复杂度O(n3logn)O(n^3\log n)

Another Problem

发现#449. 【集训队作业2018】喂鸽子和这题本质是一样的

min-max容斥,那么有:

ans=i=1n(ni)(1)i+1nif(i) ans = \sum_{i = 1}^{n}\binom{n}{i}(-1)^{i + 1}\frac{n}{i} f(i)

f(i)f(i)表示给ii只鸽子喂食,只要有一个鸽子被喂饱就停止的期望步数。而乘ni\frac{n}{i}是因为平均ni\frac{n}{i}步才会有一粒喂给选中的鸽子

然后转化问题,先枚举第一个饱的是哪个鸽子(即要乘ii),剩下的部分和上题几乎一模一样。只是上面那里求概率,而这里要求期望

复杂度O(n2k)O(n^2k)

Code

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
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch - '0');
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 250;
const int MOD = 998244353;

namespace MATH
{
int fac[MAXN * MAXN + 5], ifac[MAXN * MAXN + 5], inv[MAXN * MAXN + 5];

inline void ADD (int &a, int b) { if ((a += b) >= MOD) a -= MOD; }

inline int Pow (int a, int b)
{
int ans = 1;
for (int i = b; i; i >>= 1, a = (LL) a * a % MOD) if (i & 1) ans = (LL) ans * a % MOD;
return ans;
}

inline void init (int n = MAXN * MAXN + 1)
{
fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = (LL) fac[i - 1] * i % MOD;
ifac[n] = Pow (fac[n], MOD - 2); for (int i = n - 1; i >= 0; --i) ifac[i] = (LL) ifac[i + 1] * (i + 1) % MOD;
for (int i = 0; i < n; ++i) inv[i + 1] = (LL) fac[i] * ifac[i + 1] % MOD;
}

inline int C (int n, int m) { if (n < m || n < 0 || m < 0) return 0; return (LL) fac[n] * ifac[m] % MOD * ifac[n - m] % MOD; }
}

using namespace MATH;

int N, a, b;
int F[2][MAXN * MAXN + 5];

inline void Solve ()
{
for (int i = 0; i < b; ++i) F[1][i] = ifac[i];

int ans = 0;
for (int p = 1; p < N; ++p)
{
int lim = p * (b - 1);
if (p > 1)
{
for (int i = lim; i >= 0; --i)
{
F[(p - 1) & 1][i] = (i >= b - 1) ? ((LL) F[(p - 1) & 1][i - (b - 1)] * ifac[b - 1] % MOD) : 0;
F[p & 1][i] = (LL) F[p & 1][i + 1] * (i + 1) % MOD * inv[p] % MOD;
ADD (F[p & 1][i], F[(p - 1) & 1][i]);
}
}

int sum = 0;
for (int i = 0, coef = Pow (inv[p + 1], a); i <= lim; ++i, coef = (LL) coef * inv[p + 1] % MOD)
{
int res = (LL) fac[a - 1 + i] * ifac[a - 1] % MOD * coef % MOD * F[p & 1][i] % MOD;
ADD (sum, res);
}

ADD (ans, (LL) sum * C (N - 1, p) % MOD * ((p & 1) ? 1 : MOD - 1) % MOD);
}

cout << (LL) ans * N % MOD << endl;
}

inline void Input ()
{
N = read<int>(), a = read<int>(), b = read<int>();
}

int main ()
{

#ifdef hk_cnyali
freopen("B.in", "r", stdin);
freopen("B.out", "w", stdout);
#endif

MATH :: init ();
Input ();
Solve ();

return 0;
}