我是靠谱客的博主 糟糕帽子,这篇文章主要介绍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

代码

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#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容斥]题目思路代码内容请搜索靠谱客的其他文章。

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

评论列表共有 0 条评论

立即
投稿
返回
顶部