【CTSC2018】假面

【CTSC2018】假面

【CTSC2018】假面

op=0:直接暴力dp就好了,dp[i][j]表示第i个敌人血量剩余j的概率为多少

op=1:还是暴力dp就好了，直接算出还剩余j个人的概率，枚举的时候因为每个人只算存活的概率，所以再根据总的逆推一下就好了

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
const int N=210;
ll f[N],dp[N][N],s[N],inv[N];
int n,id,opt,k,q;
ll u,v;
int m[N],x[N];
ll ksm(ll x,ll y)
{ll ans=1;for (;y;y>>=1,x=(x*x)%mod) if (y&1) ans=(ans*x)%mod;return ans;
}
void change(int id,int p)
{ll nop=(1-p+mod)%mod;dp[id][0]=(dp[id][0]+dp[id][1]*p%mod)%mod;for (int i=1;i<=m[id];i++) dp[id][i]=(dp[id][i+1]*p%mod+dp[id][i]*nop%mod)%mod;	
}
ll rev(ll x){return (mod+1-x)%mod;
}
void solve()
{for (int i=0;i<=k;i++) f[i]=0; f[0]=1;for (int i=1;i<=k;i++) {for (int j=k;j>=0;j--) f[j]=(f[j-1]*rev(dp[x[i]][0])%mod+f[j]*dp[x[i]][0]%mod)%mod;}for (int i=1;i<=k;i++) {ll ans=0;s[k]=0; ll inv1=ksm(rev(dp[x[i]][0]),mod-2);for (int j=k-1;j>=0;j--) {s[j]=(f[j+1]-s[j+1]*dp[x[i]][0]%mod+mod)%mod*inv1%mod;ans=(ans+s[j]*rev(dp[x[i]][0])%mod*inv[j+1]%mod)%mod;}printf("%lld ",ans);}printf("n");
}
int main()
{scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&m[i]),dp[i][m[i]]=1;scanf("%d",&q);inv[0]=1;for (int i=1;i<=n;i++) inv[i]=ksm(i,mod-2);for (int i=1;i<=q;i++){scanf("%d",&opt);if (opt==0) {scanf("%d%lld%lld",&id,&u,&v); change(id,u*ksm(v,mod-2)%mod);}else {scanf("%d",&k);for (int j=1;j<=k;j++) {scanf("%d",&x[j]);}solve();	}}	for (int i=1;i<=n;i++){ll ans=0;for (int j=0;j<=m[i];j++) ans=(ans+dp[i][j]*(ll)j%mod)%mod;printf("%lld ",ans);	}
}