文章目录
- 题目
- 思路
- 代码
题目
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))=T⊆S,T=ϕ∑(−1)∣T∣−1E(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)=Bi∑pC∗∑Ci
=
∑
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)=Bi∑p1p2...pt∗∑Ci
=
∑
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<Bi∑p1p2...pw∗Ci
也就是到达每个状态的概率乘权值
转化成
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=suma∗ai 也可以,因为会约掉):
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(C∣T)=∑i∈Taisuma⋅(∑i∈Tai)∑ci(∑ci)!∗∏i∈Tci!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
∑ai,∑ci 有关
定义状态
f
i
,
j
,
k
:
前
i
个
选
择
a
i
和
为
j
,
选
了
k
个
的
乘
积
和
f_{i,j,k}:前 i 个选择 a_i 和为 j,选了 k 个的乘积和
fi,j,k:前i个选择ai和为j,选了k个的乘积和:、
转移时间复杂度为
∑
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容斥]题目思路代码内容请搜索靠谱客的其他文章。
发表评论 取消回复