Loj 2552 假面

Posted on | Views:

背包.

考虑对每个人 $i$ ,维护 $p(i,j)$ 表示他剩余了 $j$ 点生命值的概率.

对于一次锁定操作,更新对应的 $p(i)$ 即可.

对于一次结界操作,考虑 $i$ 被命中的概率,需要算出除 $i$ 之外还有 $x$ 个人存活的概率 $q(i,x)$ 来统计答案.

先算出 $q(0,x)$ 表示有 $x$ 个人存活的概率,相当于做了一个背包,要算 $q(i)$ 时,将 $i$ 的贡献从 $q(0)$ 中撤掉即可.

初始生命值 $m_i$ 可以看做与 $n$ 同阶,时间复杂度 $O(qn+n^2C)$ .

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int P = 998244353;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
int fpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
const int N = 200 + 10;
int n, Q, mx[N], p[N][N], q[N], tmp[N], inv[N];
void modify()
{
	int x = read(), up = read(), down = read();
	int Pr = mul(up, fpow(down, P - 2)); // pr of get attacked
	for (int i = 0; i <= mx[x]; ++i)
	{
		if (i == 0)
			p[x][i] = add(mul(Pr, p[x][i + 1]), p[x][i]);
		else
			p[x][i] = add(mul(Pr, p[x][i + 1]), mul(add(1, P - Pr), p[x][i]));
	}
}
int t[N];
void query()
{
	for (int i = 1; i <= n; ++i)
		q[i] = 0;
	q[0] = 1;
	int k = read();
	for (int i = 1; i <= k; ++i)
		t[i] = read();
	for (int i = 1; i <= k; ++i)
	{
		int Pr = add(1, P - p[t[i]][0]); // pr of alive
		if (!Pr)
			continue;
		for (int j = n; j >= 0; --j)
		{
			inc(q[j + 1], mul(q[j], Pr));
			q[j] = mul(q[j], add(1, P - Pr));
		}
	}
	for (int i = 0; i <= n; ++i)
		tmp[i] = q[i];
	for (int i = 1; i <= k; ++i)
	{
		int Pr = add(1, P - p[t[i]][0]);
		if (!Pr)
		{
			write(0, ' ');
			continue;
		}
		if (Pr == 1)
		{
			for (int j = 0; j <= n; ++j)
				q[j] = q[j + 1];
		}
		else
		{
			int inv_iPr = fpow(add(1, P - Pr), P - 2);
			for (int j = 0; j <= n; ++j)
			{
				q[j] = mul(q[j], inv_iPr);
				inc(q[j + 1], P - mul(q[j], Pr));
			}
		}
		int ans = 0;
		for (int x = 0; x < n; ++x)
			inc(ans, mul(Pr, mul(q[x], inv[x + 1])));
		write(ans, ' ');
		for (int j = 0; j <= n; ++j)
			q[j] = tmp[j];
	}
	puts("");
}
int main()
{
	n = read();
	for (int i = 1; i <= n; ++i)
	{
		p[i][mx[i] = read()] = 1;
		inv[i] = i > 1 ? mul(P - P / i, inv[P % i]) : 1;
	}
	int Q = read();
	while (Q--)
	{
		int op = read();
		if (op == 0)
			modify();
		else
			query();			
	}
	for (int i = 1; i <= n; ++i)
	{
		int s = 0;
		for (int j = 0; j <= mx[i]; ++j)
			inc(s, mul(p[i][j], j));
		write(s, ' ');
	}
	puts("");
	return 0;
}