题目大意：
有(n(n≤200))个人，每个人初始血量为(m_i(mi≤100))对这些人进行(q(q≤2×10^5))次操作，操作包含以下两种：
1. 选择编号为idid的人，有pp的概率扣掉一滴血；
2. 编号为(id1,id2,…,idk)的k个人，等概率的从这k个人中选取一个活着的人封印，问这k个人中每个人被封印的概率是多少。
处理完所有操作后，求每个人最终血量的期望。
题解
n,m都很小,所以第一问肥肠简单
用(f[i][j])表示第(i)个人有(j)滴血的概率然后直接背包就好了
注意当j=0时不要从这一层转移,只从上一层转移,因为如果已经死了就不会被打到了
然后第二问怎么求?
用(g[i][j])表示选择一个人u后前i个人剩j个的概率
(g[i][j] = g[i-1][j-1]*liv[u] + g[i-1][j]*die[u])
然后再对选择的这个人求答案(Ans = sum_{i = 0}^{i<=k}{frac{g[k-1][i] * liv[u]}{i+1}})
这样就是(O(Cn^3))了
然后考虑优化
显然(g[][])可以去掉第一维
可以发现(g[])似乎可以倒着推?
(g_{last}[j] = (g[j] - g_{last}[j-1] * liv[i]) / die[i])
所以可以(O(k^2))先预处理出g[]
然后倒着推出(g_{last})
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
# define LL long long
const int M = 205 ;
const LL mod = 998244353 ;
using namespace std ;
inline LL read() {
char c = getchar() ; LL x = 0 , w = 1 ;
while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
return x*w ;
}
int n , Num , peo[M] ;
LL hp[M] , f[M][M] , inv[M] ;
LL liv[M] , die[M] , t[M] , g[M] ;
void Exgcd(LL a , LL b , LL &x , LL &y) {
if(b == 0) {
x = 1 ; y = 0 ;
return ;
}
Exgcd(b , a % b , x , y) ;
LL tmp = x ;
x = y ;
y = tmp - a / b * y ;
}
inline LL Inv(LL a) {
LL x , y ;
Exgcd(a , mod , x , y) ;
return (x + mod) % mod ;
}
// g[i] 表示有i个人存活的概率
inline void Solve() {
Num = read() ;
for(int i = 1 ; i <= Num ; i ++) {
peo[i] = read() ;
die[i] = f[peo[i]][0] ;
liv[i] = (1 - die[i] + mod) % mod ;
}
memset(g , 0 , sizeof(g)) ;
g[0] = 1 ;
for(int i = 1 ; i <= Num ; i ++)
for(int j = i ; j >= 0 ; j --) {
g[j] = (g[j] * die[i]) % mod ;
if(j > 0) g[j] = (g[j] + g[j - 1] * liv[i] + mod) % mod ;
}
LL Ans = 0 , x ;
for(int i = 1 ; i <= Num ; i ++) {
Ans = 0 ; x = Inv(die[i]) ;
if(die[i]) {
t[0] = (g[0] * x) % mod ;
for(int j = 1 ; j < Num ; j ++)
t[j] = ((g[j] - (t[j - 1] * liv[i]) % mod + mod) % mod * x) % mod ;
}
else for(int j = 0 ; j < Num ; j ++) t[j] = g[j + 1] ;
for(int j = 0 ; j < Num ; j ++)
Ans = (Ans + t[j] * ((liv[i] * inv[j + 1]) % mod) % mod + mod) % mod ;
printf("%lld ",Ans) ;
}
printf("
") ;
}
int main() {
n = read() ; inv[1] = 1 ;
for(int i = 2 ; i <= n + 1 ; i ++) inv[i] = Inv(i) ;
for(int i = 1 ; i <= n ; i ++) {
hp[i] = read() ;
f[i][hp[i]] = 1 ;
}
int Q = read() ;
LL opt , x , u , v , p ;
while(Q --) {
opt = read() ;
if(opt == 0) {
x = read() ; u = read() , v = read() ;
p = (u * Inv(v)) % mod ;
for(int j = 0 ; j <= hp[x] ; j ++) {
if(j) f[x][j] = (f[x][j] * (1 - p + mod)) % mod ;
if(j < hp[x]) f[x][j] = (f[x][j] + f[x][j + 1] * p + mod) % mod ;
}
}
else Solve() ;
}
LL Ans = 0 ;
for(int i = 1 ; i <= n ; i ++) {
Ans = 0 ;
for(int j = 1 ; j <= hp[i] ; j ++)
Ans = (Ans + f[i][j] * j) % mod ;
printf("%lld ",Ans) ;
}
printf("
") ;
return 0 ;
}