link
$solution:$
考虑暴力 $dp$ 。
设 $f_{i,j}$ 表示第 $i$ 个人还有 $j$ 血量的概率。因为 $血量\leq100$ 所以这个转移不会超时。
最后直接按照这个值算最后期望即可。
而结界技能 $g_{i,j}$ 表示前 $i$ 个人有 $j$ 人存活的概率，则 $g_{i,j}=g_{i-1,j}\times f_{i,0}+g_{i-1,j-1}\times (1-f_{i,0})$ 。因为每次处理第 $x$ 个人将即可。每次查询时间复杂度 $O(n^3)$ 。
但是这样会超时，考虑如何将一次操作做到 $O(n^2)$ 。
因为这个式子可以人的顺序是无序的， $g_{i,j}=g_{i-1,j}\times f_{i,0}+g_{i-1,j-1}\times (1-f_{i,0})$ ，所以可以倒退 $g$ 式。每次查询时间复杂度 $O(n^2)$ 。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define int long long #define mod 998244353 using namespace std; inline int read(){int f=1,ans=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}return f*ans; } const int MAXN=201; int f[MAXN] [MAXN],n; int ksm(int a,int b){int ans=1;while(b){if(b&1) ans*=a,ans%=mod;a*=a,a%=mod;b>>=1;}return ans; } int q,a[MAXN],cur[MAXN]; int Mod(int x){return ((x%mod)+mod)%mod;} int calc(int x){int ans=0;for(int i=1;i<=a[x];i++){ans+=i*f[x][i];ans%=mod;}return ans; } int p[MAXN],inv[MAXN]; int Num,g[MAXN],k[MAXN]; void Calc_init(){k[0]=0;for(int i=1;i<=Num;i++) k[++k[0]]=p[i];memset(g,0,sizeof(g));g[0]=1;for(int i=1;i<=Num;i++){for(int j=Num;j>=0;j--) {if(j!=0) g[j]=Mod(g[j]*f[k[i]][0])+Mod(g[j-1]*Mod((1-f[k[i]][0]))),g[j]=Mod(g[j]);else g[j]=g[j]*f[k[i]][0],g[j]=Mod(g[j]);}}return; } int G[MAXN]; int Calc(int x){memset(G,0,sizeof(G));int ans=0;if(f[x][0]==0){for(int i=1;i<=Num;i++) ans+=g[i]*inv[i],ans=Mod(ans);return ans;}G[0]=1;for(int i=1;i<=Num;i++) if(p[i]!=x) G[0]*=f[p[i]][0],G[0]=Mod(G[0]);for(int i=0;i<Num;i++){if(i>0) G[i]=Mod(Mod(g[i]-(Mod((Mod(1-f[x][0]))*G[i-1])))*ksm(f[x][0],mod-2));ans+=G[i]*inv[i+1];ans=Mod(ans);}return Mod(ans*Mod(1-f[x][0])); } void debug(){printf("debug\n");for(int i=1;i<=n;i++){for(int j=0;j<=a[i];j++) printf("%lld ",f[i][j]);printf("\n");}printf("===============\n");return; } signed main(){//freopen("3.in","r",stdin);//freopen("3.out","w",stdout);n=read();for(int i=1;i<=n;i++) inv[i]=ksm(i,mod-2);for(int i=1;i<=n;i++) f[i][(a[i]=read())]=1;q=read();while(q--){int opt=read();if(opt==0){int id=read(),u=read(),v=read();int Inv=(u*ksm(v,mod-2))%mod;memset(cur,0,sizeof(cur));cur[0]=Mod(f[id][0]+f[id][1]*Inv);for(int i=1;i<=a[id];i++) cur[i]=Mod(f[id][i]*Mod(1-Inv) +f[id][i+1]*Inv);for(int i=0;i<=a[id];i++) f[id][i]=cur[i];}else{int k=read();Num=k;for(int i=1;i<=k;i++) p[i]=read();Calc_init();for(int i=1;i<=k;i++) printf("%lld ",Calc(p[i]));printf("\n");}}for(int i=1;i<=n;i++) printf("%lld ",calc(i));printf("\n");return 0; }/* 3 1 2 3 3 0 2 1 1 0 2 1 1 1 3 1 2 3 */
