P4564 [CTSC2018] 假面
分析
首先，容易看出结界操作对答案没有任何影响，仅仅只是一个查询操作。那么我们看第一问：
对于针针施放的每个结界技能，它命中各敌人的概率分别是多少。
如果结界要命中第 \(i\) 个人，那么首先要保证他存活。因为我们难以直接判断一个人存活的概率，所以我们可以维护第 \(i\) 个人在生命值为 \(m\) 的概率 \(P_{i,m}\)，那么他死亡的概率就是 \(P_{i,0}\)，存活概率为 \(p_i = 1 - P_{i,0}\)。其次，我们命中的概率还受剩下的人中存活人数的影响，因此我们可以枚举这 \(k\) 个人有 \(j\) 个人存活，概率为 \(f_{k,j}\)，那么我们命中第 \(k\) 个人的概率就是 \(p_k \times \sum _ {j=0}^{k-1} \frac{f_{k,j}}{j+1}\)，表示在第 \(k\) 个人存活的条件下，其余的 \(k-1\) 个人中有 \(j\) 个人存活的概率除以总人数 \(j+1\) 即为命中概率。因为人的顺序不影响答案，因此我们可以总是将要求的第 \(i\) 个人放到第 \(k\) 个位置，那么我们记前 \(k\) 个人有 \(j\) 个人存活的概率为 \(g_{k,j}\)，那么计算除 \(k\) 外的 \(k-1\) 个人就是计算前 \(k-1\) 个人，可得 $f_{k,j} = g_{k-1,j} $。
现在我们来求 \(g_{k,j}\)。首先，显然 \(g_{0,0} = 1\)。然后，当到第 \(i\) 个人时，如果还是无人生还，则需要乘上第 \(i\) 个人的死亡概率 \(1 - p_i\)，即：
然后我们考虑到第 \(i\) 个人时有 \(j\) 个人存活，则有两种情况：
- 这个人存活，那么概率为这个人存活的概率乘上有 \(j-1\) 个人存活的概率，即 \(g_{i-1,j-1} \times p_i\)
- 这个人死亡，那么概率为这个人死亡的概率乘上有 \(j\) 个人存活的概率，即 \(g_{i-1,j} \times ( 1 - p_i )\)
合起来：
于是我们也可以得到 \(g_{i-1,j-1} = \frac{g_{i,j}-g_{i-1,j} \times (1-p_i)}{p_i}\)，将 \(g\) 换成 \(f\) 得到 \(f_{i,j-1} = \frac{g_{i,j} - f_{i,j} \times (1-p_i)}{p_i}\)
再来看第二问，求剩余生命值的期望，我们可以直接将处于每个生命值的概率乘上生命值大小得出。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=205;
const int P=998244353;
int n,q,k[N],m[N];
int ksm(int x,int t)
{int ans=1;while(t){if(t&1)ans=ans*x%P;x=x*x%P;t>>=1;}return ans;
}
int D(int x){return ksm(x,P-2);}//求逆元
int f[N][105],g[N][N],ny[N],a[N],p[N];
signed main()
{cin>>n;for(int i=1;i<=n;i++){cin>>m[i];f[i][m[i]]=1;//开局一定满血ny[i]=D(i);//求 1/i}cin>>q;while(q--){int ty;cin>>ty;if(!ty){int id,u,v;cin>>id>>u>>v;u=u%P*D(v)%P;for(int i=1;i<=m[id];i++){f[id][i-1]=(f[id][i-1]+f[id][i]*u%P)%P;//扣血f[id][i]=(f[id][i]*(1-u+P)%P)%P;//不扣血}}else {int k;cin>>k;for(int i=1;i<=k;i++){cin>>a[i];p[i]=1-f[a[i]][0];//存活概率为1减生命清零（死亡）的概率}g[0][0]=1;//前0个人一定存活0人for(int i=1;i<=k;i++){g[i][0]=g[i-1][0]*(1-p[i])%P;//转移到i依然全死的概率乘上i死亡的概率for(int j=1;j<=k;j++)g[i][j]=(g[i-1][j-1]*p[i]%P+g[i-1][j]*(1-p[i])%P)%P;}for(int i=1;i<=k;i++){int del=D(p[i]),ans=0;int now=g[k][k]*del%P;for(int j=k-1;j>=0;j--)//还剩除第k个外的j个人{//写代码的时候将f[k][j]变成了f[k][j+1]ans=(ans+(now*p[i]%P*ny[j+1])%P)%P;now=(g[k][j]-now*(1-p[i])%P)%P*del%P;}cout<<(ans+P)%P<<' ';}cout<<'\n';}}for(int i=1;i<=n;i++){int ans=0;for(int j=0;j<=m[i];j++)ans=(ans+f[i][j]*j%P)%P;cout<<(ans+P)%P<<' ';//将答案转为正数}
}