题解 P4564 【[CTSC2018]假面】
Kelin
2018-05-21 12:56:10
## [题意](https://blog.csdn.net/BeNoble_/article/details/80390659)
$n$个人$,Q$个操作$,$第$i$个人有$m_i$滴血$,$有两种操作
$1.$以$p$的概率使$u$掉$1$点血
$2.$给出$k$个人$,$从这些人中等概率地选出$1$个$,$求每个人被选中的概率
最后求每个人剩余血量的期望
---
## 题解
考虑怎么求每个人剩余的血的期望
用$p_u[i]$表示$u$剩余$i$点血的概率$\Rightarrow E_u=\sum_{i=0}^{m_i}ip_u[i]$
这个$p_u$是可以用背包维护的$($而且非常好理解$,$初值$p_u[m_u]=1)$
$p_u'[0]=p_u[0]+p_u[1]*p$
$p_u'[i]=p_u[i]*(1-p)+p_u[i+1]*p,i\in[1,m_u]$
操作$1$就用上面的$dp$维护即可
考虑怎么处理操作$2$
实际上操作$2$只需要知道每个人活下来的概率即可$,$即$px_u=1-p_u[0]$
对于$k$个人中的每个人用简单的数学知识可以得到选中$u$的概率是
$$px_u\sum_{i=0}^{k-1}\frac{f_u[i]}{i+1}$$
$f_u[i]$表示除了$u$之外只有$i$个人活着的概率
枚举另外一个人$v,$可以得到
$$f_u'[i]=px_v*f_u[i-1]+(1-px_v)*f_u[i]$$
于是乎对于每一个人做一遍这样的$dp$即可
复杂度$O(Qm+Cn^3)$~~显然过不了~~
考虑如果知道还活着任意$i$个人的概率$g[i]$和$px_u,$能不能知道$f_u[i]?$
~~显然是可以的~~可以发现上面那个$dp$没有人的限制$,$所以可以倒过来
$$f_u[i]=\frac{f'_u[i]-px_v*f_u[i-1]}{1-px_v}$$
因为这个$v$是随意的$,$所以有
$$f_u[i]=\frac{g[i]-px_u*f_u[i-1]}{1-px_u}$$
当$px_u=1$时$f_u[i]=g[i+1]$
$g$可以通过一个$n^2$的$dp$求出
$$g[i]=px_u*g[i-1]+(1-px_u)*g[i]$$
对于每一个人只要再$O(n)$逆转移一下即可
总时间复杂度$O(Qm+Cn^2)$
```
#include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
template<class T>inline void sd(T&x){
char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48;
while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y;
}
char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
template<class T>inline void we(T x){
if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++C]=z[Z],--Z);sr[++C]=' ';
}
const int N=205,P=998244353;
typedef int arr[N];
typedef long long ll;
int n,m,q;arr f,g,w,px,inv,p[N];
int Inv(int x){return x<N?inv[x]:(ll)(P-P/x)*Inv(P%x)%P;}
inline int pls(int a,int b){return a+=b,a<P?a:a-P;}
inline int sub(int a,int b){return a-=b,a<0?a+P:a;}
int main(){
#ifndef ONLINE_JUDGE
file("s");
#endif
sd(n);
fp(i,1,n)sd(w[i]),p[i][w[i]]=1;inv[1]=1;
fp(i,2,N-1)inv[i]=(ll)(P-P/i)*inv[P%i]%P;
sd(q);int op,x,a,b,tp=0;
while(q--){
sd(op);
if(op){
sd(m);fp(i,1,m)sd(x),px[i]=sub(1,p[x][0]),g[i]=0;g[0]=1;
fp(i,1,m)fd(j,i,0)g[j]=((j?(ll)px[i]*g[j-1]%P:0ll)+(ll)sub(1,px[i])*g[j])%P;
fp(i,1,m){
if(!px[i]){we(0);continue;}
if(px[i]==1)fp(j,0,m-1)f[j]=g[j+1];
else{
x=Inv(sub(1,px[i]));f[0]=(ll)g[0]*x%P;
fp(j,1,m-1)f[j]=(ll)sub(g[j],(ll)f[j-1]*px[i]%P)*x%P;
}
fp(j,0,m-1)tp=pls(tp,(ll)f[j]*inv[j+1]%P);
we((ll)px[i]*tp%P);tp=0;
}sr[++C]='\n';
}else{
sd(x),sd(a),sd(b);
a=(ll)a*Inv(b)%P,b=sub(1,a);
p[x][0]=pls(p[x][0],(ll)p[x][1]*a%P);
fp(i,1,w[x])p[x][i]=((ll)p[x][i+1]*a+(ll)p[x][i]*b)%P;
}
}
fp(i,1,n){
tp=0;
fp(j,1,w[i])tp=pls(tp,(ll)j*p[i][j]%P);
we(tp);
}
return Ot(),0;
}
```
---
~~出题人说这是一道NOIP中档题~~