LOJ #2552. 「CTSC2018」假面 概率期望+背包

比较友好的背包+期望题. 

刚开始没特判概率为 0 的情况，WA 了半天.  

总是还是挺简单的吧，只要会期望的线性性就行. 

code: 

#include <bits/stdc++.h>
#define N 207  
#define M 203   
#define mod 998244353 
#define ll long long 
#define setI(s) freopen(s".in","r",stdin) 
#define setO(s) freopen(s".out","w",stdout)  
using namespace std; 
int f[N][M],val[N],a[N],perc[N],dp[N][N],g[N][N],b[N],INV[N*N];                         
int qpow(int x,int y) 
{
    int tmp=1; 
    for(;y;y>>=1,x=(ll)x*x%mod) 
        if(y&1) tmp=(ll)tmp*x%mod; 
    return tmp; 
} 
void init() 
{
    INV[0]=1;       
    for(int i=1;i<N*N;++i) 
    {
        INV[i]=qpow(i,mod-2);   
    }
}
void calc() 
{      
    int k,t=0,aliv=0;          
    scanf("%d",&k);  
    for(int i=1;i<=k;++i)   
        scanf("%d",&a[i]);
    for(int i=1;i<=k;++i) 
    {  
        perc[i]=0; 
        for(int j=1;j<=100;++j)    
            perc[i]=(ll)(perc[i]+f[a[i]][j])%mod;              
        if(perc[i]==1) ++aliv;    
        else if(perc[i]!=0) b[++t]=i;        
    }   
    memset(dp,0,sizeof(dp));  
    memset(g,0,sizeof(g));      
    dp[0][0]=1;      
    for(int i=1;i<=t;++i) 
    {
        for(int j=0;j<=i;++j)  
        {
            dp[i][j]=(ll)dp[i-1][j]*(1-perc[b[i]]+mod)%mod;    
            if(j) (dp[i][j]+=(ll)dp[i-1][j-1]*perc[b[i]]%mod)%=mod;   
        }
    }     
    for(int i=1;i<=k;++i) 
    {         
        if(perc[i]==0) { printf("0 "); continue; }   
        if(perc[i]==1) 
        {    
            int SUM=0; 
            for(int j=0;j<=t;++j) 
                (SUM+=(ll)dp[t][j]*INV[aliv+j]%mod)%=mod;      
            printf("%d ",SUM);      
            continue;     
        }
        g[i][0]=1; 
        for(int j=1;j<=t;++j) if(i!=b[j]) g[i][0]=(ll)g[i][0]*(1-perc[b[j]]+mod)%mod;       
        int in=qpow((1-perc[i]+mod)%mod,mod-2);   
        for(int j=1;j<t;++j)  
        {   
            g[i][j]=(ll)(dp[t][j]-(ll)g[i][j-1]*perc[i]%mod+mod)%mod;              
            g[i][j]=(ll)g[i][j]*in%mod;
        }  
        int SUM=0;         
        for(int j=0;j<t;++j) 
        {             
            (SUM+=(ll)g[i][j]*perc[i]%mod*INV[j+1+aliv]%mod)%=mod;
        } 
        printf("%d ",SUM); 
    }    
    printf("
");
}
int main() 
{ 
    // setI("input");   
    // setO("input"); 
    init();  
    int n; 
    scanf("%d",&n); 
    for(int i=1;i<=n;++i) 
        scanf("%d",&val[i]),f[i][val[i]]=1;    
    int Q; 
    scanf("%d",&Q); 
    for(int i=1;i<=Q;++i) 
    {
        int op; 
        scanf("%d",&op); 
        if(op==0) 
        {
            int id,u,v; 
            scanf("%d%d%d",&id,&u,&v);        
            int p=(ll)u*qpow(v,mod-2)%mod;     
            for(int j=0;j<=100;++j)         
                f[id][j]=(ll)((ll)f[id][j]*(1-p+mod)%mod+(ll)f[id][j+1]*p%mod+mod)%mod;  
        }      
        else calc();
    }
    for(int i=1;i<=n;++i) 
    {
        int SUM=0;   
        for(int j=0;j<=100;++j)   
            SUM=(ll)(SUM+(ll)j*f[i][j]%mod)%mod;   
        printf("%d ",SUM);  
    }
    return 0;
}