被二月份的自己爆踩了
显然可以用 min-max 定理来搞：
[Sigma S = sum_{i in S}a_i
]
[egin{aligned}
E(max_{i in S}(x_i))\
&=sum_{T in S,T
ot= phi}(-1)^{|T|+1}E(min_{i in T}(x_i))\
&=sum_{T in S,T
ot= phi}(-1)^{|T|+1}frac{Sigma S}{Sigma T}E'(min_{i in T}(x_i))\
&= sum_{T in S,T
ot= phi}(-1)^{|T| + 1}frac{Sigma S}{Sigma T}sum_{t}P(x=t)t\
&= sum_{T in S,T
ot= phi}(-1)^{|T| + 1}frac{Sigma S}{Sigma T}sum_{tge 0} P(x > t)\
&= sum_{T in S,T
ot= phi}(-1)^{|T|+1}frac{Sigma S}{Sigma T}sum_{j ge 0}[frac{x^j}{j!}]prod_{i in T}sum_{d < b_i}(frac{a_i}{Sigma T})^d frac{x^d}{d!}\
&= sum_{T in S,T
ot= phi}(-1)^{|T|+1}frac{Sigma S}{Sigma T}sum_{j = 0}^B (1/ Sigma T)^j[frac{(frac{x}{Sigma T})^j}{j!}]prod_{i in T}sum_{d < b_i}a_i^d frac{(frac{x}{Sigma T})^d}{d!}\
&= Sigma Ssum_{T in S,T
ot= phi}sum_{j = 0}^B (frac{1}{Sigma T})^{j+1}(-1)^{|T|+1}[frac{x^j}{j!}]prod_{i in T}sum_{d < b_i}a_i^d frac{x^d}{d!}\
end{aligned}]
发现好多地方都与 (Sigma T) 有关，可以尝试用 (Sigma T) 做状态的一部分来背包DP以防止枚举子集。但是只有 (Sigma T) 还不够，我们还需要知道当前 (|T|) 的奇偶性和 (j)（选的总次数，即背包体积）。可以直接把 ((-1)^{|T|+1}) 乘进去。
设 (f[i][s][j]) 表示考虑了前 (i) 个，选择的集合中 (Sigma T) 为 (s)，的背包数组（含若干 ((-1)) 的贡献）。讨论第 (i) 个是否加入 (T) 集合以及加进去多少：
[egin{aligned}
f(i,s,j) &gets f(i-1,s,j)\
&gets f(i-1,s-a_i,j-k) imes (-1) imes a_i^k imes frac{1}{k!},k < b_i
end{aligned}]
注意这个 (f(i,s,j)) 最后要乘 (j!)。转移要除阶乘，最后要乘阶乘，就又是用多项式乘法来算 EGF 的那些套路了。
总结一下涉及的套路：
-
min-max 容斥
-
(sum_{i} P(x=i) imes i = sum_{i ge 0}P(x>i))
-
指数生成函数 与 背包DP
-
状态中记录关键信息以避免枚举子集
ll f[N][N];
inline void work() {
f[0][0] = -1;
int sm = 0;
for (int i = 1; i <= n; ++i) {
sm += a[i];
for (int s = A; ~s; --s) {
for (int j = 0; j <= B; ++j) {
if (s - a[i] < 0) continue;
ll lstf = f[s][j]; f[s][j] = 0;
ll tmp = 1;
for (int k = 0; k < b[i] && k <= j; ++k, tmp = tmp * a[i] % P) {
f[s][j] = (f[s][j] + f[s - a[i]][j - k] * tmp % P * jieni[k]) % P;
}
f[s][j] = (lstf - f[s][j] + P) % P;
}
}
}
ll ans = 0;
for (int s = 0; s <= A; ++s) {
ll sn = quickpow(s, P - 2);
ll tmp = sn;
for (int j = 0; j < B; ++j, tmp = tmp * sn % P) {
ans = (ans + tmp * f[s][j] % P * jie[j]) % P;
}
}
ans = ans * A % P;
printf("%lld
", (ans % P + P) % P);
}