AGC038E Gachapon 题解 （min-max 容斥，dp,期望）

听说这题可以用生成函数做，但我不会。。。
做这题首先必须知道min-max容斥也就是：
$$max(S)=\sum _{T\subset S,T\ne \varnothing }(-1{)}^{|T|-1}min(T)$$
证明的化，大概就是二项式定理。
由于期望的线性性质。
我们有：
$$E(max(S))=\sum _{T\subset S,T\ne \varnothing }(-1{)}^{|T|-1}E(min(T))$$
其中$E(max(S))表示S$中的元素全部都$\ge B_i$的期望,$E(min(S))$表示$S$中的元素至少一个$\ge B_i$的期望。
显然答案 = E ( m a x ( { 1 , 2 , 3... n } ) ) =E(max({1,2,3...n})) =E(max({1,2,3...n}))，这样问题就变成了一个个子问题了。
那么怎么来求$E(\min (s))$呢？
假设$s$已经固定，元素为$i_1,i_2...i_k$。
那么如果在状态$X_{i_1},X_{i_2},X_{i_3}...X_{i_k}$下($X_{i_j}$表示第$i_j$个数有了$X_{i_j}$个且$(0\le X_{i_j}<B_{i_j})$)。
那么我们可以算出到达这个状态的概率,我们设$Sum={\sum }_{i=1}^n{A}_i,S={\sum }_{i_j\in S}{A}_{i_j},X={\sum }_{i_j\in S}{X}_{i_j}$。
则$P(S)=X!\ast \prod [(\frac{A_{i_j}}{S}{)}^{x_{i_j}}\ast \frac{1}{x_{i_j}!}]=X!\ast (\frac{1}{S}{)}^X\ast \prod (A_{i_j}^{x_{i_j}}\ast \frac{1}{x_{i_j}!})$。
很多人可能会有疑问，为什么是$\frac{A_{i_j}}{S}$instead of $\frac{A_{i_j}}{Sum}$。这也是一开始困扰我的。其实是这样的：我们其实是想要集合里最后一个元素$i_j$满足$=x_{i_j}$的要求时别的也恰好满足要求。那么我们一位一位的考虑，对于每一位，我们有$\frac{S}{Sum}$的概率选择$S$中的元素，由于我们当前值考虑集合S中的元素所以我们就考虑选中$S$中的元素的位置考虑。
假设这些位置是$y_1,y_2...y_{|S|}$,那么这些位置可以怎么放置S中的数呢？使得第i个数出现$x_i$次。也就是可重复排列，要实现这个排列的概率就是$\prod [(\frac{A_{i_j}}{S}{)}^{x_{i_j}}]$也就是每一位在$S$中进行选择。
那么有了$P(S)$，我们还需要什么？
对于每一个状态，我们知道到达这个状态的概率。显然我们还要求出走出这个状态的期望步数。
所以答案$E(min(S))=\sum P(S)\ast E(S)$
怎么理解这个柿子呢？对于一个状态，我们有$P(S)$的概率到达，到达了我们一定要走出去对不对？所以我们有$P(S)$的概率走$E(S)$步。
$E(S)$也非常好求，$E(S)=sum/s$
这样对于状态$x_1..x_k$，他的答案$=sum/s\ast X!\ast (\frac{1}{S}{)}^X\ast \prod (A_{i_j}^{x_{i_j}}\ast \frac{1}{x_{i_j}!})$。那么我们在想如果在集合{$x_1,x_2..x_k$}中添加$x_{k+1}$的化答案会变成什么样子？$E将变为E^{\prime }\ast s/(s+a_{k+1})$,$P=P^{\prime }/X!\ast (X+x_{k+1})!\ast S^X/(S+a_{k+1}{)}^{(X+x_{k+1})}\ast A_{k+1}^{x_{k+1}}/(x_{k+1})!$。
显然这只和$S和X$有关。可以想到dp,维护$S,X$和集合的奇偶性。时间复杂度$O(Su{m}^3)$级别的。注意，逆元，快速幂这些要预处理，不然由于大常数多一个log可能会Tle.

/*
{By GWj
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define R(a) cin>>a
#define R2(a,b) cin>>a>>b
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
LL n,a[404],b[404];
const int MOD=998244353;
LL sum=0,fact[404],rfact[404];
LL quick(LL A,LL B){
	if(!B) return 1ll;
	LL tmp=quick(A,B>>1);
	tmp*=tmp;
	tmp%=MOD;
	if(B&1){
		tmp*=A;
		tmp%=MOD;
	}
	return tmp;
}
LL c(LL A,L
LL dp[404][404][404][2],g[404][404][2]; 
LL inv[404][404],mi[404][404]/*(i^j)^(-1)*/;
int main(){
	fastio;
	R(n);
	LL sum2=0;
	rb(i,1,n){
		R2(a[i],b[i]); 
		sum2+=b[i];
		sum+=a[i];
	} 
	fact[0]=1ll;
	rb(i,1,400)
		fact[i]=fact[i-1]*i%MOD;
	rfact[400]=quick(fact[400],MOD-2);
	rfact[0]=1;
	rl(i,399,1){
		rfact[i]=rfact[i+1]*(i+1)%MOD;
	}
	rb(i,0,400)
		rb(j,0,400)
			inv[i][j]=quick(quick(i,j),MOD-2),mi[i][j]=quick(i,j);
	g[0][0][0]=1;
	rb(i,1,n){
		rb(k,0,b[i]-1)
			rb(s,a[i],400){
				rb(x,k,400){
					rep(p,2){
						if(!g[s-a[i]][x-k][p^1]) continue;
						dp[i][s][x][p]+=g[s-a[i]][x-k][p^1]*rfact[x-k]%MOD*fact[x]%MOD*mi[s-a[i]][x-k]%MOD*inv[s][x]%MOD*mi[a[i]][k]%MOD*rfact[k]%MOD*(s-a[i]? (s-a[i])*inv[s][1]%MOD:sum*inv[s][1]%MOD)%MOD;
						dp[i][s][x][p]%=MOD;						
					}
				}
			}
		rb(s,0,400)
			rb(x,0,400)
				rep(p,2)
					g[s][x][p]+=dp[i][s][x][p],g[s][x][p]%=MOD;
	}
	LL rest=0;
	rb(s,0,400)
		if(s)
		rb(x,0,400)
			rep(p,2){
				if(p){
					rest+=g[s][x][p];
					rest%=MOD;		
				}
				else{
					rest-=g[s][x][p];
					rest+=MOD;
					rest%=MOD;
				}
			}
//	cout<<9ll*inv[2][1]%MOD<<endl;
	cout<<rest<<endl;
	return 0;
}
/*
2
1 2
1 1

*/

最后

以上就是欢喜小笼包为你收集整理的AGC038E Gachapon 题解 （min-max 容斥，dp,期望）的全部内容，希望文章能够帮你解决AGC038E Gachapon 题解 （min-max 容斥，dp,期望）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。