[BZOJ5340][CTSC2018] 假面

居然把id[i]当成i打了,调了2hqwq

题意

对n个值有两种操作:

  • 指定一个大于0的值有p概率将其减1。
  • 指定k个值随机选中一个大于0的值。

求:

  • 每个操作2分别命中k个值的概率。
  • 最后所有值的期望。

模998244353

思路

首先思考询问2。

设$ p[u][i] $表示u的血量为i的概率,每次枚举是否命中即可。

然后就是询问1。

实际上就是询问每个人活着的概率。

设$ f[u][i] $表示除了u的k - 1个人中存活i个的概率。

$ ans[u] = (1 - p[u][0]) \sum_{i = 0}^{k - 1} \frac{f[u][i]}{i + 1}$。

直接转移$ \Theta(Cn ^ 3) $不可做。

我们考虑计算$ g[j][i] $表示递推到第j个人,剩余$ i $个的概率。

递推是$ g[j][i] = g[j]p[u][0] + g[j - 1] (1 - p[u][0]) $。

然后有$ g[k][i] = f[u][i]p[u][0] + f[u][i - 1] (1 - p[u][0]) $。

转化成$ f[u][i] = \frac{g[k][i] - f[u][i - 1] (1 - p[u][0])}{p[u][0]} $。

也可以递推了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#define S 32768
char buf[S];int len = 0,pos = 0;
char buf2[S],*pp = buf2;
inline char __getchar()
{
if(pos == len)pos = 0,len = fread(buf,1,S,stdin);if(pos == len)return '\0';
return buf[pos++];
}
inline void __putchar(char c) {if(pp == buf2 + S)fwrite(buf2,1,S,stdout),pp = buf2;*pp++ = c;}
inline void flush(){fwrite(buf2,1,pp - buf2,stdout);}
inline void putint(int x)
{
if(!x) {__putchar('0');return;}
if(x > 9) putint(x / 10);
__putchar((x % 10) ^ '0');
}
inline int getint()
{
int r = 0,s = 1;char c = __getchar();for(;!isdigit(c);c = __getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = __getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
const int N = 220,MOD = 998244353;
int n,m[N],q;
int p[N][N];int g[N][N],f[N][N],inv[N];
inline void exgcd(int a,int b,int &x,int &y)
{
if(!b){x = 1;y = 0;return;}
exgcd(b,a % b,y,x);
y -= a / b * x;
}
inline int ginv(int x)
{
int r,t;
exgcd(x,MOD,r,t);
return (r % MOD + MOD) % MOD;
}
int main()
{
n = getint();
for(int u = 1;u <= n;u++) p[u][m[u] = getint()] = 1;
for(int u = 0;u < N;u++) inv[u] = ginv(u);
int q = getint();
while(q--)
{
int opt = getint();
if(!opt)
{
int id = getint(),u = getint(),v = getint(),pp = 1LL * u * ginv(v) % MOD;
p[id][0] = (p[id][0] + 1LL * p[id][1] * pp) % MOD;
for(int va = 1;va <= m[id];va++) p[id][va] = (1LL * p[id][va] * (MOD + 1 - pp) + 1LL * p[id][va + 1] * pp) % MOD;
}
else
{
int k = getint();
static int id[N];
for(int i = 1;i <= k;i++) id[i] = getint();
g[0][0] = 1;
for(int j = 1;j <= k;j++)
{
int u = id[j];
g[j][0] = 1LL * g[j - 1][0] * p[u][0] % MOD;
for(int i = 1;i <= j;i++) g[j][i] = (1LL * g[j - 1][i] * p[u][0] + 1LL * g[j - 1][i - 1] * (MOD + 1 - p[u][0])) % MOD;
}
for(int i = 1;i <= k;i++)
{
int u = id[i];
if(!p[u][0]) for(int j = 0;j < k;j++) f[i][j] = g[k][j + 1];
else
{
int invp = ginv(p[u][0]);
f[i][0] = 1LL * g[k][0] * invp % MOD;
for(int j = 1;j < k;j++) f[i][j] = 1LL * (g[k][j] + MOD - (1LL * f[i][j - 1] * (MOD + 1 - p[u][0]) % MOD)) * invp % MOD;
}
int ans = 0;
for(int j = 0;j < k;j++)
{
ans += 1LL * f[i][j] * inv[j + 1] % MOD;
if(ans >= MOD) ans -= MOD;
}
ans = 1LL * ans * (MOD + 1 - p[u][0]) % MOD;
putint(ans);__putchar(i == k ? 10 : 32);
}
}
}
for(int u = 1;u <= n;u++)
{
int ans = 0;
for(int j = 0;j <= m[u];j++) if((ans += (1LL * j * p[u][j] % MOD)) >= MOD) ans -= MOD;
putint(ans);__putchar(u == n ? 10 : 32);
}
flush();
return 0;
}