网站开发设计培训价格,阿丰 做网站,html5网页制作实例视频教程,企业文化视频制作正题
题目大意:https://www.luogu.com.cn/problem/P4564 题目大意 nnn个人第iii个有mim_imi点血#xff0c;每次有操作
有ppp的概率对一个人造成111点伤害#xff08;如果死了就不算#xff0c;ppp每次都不同#xff09;给出若干个人#xff0c;对里面存活的人随机选择…正题
题目大意:https://www.luogu.com.cn/problem/P4564 题目大意
nnn个人第iii个有mim_imi点血每次有操作
有ppp的概率对一个人造成111点伤害如果死了就不算ppp每次都不同给出若干个人对里面存活的人随机选择一个求每个人被选中的概率
最后要求输出每个人的期望血量 解题思路
pi,jp_{i,j}pi,j表示第iii个人剩余jjj点血的概率。这个可以O(Qn)O(Qn)O(Qn)的时间内维护。
考虑如何计算概率因为存活人数的不同产生的贡献也不同我们设fi,jf_{i,j}fi,j表示第iii个人以外的人存活了jjj个的概率这个很容易可以在O(Cn2)O(Cn^2)O(Cn2)的时间内算但是这样显然过不去。
所以我们要进行优化我们可以在O(n2)O(n^2)O(n2)的时间内算出gig_igi表示所有人里存活iii个人的概率也就是有以下为了方便定义pip_ipi表示1−pi,01-p_{i,0}1−pi,0即第iii个人存活的概率 gigi−1∗pugi∗(1−pu)g_ig_{i-1}*p_ug_{i}*(1-p_u)gigi−1∗pugi∗(1−pu)
显然我们可以从fuf_{u}fu推到ggg gifu,i∗(1−pu)fu,i−1∗pug_if_{u,i}*(1-p_u)f_{u,i-1}*p_ugifu,i∗(1−pu)fu,i−1∗pu可以回推回来也就是 ⇒fu,igi−fu,i−1∗pu1−pu\Rightarrow f_{u,i}\frac{g_i-f_{u,i-1}*p_u}{1-p_u}⇒fu,i1−pugi−fu,i−1∗pu
这样我们就可以在O(Cn2)O(Cn^2)O(Cn2)的时间内算出所有的fu,if_{u,i}fu,i来统计答案。因为求逆元也很慢所以我们先线性推逆元预处理一下比较小的值。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecctype
using namespace std;
const int XJQ998244353;
int n,Q,p[210][210],c[210],g[210],f[210],in[210];
int power(int x,int b){int ans1;x%XJQ;while(b){if(b1)ans1ll*ans*x%XJQ;x1ll*x*x%XJQ;b1;}return ans;
}
int read() {int x0,f1; char cgetchar();while(!isdigit(c)) {if(c-)f-f;cgetchar();}while(isdigit(c)) x(x1)(x3)c-48,cgetchar();return x*f;
}
void print(int x){if (x9) print(x/10); putchar(x%1048); return;
}
signed main()
{nread();for(int i1;in;i)p[i][read()]1;Qread();in[1]1;for(int i2;in;i)in[i](long long)XJQ-(long long)XJQ/i*in[XJQ%i]%XJQ;while(Q--){int opread();if(op0){int idread(),uread(),vread();u1ll*u*power(v,XJQ-2)%XJQ;p[id][0](p[id][0]1ll*p[id][1]*u)%XJQ;for(int i1;i100;i)p[id][i](1ll*p[id][i1]*u1ll*p[id][i]*(1-uXJQ))%XJQ;}else{int kread(),x,ans0;for(int i1;ik;i)c[i]read();memset(g,0,sizeof(g));g[0]1;for(int i1;ik;i){for(int ji;j1;j--)g[j](1ll*g[j]*p[c[i]][0]1ll*(1-p[c[i]][0]XJQ)*g[j-1])%XJQ;g[0]1ll*g[0]*p[c[i]][0]%XJQ;}for(int i1;ik;i){int ans0,z(1-p[c[i]][0]XJQ)%XJQ,invpower(p[c[i]][0],XJQ-2);if(p[c[i]][0]1){printf(0 );continue;}if(p[c[i]][0]0)for(int j0;jk;j)f[j]g[j1];else{f[0]1ll*g[0]*inv%XJQ;for(int j1;jk;j){f[j](g[j]-1ll*f[j-1]*z%XJQXJQ)%XJQ;f[j]1ll*f[j]*inv%XJQ;}}for(int j0;jk;j)(ans1ll*f[j]*in[j1]%XJQ)%XJQ;print(1ll*ans*z%XJQ);putchar( );}putchar(\n); }}for(int i1;in;i){int ans0;for(int j1;j100;j)ans(ans1ll*p[i][j]*j%XJQ)%XJQ;print(ans);putchar( );}
}
