题解 P4564 【[CTSC2018]假面】
xukuan
2020-08-11 16:00:31
首先这题时间限制可能有鬼，xjoi上时6s，这份代码在xjoi103上要5-5.2s
**本题解的推导不包括取模**
这题直接维护期望会非常难理解，由于概率非常好处理，所以维护概率
设$f_{i,j}$表示当前第i个人的血量为j的概率
转移方程只有2中情况：被打了掉血或不掉血。特别的，0血的人不会被打
$
f_{i,j}=\left\{
\begin{aligned}
f_{i,j+1}*p+f_{i,j}*(1-p),j \geq 1\\
f_{i,j+1}*p+f_{i,j},j=0\\
\end{aligned}
\right.
$
对于每一个怪而言：
期望直接用 $\sum$概率\*收益 来求
dp类似01背包的压维，倒着跑
$
dp_j=\left\{
\begin{aligned}
g_i*dp_{j-1}+(1-g_i)*dp_j,j \geq 1\\
(1-g_i)*dp_j,j=0
\end{aligned}
\right.
$
理论上可以出答案了，但跑的太慢，所以要优化。
活着就是血量不为0，概率可以直接得出
$g_i=1-f_{i,0}$
然后继续推
没人死就直接抄：当$g_i=1$时$sum_j=dp_{j+1}$
因为是在不死的人里面选，
$
sum_j=\left\{
\begin{aligned}
\frac{dp_j+sum_{j-1}*g_i}{1-g_i},j \geq 1\\
\frac{dp_j}{1-g_i},j=0\\
\end{aligned}
\right.
$
代码：
```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=2010,mod=998244353;
ll n,a[N],f[N][N],g[N],dp[N],sum[N];
inline ll read(){
ll x=0,tmp=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') tmp=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return tmp*x;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
ll y=10,len=1;
while(y<=x){
y=(y<<3)+(y<<1);
len++;
}
while(len--){
y/=10;
putchar(x/y+48);
x%=y;
}
}
inline ll ksm(ll x,ll y){
ll ans=1;
while(y){
if(y&1) ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
inline ll inv(ll x){
return ksm(x,mod-2);
}
int main(){
n=read();
for(ll i=1; i<=n; i++){
a[i]=read();
f[i][a[i]]=1;
}
for(ll q=read(); q; q--){
ll op=read();
if(op==0){
ll x=read(),fenzi=read(),fenmu=read();
ll gailv=fenzi*inv(fenmu)%mod;
f[x][0]=(f[x][0]+f[x][1]*gailv%mod)%mod;
for(ll i=1; i<=a[x]; i++) f[x][i]=(f[x][i]*(mod+1-gailv)%mod+f[x][i+1]*gailv%mod)%mod;
}
else if(op==1){
ll m=read();
for(ll i=1; i<=m; i++){
ll x=read();
g[i]=(mod+1-f[x][0])%mod;
}
memset(dp,0,sizeof(dp));
dp[0]=1;
for(ll i=1; i<=m; i++){
for(ll j=i; j>=0; j--){
if(j) dp[j]=(g[i]*dp[j-1]%mod+(mod+1-g[i])%mod*dp[j]%mod)%mod;
else dp[j]=(mod+1-g[i])%mod*dp[j]%mod;
}
}
for(ll i=1; i<=m; i++){
if(!g[i]){
putchar('0'); putchar(' ');
continue;
}
if(g[i]==1){
for(ll j=0; j<m; j++) sum[j]=dp[j+1];
}
else{
ll x=inv((mod+1-g[i])%mod);
sum[0]=dp[0]*x%mod;
for(ll j=1; j<m; j++) sum[j]=(dp[j]+mod-sum[j-1]*g[i]%mod)%mod*x%mod;
}
ll ans=0;
for(ll j=0; j<m; j++) ans=(ans+sum[j]*inv(j+1)%mod)%mod;
write(g[i]*ans%mod); putchar(' ');
}
putchar('\n');
}
else cout<<"FUCK "<<op<<endl;
}
for(ll i=1; i<=n; i++){
ll ans=0;
for(ll j=1; j<=a[i]; j++) ans=(ans+j*f[i][j])%mod;
write(ans); putchar(' ');
}
putchar('\n');
return 0;
}
```