我是靠谱客的博主 糟糕帽子,最近开发中收集的这篇文章主要介绍Gachapon[AGC038E][MinMax容斥]题目思路代码,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

文章目录

  • 题目
  • 思路
  • 代码

题目

Luogu
在这里插入图片描述

思路

之前 T T T 神用生成函数讲过,可惜不会了。。。
记录 i i i 达成条件时间为 s i s_i si,抽中概率为 a i a_i ai,集合为 S S S
也就是求 E ( m a x ( S ) ) E(max(S)) E(max(S))
那么容斥可得
E ( m a x ( S ) ) = ∑ T ⊆ S , T ≠ ϕ ( − 1 ) ∣ T ∣ − 1 E ( m i n ( T ) ) E(max(S))=sum_{Tsubseteq S,Tnot=phi}(-1)^{|T|-1}E(min(T)) E(max(S))=TS,T=ϕ(1)T1E(min(T))

然后我就不会了
发现此时操作次数是有限的
考虑期望定义

E ( m i n ( T ) ) = ∑ C , 有 且 仅 有 一 个 i , m a x ( C ) = B i p C ∗ ∑ C i E(min(T))=sum_{C,有且仅有一个 i,max(C)=B_i}p_C*sum C_i E(min(T))=C,i,max(C)=BipCCi
= ∑ C , 有 且 仅 有 一 个 i , m a x ( C ) = B i p 1 p 2 . . . p t ∗ ∑ C i =sum_{C,有且仅有一个 i,max(C)=B_i}p_1p_2...p_t*sum C_i =C,i,max(C)=Bip1p2...ptCi
= ∑ C , ∀ i , C i < B i p 1 p 2 . . . p w ∗ C i =sum_{C,forall i,C_i<B_i}p_1p_2...p_w*C_i =C,i,Ci<Bip1p2...pwCi
也就是到达每个状态的概率乘权值
转化成 C < B C<B C<B 的类似期望的东西之和
根据期望线性性拆分可得
对于 T T T 的一个方案 C C C,它的贡献为(此时右边 a i = s u m a ∗ a i a_i=suma*a_i ai=sumaai 也可以,因为会约掉):
在这里插入图片描述
E ( C ∣ T ) = s u m a ∑ i ∈ T a i ⋅ ( ∑ c i ) ! ∗ ∏ i ∈ T a i c i c i ! ( ∑ i ∈ T a i ) ∑ c i E(C|T)=frac{suma}{sum_{iin T} a_i}cdotfrac{(sum c_i)!*prod_{iin T}frac{a_i^{c_i}}{c_i!}}{(sum_{iin T} a_i)^{sum c_i}} E(CT)=iTaisuma(iTai)ci(ci)!iTci!aici
注意后面代表选择 T T T 情况抽出 C C C 的概率,但此时权值是抽中 T T T 1 1 1 次的期望次数,而不是 1 1 1
发现只和 ∑ a i , ∑ c i sum a_i,sum c_i aici 有关
定义状态 f i , j , k : 前 i 个 选 择 a i 和 为 j , 选 了 k 个 的 乘 积 和 f_{i,j,k}:前 i 个选择 a_i 和为 j,选了 k 个的乘积和 fi,j,kiaijk:、
转移时间复杂度为 ∑ A i ∗ ( ∑ B i ) 2 sum A_i*(sum B_i)^2 Ai(Bi)2
对于 i , j , k i,j,k i,j,k 转移次数是 B i B_i Bi

代码

#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<climits>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
int read(){
	int f=0,x=0;char c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=1;c=getchar();}
	while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return !f?x:-x;
}
#define mp make_pair
const int MAXN=400;
const int Mod=998244353;
int A[MAXN+5],B[MAXN+5];
int f[MAXN+5][MAXN+5];
int Add(int x,int y){x+=y;return x>=Mod?x-Mod:x;}
int Sub(int x,int y){x-=y;return x<0?x+Mod:x;}
int Mul(LL x,int y){x*=y;return x>=Mod?x%Mod:x;}
int Pow(int x,int y){
	int ret=1;
	while(y){
		if(y&1) ret=1ll*ret*x%Mod;
		x=1ll*x*x%Mod,y>>=1;
	}
	return ret;
}
int fac[MAXN+5],inv[MAXN+5];
int main(){//f[i][j][k]:前i个选j个概率和为k的期望系数
	int n=read(),s=0;
	fac[0]=1;
	for(int i=1;i<=400;i++)
		fac[i]=1ll*fac[i-1]*i%Mod;
	inv[400]=Pow(fac[400],Mod-2);
	for(int i=399;i>=0;i--)
		inv[i]=1ll*inv[i+1]*(i+1)%Mod;
	for(int i=1;i<=n;i++)
		A[i]=read(),B[i]=read(),s+=A[i];
	f[0][0]=Mod-1;
	for(int i=1,sb=B[1];i<=n;i++,sb+=B[i])
		for(int j=s;~j;j--)
			for(int k=sb;~k;k--)
				if(f[j][k])
					for(int l=0,t=1;l<B[i];l++,t=Mul(t,A[i]))
						f[j+A[i]][k+l]=Sub(f[j+A[i]][k+l],Mul(t,Mul(inv[l],f[j][k])));
	int ans=0;
	for(int j=1;j<=s;j++)
		for(int k=0,p=Pow(j,Mod-2),t=1,w=Mul(s,Pow(j,Mod-2));k<=400;k++,t=Mul(t,p))
			ans=Add(ans,Mul(Mul(Mul(f[j][k],t),w),fac[k]));
    printf("%dn",ans);
	return 0;
}

最后

以上就是糟糕帽子为你收集整理的Gachapon[AGC038E][MinMax容斥]题目思路代码的全部内容,希望文章能够帮你解决Gachapon[AGC038E][MinMax容斥]题目思路代码所遇到的程序开发问题。

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

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(55)

评论列表共有 0 条评论

立即
投稿
返回
顶部