正题
题目大意:https://www.luogu.com.cn/problem/P4564
题目大意
n
n
n个人第
i
i
i个有
m
i
m_i
mi点血，每次有操作
有
p
p
p的概率对一个人造成
1
1
1点伤害（如果死了就不算，
p
p
p每次都不同）给出若干个人，对里面存活的人随机选择一个，求每个人被选中的概率
最后要求输出每个人的期望血量
解题思路
p
i
,
j
p_{i,j}
pi,j表示第
i
i
i个人剩余
j
j
j点血的概率。这个可以
O
(
Q
n
)
O(Qn)
O(Qn)的时间内维护。
考虑如何计算概率，因为存活人数的不同，产生的贡献也不同，我们设
f
i
,
j
f_{i,j}
fi,j表示第
i
i
i个人以外的人存活了
j
j
j个的概率，这个很容易可以在
O
(
C
n
2
)
O(Cn^2)
O(Cn2)的时间内算，但是这样显然过不去。
所以我们要进行优化，我们可以在
O
(
n
2
)
O(n^2)
O(n2)的时间内算出
g
i
g_i
gi表示所有人里存活
i
i
i个人的概率，也就是有（以下为了方便定义
p
i
p_i
pi表示
1
−
p
i
,
0
1-p_{i,0}
1−pi,0即第
i
i
i个人存活的概率）：
g
i
=
g
i
−
1
∗
p
u
+
g
i
∗
(
1
−
p
u
)
g_i=g_{i-1}*p_u+g_{i}*(1-p_u)
gi=gi−1∗pu+gi∗(1−pu)
显然我们可以从
f
u
f_{u}
fu推到
g
g
g
g
i
=
f
u
,
i
∗
(
1
−
p
u
)
+
f
u
,
i
−
1
∗
p
u
g_i=f_{u,i}*(1-p_u)+f_{u,i-1}*p_u
gi=fu,i∗(1−pu)+fu,i−1∗pu可以回推回来也就是
⇒
f
u
,
i
=
g
i
−
f
u
,
i
−
1
∗
p
u
1
−
p
u
\Rightarrow f_{u,i}=\frac{g_i-f_{u,i-1}*p_u}{1-p_u}
⇒fu,i=1−pugi−fu,i−1∗pu
这样我们就可以在
O
(
C
n
2
)
O(Cn^2)
O(Cn2)的时间内算出所有的
f
u
,
i
f_{u,i}
fu,i来统计答案。因为求逆元也很慢，所以我们先线性推逆元预处理一下比较小的值。
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std
;
const int XJQ
=998244353;
int n
,Q
,p
[210][210],c
[210],g
[210],f
[210],in
[210];
int power(int x
,int b
){
int ans
=1;x
%=XJQ
;
while(b
){
if(b
&1)ans
=1ll*ans
*x
%XJQ
;
x
=1ll*x
*x
%XJQ
;b
>>=1;
}
return ans
;
}
int read() {
int x
=0,f
=1; char c
=getchar();
while(!isdigit(c
)) {if(c
=='-')f
=-f
;c
=getchar();}
while(isdigit(c
)) x
=(x
<<1)+(x
<<3)+c
-48,c
=getchar();
return x
*f
;
}
void print(int x
){
if (x
>9) print(x
/10); putchar(x
%10+48); return;
}
signed main()
{
n
=read();
for(int i
=1;i
<=n
;i
++)p
[i
][read()]=1;
Q
=read();in
[1]=1;
for(int i
=2;i
<=n
;i
++)
in
[i
]=(long long)XJQ
-(long long)XJQ
/i
*in
[XJQ
%i
]%XJQ
;
while(Q
--){
int op
=read();
if(op
==0){
int id
=read(),u
=read(),v
=read();
u
=1ll*u
*power(v
,XJQ
-2)%XJQ
;
p
[id
][0]=(p
[id
][0]+1ll*p
[id
][1]*u
)%XJQ
;
for(int i
=1;i
<=100;i
++)
p
[id
][i
]=(1ll*p
[id
][i
+1]*u
+1ll*p
[id
][i
]*(1-u
+XJQ
))%XJQ
;
}
else{
int k
=read(),x
,ans
=0;
for(int i
=1;i
<=k
;i
++)c
[i
]=read();
memset(g
,0,sizeof(g
));g
[0]=1;
for(int i
=1;i
<=k
;i
++){
for(int j
=i
;j
>=1;j
--)
g
[j
]=(1ll*g
[j
]*p
[c
[i
]][0]+1ll*(1-p
[c
[i
]][0]+XJQ
)*g
[j
-1])%XJQ
;
g
[0]=1ll*g
[0]*p
[c
[i
]][0]%XJQ
;
}
for(int i
=1;i
<=k
;i
++){
int ans
=0,z
=(1-p
[c
[i
]][0]+XJQ
)%XJQ
,inv
=power(p
[c
[i
]][0],XJQ
-2);
if(p
[c
[i
]][0]==1){
printf("0 ");
continue;
}
if(p
[c
[i
]][0]==0)
for(int j
=0;j
<k
;j
++)
f
[j
]=g
[j
+1];
else{
f
[0]=1ll*g
[0]*inv
%XJQ
;
for(int j
=1;j
<k
;j
++){
f
[j
]=(g
[j
]-1ll*f
[j
-1]*z
%XJQ
+XJQ
)%XJQ
;
f
[j
]=1ll*f
[j
]*inv
%XJQ
;
}
}
for(int j
=0;j
<k
;j
++)
(ans
+=1ll*f
[j
]*in
[j
+1]%XJQ
)%=XJQ
;
print(1ll*ans
*z
%XJQ
);putchar(' ');
}
putchar('\n');
}
}
for(int i
=1;i
<=n
;i
++){
int ans
=0;
for(int j
=1;j
<=100;j
++)
ans
=(ans
+1ll*p
[i
][j
]*j
%XJQ
)%XJQ
;
print(ans
);putchar(' ');
}
}
