AGC038E Gachapon

DP 优化 min-max 容斥套路似乎是 min-max 容斥唯一考法了……

题意：有一个随机数生成器，每次生成一个 $[1, n]$ 的随机数，$i$ 生成的概率是 $\dfrac{a_i}{\sum a_i}$，当所有数出现次数都 $\geq b_i$ 时停止，求期望操作次数。$n\leq 400$，$\sum a_i\leq 400$，$\sum b_i\leq 400$。

首先考虑 min-max 容斥，可以得到：

$$ans = \sum_{S\subseteq \{1, 2, \cdots, n\}, s\not= \varnothing} (-1) ^ {|S| - 1} E(\min_{i\in S})$$

后面表示在 $S$ 当中 所有元素出现次数 $\geq b_i$ 时的操作次数 的最小值 的期望。考虑如何求出后面一坨。

操作次数显然很难求，考虑一个比较常见的转化：统计所有合法时操作次数的和等于统计所有不合法状态的概率和。容易发现这是对的。

考虑一个不合法的出现次数序列 $\{c_1, c_2, \cdots, c_n\}$，那么 $c_i < b_i$，然后考虑这个的出现概率，即为：

$$\prod_{i \in S} (\dfrac{a_i}{\sum_{j\in S}a_j}) ^ {c_i}\times \dfrac{(\sum_{i\in S} c_i)!}{\prod_{i\in S} c_i!}$$

第一个表示我们钦定每一位出现哪一个数，出现概率的乘积。后面表示可能出现的排列情况。

现在我们已经把 $S$ 的期望算出来了，但是我们发现这个时候每选择 $S$ 中的数，其实在原问题中只是 $\dfrac {\sum_{i\in S} a_i}{\sum a}$ 的概率，那么就是说，我们的期望值还需要乘上 $\dfrac{\sum a}{\sum_{i\in S} a_i}$，才能得到在原问题中的期望。

于是我们就可以把整个式子写出来了：

$$\sum_{S\subseteq \{1, 2, \cdots, n\}, S\not=\varnothing} (-1) ^ {|S| - 1} \dfrac{\sum a}{\sum_{i\in S}a_i} \sum_{c_1, c_2, \cdots, c_n}[c_i<b_i] \prod_{i \in S} (\dfrac{a_i}{\sum_{j\in S}a_j}) ^ {c_i}\times \dfrac{(\sum_{i\in S} c_i)!}{\prod_{i\in S} c_i!}$$

还是很难算，注意到我们需要把整体的设为状态，比如涉及到的有 $\sum_{i\in S} a_j$，$\sum_{i\in S}c_j$，于是考虑把这两维设为状态计算。剩下的拆开计算即可。

于是直接考虑转移，枚举 $i, \sum_{\in S} c_i, \sum_{i\in S} a_i$ 和当前的 $c$，看似复杂度 $O(n ^ 4)$，但其实由于 $\sum b$ 是一个量级，所以枚举 $i$ 和 $c$ 总体是 $O(n)$，于是总时间复杂度 $O(n ^ 3)$，可以通过。空间比较卡，滚动即可。

int main()
{
	init();
	std::cin >> n;
	for (int i = 1; i <= n; ++ i) std::cin >> a[i] >> b[i];
	f[0][0][0] = Mod - 1;
	for (int id = 1; id <= n; ++ id)
	{
		memset(f[id & 1], 0, sizeof(f[id & 1]));
		for (int sa = 0; sa < N; ++ sa)
			for (int sc = 0; sc < N; ++ sc) {
				if (!f[(id - 1) & 1][sa][sc]) continue;
				int frm = f[(id - 1) & 1][sa][sc];
				adj(f[id & 1][sa][sc] += frm - Mod);
				for (int c = 0, mul = 1; c < b[id]; ++ c, mul = (LL) mul * a[id] % Mod) {
					int &to = f[id & 1][sa + a[id]][sc + c];
					to = (to + (LL) (Mod - mul) * infact[c] % Mod * frm) % Mod;
				}
			}
	}
	int ans = 0, suma = 0;
	for (int i = 1; i <= n; ++ i) suma += a[i];
	for (int sa = 0; sa < N; ++ sa)
		for (int sc = 0, frm; sc < N; ++ sc) {
			if (!(frm = f[n & 1][sa][sc])) continue;
			ans = (ans + (LL) suma * qpow(sa, Mod - 2 - sc) % Mod * fact[sc] % Mod * frm) % Mod;
		}
	std::cout << ans << '\n';
	return 0;
}