概述
文章目录
- 题目
- 思路
- 代码
题目
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 次
代码
#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容斥]题目思路代码所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复