夏晓光(loveJY)的博客

其实这篇博客是用来充数的Qwq

容斥dp这道题即可,我们有一个很妙的转换思路:利用势能函数求出期望次数

期望势能函数就是之前那个全网仅有一个的题的思路,本题也是用到了一点点,因为任何一个第一个大于T的局面的达到都是由一些他之前的状态转移的,并且我们都要乘上对应的局面的概率!

这个概率相当于说在所有的局面中达到这个局面的概率,也就是通过每个操作转移到他这个局面的概率,而转移到了这个局面我们根据期望势能函数的想法,加上他转移出去的期望步数即可

换一种角度,这个也相当于算贡献并且统计方案数,每个局面能够到达的步数等于他[大于等于他子局面]的符号求和,就是3=3>=1+3>=2+3>=3

下面的式子可以仔细品一品

下面是本题题解,摘自ZR省选Day4?

考虑计算$E(min(T))$,即一个集合的一个元素达到$B_i$的一个最小时间qwq

我们可以根据势能函数的定义方法去求这个状态的期望,即对于每个这个状态的先决局面,用他们转移到下一个状态的期望步数*他们出现的概率

于是我们有所有这个状态的前若干步状态的期望和,$c_i$表示某个局面的概率:

$E=(-1)^{|T|+1}\frac{S}{\sum a_i}\sum_{0<=c_i<b_{x_i}}\frac{\sum {c_i}! }{\prod_{i=1}^n(c_i!)}\prod(\frac{a_{x_i}}{\sum{a_{x_i}}})^{c_i}$

其中我们相当于枚举了每一个$c_i$啊,然后就是相当于一个可重全排列每一个的概率走到下个局面期望步数

所以说我们就对于这个式子,算一个容斥dp,看看题目,$\sum B_i ,\sum A_i,n \leq 400$

有个容斥dp状态很严谨的定义$f_{i,j,k}$表示上式中考虑了前i个数,然后$\sum A$为j,$\sum B$为k的所有集合按照上述式子中除掉$\sum A,\sum C$有关项的乘积之和

那么转移就考虑这个数选择的次数对于式子的贡献,会影响A和C

具体的,我们再变变形

$E=(-1)^{|T|+1}\frac{S}{\sum a_i}\sum_{0<=c_i<b_{x_i}}\frac{\sum{c_i}!}{\prod_{i=1}^n(c_i!)}\prod a_{x_i}^{c_i}(\frac{1}{\sum{a_{x_i}}})^{\sum c_i}$

也就是说我们要$\prod (c_i!)$和$\prod a_{x_i}^{c_i}$和$-1^?$

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 998244353;
const int MAXN = 405;
int n, a[MAXN], b[MAXN];
ll fac[3 * MAXN], ifac[3 * MAXN], inv[MAXN][MAXN];
int f[MAXN][MAXN][MAXN];//容斥DP
//前i个数,然后a的和,c的和
inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}
inline void add(int &x, int y) {
	x += y;
	if(x >= P)x -= P;
}
inline void init() {
	int mx1 = 0, mx2 = 0, N = 0;
	for(int i = 1; i <= n; ++i) {
		mx1 = max(a[i], mx1);
		mx2 = max(mx2, b[i]);
		N += max(a[i], b[i]);
	}
	for(int i = 1; i <= mx1; ++i) {
		for(int j = 0; j <= mx2; ++j) {
			inv[i][j] = ksm(i, j);
		}
	}
	fac[0] = 1;
	ifac[0] = 1;
	for(int i = 1; i <= N; ++i)
		fac[i] = fac[i - 1] * i % P;
	ifac[N] = ksm(fac[N], P - 2);
	for(int i = N - 1; i >= 1; --i)ifac[i] = ifac[i + 1] * (i + 1) % P;
	return ;
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d%d", &a[i], &b[i]);
	}
	init();
	f[0][0][0] = P - 1;
	ll Sa = 0, Sb = 0;
	for(int i = 1; i <= n; ++i) {
		Sa += a[i];
		Sb += b[i];
		for(int j = 0; j <= Sa; ++j) {
			for(int k = 0; k <= Sb; ++k) {
				//选择这个数
				if(j - a[i] >= 0)
					for(int l = 0; l < b[i]; ++l) {
						if(k - l >= 0)
							add(f[i][j][k], P - 1ll * f[i - 1][j - a[i]][k - l] * inv[a[i]][l] % P * ifac[l] % P);
						//ifac是i!的逆元
					}
				add(f[i][j][k], f[i - 1][j][k]);//不选择这个数,没有变化
			}
		}
	}
	int ans = 0;
	for(int i = 0; i <= Sa; ++i) {
		ll tmp = Sa * ifac[i] % P * fac[i - 1] % P;
		for(int j = 0; j <= Sb; ++j) {
			add(ans, tmp * f[n][i][j] % P * fac[j] % P * ksm(ifac[i] * fac[i - 1] % P, j) % P);
		}
	}
	printf("%d\n", ans);
	return 0;
}