首页 > 其他 > 详细

[bzoj5340]假面

时间:2019-09-15 19:25:40      阅读:80      评论:0      收藏:0      [点我收藏+]

修改:维护g[i][j]表示第i个数为j的概率,从前往后转移
转移方程:g[id][i]=g[id][i-1]*p+g[id][i]*(1-p),初始g[i][a[i]]=1
询问:对于每一个人i,输出sigma(P(除了i有j个正数)/(j+1))*P(i是正数)
P(i是正数)就是1-g[i][0],以下简写为h[i],j+1的逆元可以预处理出来
考虑P(除了i有j个正数),用f[j]表示前i个数有j个正数的概率
转移方程(滚动后):f[j]=f[j]*g[i][0]+f[j-1]*h[i],初始[0]=1
那么相当于要去掉i,设f‘[j]=P(除了i有j个正数),则有转移:
f[j]=f‘[j]*g[i][0]+f‘[j-1]*h[i],f‘[j]=(f[j]-f‘[j-1]*h[i])/g[i][0](递推即可) (需要特判g[i][0]=0,此时相当于他一定活着,那么f‘[j]=f[j+1])
最终的期望可以用g来算,对于第i个人,即sigma(j*g[i][j]) ,总时间复杂度为o(Qn+Cn^2logn),可以通过

技术分享图片
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define mod 998244353
 4 int n,m,p,x,y,z,a[205],f[205],inv[205],g[205][105];
 5 int ksm(int n,int m){
 6     if (!m)return 1;
 7     int s=ksm(n,m>>1);
 8     s=1LL*s*s%mod;
 9     if (m&1)s=1LL*s*n%mod;
10     return s;
11 }
12 int main(){
13     scanf("%d",&n);
14     inv[0]=inv[1]=1;
15     for(int i=1;i<=n;i++){
16         scanf("%d",&x);
17         g[i][x]=1;    
18     }
19     for(int i=2;i<=n;i++)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
20     scanf("%d",&m);
21     for(int i=1;i<=m;i++){
22         scanf("%d%d",&p,&x);
23         if (!p){
24             scanf("%d%d",&y,&z);
25             y=1LL*y*ksm(z,mod-2)%mod;
26             g[x][0]=(g[x][0]+1LL*g[x][1]*y)%mod;
27             for(int j=1;j<=100;j++)
28                 g[x][j]=(g[x][j]*(mod+1LL-y)+1LL*g[x][j+1]*y)%mod;
29         }
30         else{
31             f[0]=1;
32             for(int j=1;j<=x;j++)f[j]=0;
33             for(int j=1;j<=x;j++){
34                 scanf("%d",&y);
35                 a[j]=g[y][0];
36                 for(int k=j;k;k--)
37                     f[k]=(1LL*f[k]*a[j]+f[k-1]*(mod+1LL-a[j]))%mod;
38                 f[0]=1LL*f[0]*a[j]%mod;
39             }
40             for(int j=1;j<=x;j++){
41                 y=z=0;
42                 int t=ksm(a[j],mod-2);
43                 for(int k=0;k<x;k++){
44                     if (!a[j])z=f[k+1];
45                     else z=(f[k]-z*(mod+1LL-a[j])%mod+mod)*t%mod;
46                     y=(y+1LL*z*inv[k+1])%mod;
47                 }
48                 printf("%lld ",y*(mod+1LL-a[j])%mod);
49             }
50             printf("\n");
51         }
52     }
53     for(int i=1;i<=n;i++){
54         x=0;
55         for(int j=1;j<=100;j++)x=(x+1LL*j*g[i][j])%mod;
56         printf("%d ",x);
57     }
58 }
View Code

 

[bzoj5340]假面

原文:https://www.cnblogs.com/PYWBKTDA/p/11523439.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!