【CTSC2018】假面 | Mrsrz's blog

概率 dp

题目大意：

给定 $n$ 个怪物，第 $i$ 个怪物初始有 $m_i$ 滴血。

有两个操作：

1. 给定 $k,u,v$，第 $k$ 个怪物有 $\frac u v$ 的概率掉一滴血（如果已经为 $0$ 则不管）。
2. 给定 $k$ 以及 $a_1,a_2,\ldots,a_k$，你会在这 $k$ 个怪物中的活着的那些怪物里等概率选一个（都死了则忽略）。问每个怪物被选的期望。

保证 $2$ 操作个数不超过 $C$。

最后还要回答最终每个怪物血量的期望。

题解：

怪物个数和血量比较少，所以可以直接用 $g_{i,j}$ 记录第 $i$ 个怪物有 $j$ 滴血的概率。

执行操作 $1$ 的时候，有 $\frac u v$ 概率血量减少，$1-\frac u v$ 概率血量不变，直接 $O(m)$ 转移即可。

考虑操作 $2$，我们想要对每个怪物，求出其他怪物中存活 $0,1,2,\ldots,k-1$ 个的概率。

令 $f_i(x)=a_ix+(1-a_i)$，其中 $a_i$ 表示 $i$ 活着的概率。

那么我们就需要对每个 $t$ 求 $\prod_{i\neq t}f_i(x)$。

暴力求的总复杂度是 $O(n^3)$。

考虑令 $F(x)=\prod_i f_i(x)$，那么对于 $t$ 来说，我们就是要求 $\frac{F(x)}{f_t(x)}$。后者是一个 $k$ 次多项式除以一个 $1$ 次多项式，可以做到 $O(n)$。因此复杂度为 $O(n^2)$。

算血量的期望，直接枚举剩余血量，然后乘上对应概率即可。

时间复杂度 $O(Cn^2+qm)$。

Code：

#include<iostream>
#include<cstring>
typedef long long LL;
using namespace std;
const int md=998244353;
int F[202][102],n,Q,k,M[202],d[202],g[202],h[202],iv[202];
inline int pow(int a,int b){
    int res=1;
    for(;b;b>>=1,a=(LL)a*a%md)if(b&1)res=(LL)res*a%md;
    return res;
}
void calc(){
    for(int i=1;i<=k;++i){
        for(int j=i;j;--j)
        g[j]=((LL)g[j]*F[d[i]][0]+g[j-1]*(md+1LL-F[d[i]][0]))%md;
        g[0]=(LL)g[0]*F[d[i]][0]%md;
    }
}
void divide(int A,int B){
    int iA=pow(A,md-2);
    static int f[202];
    memcpy(f,g,sizeof f);
    memset(h,0,sizeof h);
    for(int i=k-1;~i;--i){
        int x=f[i+1]*(LL)iA%md;
        h[i]=x;
        f[i]=(f[i]+md-(LL)x*B%md)%md;
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>M[i],F[i][M[i]]=1;
    iv[1]=1;
    for(int i=2;i<=n;++i)iv[i]=(LL)(md-md/i)*iv[md%i]%md;
    for(cin>>Q;Q--;){
        int op;
        cin>>op;
        if(op){
            cin>>k;
            for(int i=1;i<=k;++i)cin>>d[i];
            memset(g,0,sizeof g);
            *g=1;
            calc();
            for(int i=1;i<=k;++i){
                divide((md+1-F[d[i]][0])%md,F[d[i]][0]);
                int ans=0;
                for(int j=0;j<k;++j)ans=(ans+(LL)iv[j+1]*h[j])%md;
                ans=ans*(md+1LL-F[d[i]][0])%md;
                cout<<ans<<" \n"[i==k];
            }
        }else{
            int u,v;
            cin>>k>>u>>v;
            u=(LL)u*pow(v,md-2)%md,v=md+1-u;
            int*f=F[k];
            f[0]=(f[0]+(LL)f[1]*u)%md;
            for(int i=1;i<=M[k];++i)f[i]=((LL)f[i]*v+(LL)f[i+1]*u)%md;
        }
    }
    for(int i=1;i<=n;++i){
        int ans=0;
        for(int j=1;j<=M[i];++j)
        ans=(ans+(LL)j*F[i][j])%md;
        cout<<ans<<" \n"[i==n];
    }
    return 0;
}