[CTSC2018]假面(概率DP)

考场上以为CTSC的概率期望题都不可做，连暴力都没写直接爆零。

结果出来发现全场70以上，大部分AC，少于70的好像极少，感觉血亏。

设a[i][j]表示到当前为止第i个人的血量为j的概率（注意特判血量为0的情况）。那么a[i][0]则为这个人的死亡率。

设dp[i]表示当前指定集合中，有i个人存活的概率。

可以发现a[][]和是可以推导出dp[]的，直接DP可以得到70分。同时发现dp[]存在逆变换，所以复杂度就可以通过了。

但是如果写丑了还是会被卡掉，优化方法可以加快读，减少取模次数，以及预处理逆元。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define rep(i,l,r) for (int i=l; i<=r; i++)

 typedef long long ll;

 using namespace std;

 const int N=,mod=;

 int n,K,Q,op,id,u,v,ans,h[N],s[N],inv[N],dp[N],dp1[N],a[N][N];

 int rd(){

     int x=; bool t=; char ch=getchar();

     while (ch<'' || ch>'') t|=(ch=='-'),ch=getchar();

     while (ch>='' && ch<='') x=x*+ch-'',ch=getchar();

     if (t) return -x; else return x;

 }

 int ksm(int a,int b){

     int res;

     for (res=; b; a=1ll*a*a%mod,b>>=)

         if (b & ) res=1ll*res*a%mod;

     return res;

 }

 int main(){

     freopen("faceless.in","r",stdin);

     freopen("faceless.out","w",stdout);

     n=rd(); rep(i,,n) h[i]=rd(),a[i][h[i]]=;

     inv[]=; rep(i,,n) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

     for (Q=rd(); Q--; ){

         op=rd();

         if (op==){

             id=rd(); u=rd(); v=rd(); int vv=ksm(v,mod-);

             a[id][]=(a[id][]+1ll*a[id][]*u%mod*vv%mod)%mod;

             rep(i,,h[id])

                 a[id][i]=(1ll*a[id][i]*(-1ll*u*vv%mod+mod)+1ll*a[id][i+]*u%mod*vv)%mod;

         }else{

             K=rd();

             rep(i,,K) dp[i]=; dp[]=;

             rep(i,,K){

                 s[i]=rd();

                 for (int j=i; ~j; j--) dp[j]=(1ll*(-a[s[i]][]+mod)*dp[j-]+1ll*a[s[i]][]*dp[j])%mod;

             }

             rep(i,,K){

                 ans=; rep(j,,K) dp1[j]=;

                 if (!a[s[i]][]) rep(j,,K-) ans=(ans+1ll*dp[j+]*inv[j+])%mod;

                 else{

                     int res=; rep(j,,K) if (j!=i) res=1ll*res*a[s[j]][]%mod; dp1[]=res;

                     rep(j,,K-){

                         if (j>) dp1[j]=1ll*(dp[j]-1ll*(-a[s[i]][])*dp1[j-]%mod+mod)%mod*ksm(a[s[i]][]%mod,mod-)%mod;

                         ans=(ans+1ll*dp1[j]*inv[j+])%mod;

                     }

                 }

                 ans=1ll*ans*(-a[s[i]][]+mod)%mod; printf("%d ",ans);

             }

             puts("");

         }

     }

     rep(i,,n){

         ans=;

         rep(j,,h[i]) ans=(ans+1ll*j*a[i][j])%mod;

         printf("%d ",ans);

     }

     puts("");

     return ;

 }