BZOJ5340 [Ctsc2018]假面【概率dp】

题目链接

BZOJ5340

题解

我们能很容易维护每个人当前各种血量的概率

设\(p[u][i]\)表示\(u\)号人血量为\(i\)的概率

每次攻击的时候，讨论一下击中不击中即可转移

是\(O(Qm^2)\)的

现在考虑一下结界

如果我们设\(f[u][i]\)表示除了\(u\)还存活\(i\)个人的概率

那么

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

所以我们只需计算\(f[u][i]\)

\(f[u][i]\)同样可以通过枚举剩余每个人存活与否进行转移，是\(O(n^3)\)的，复杂度过高

我们考虑计算\(g[i]\)表示剩余\(i\)人的概率

枚举\(u\)

\[g'[i] = g[i]p[u][0] + g[i - 1](1 - p[u][0])
\]

即可\(O(n^2)\)计算\(g[i]\)

如果我们拿\(f[u][i]\)来计算\(g[i]\)的话

\[g[i] = f[u][i]p[u][0] + f[u][i - 1](1 - p[u][0])
\]

那么

\[f[u][i] = \frac{g[i] - f[u][i - 1](1 - p[u][0])}{p[u][0]}
\]

也可以\(O(n^2)\)递推

这样我们就做完了

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

using namespace std;

const int maxn = 205,maxm = 105,INF = 1000000000,P = 998244353;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

LL p[maxn][maxm],f[maxn][maxn],g[maxn][maxn],n,m[maxn],id[maxn];

LL INV[maxn];

inline LL qpow(LL a,LL b){

	LL ans = 1;

	for (; b; b >>= 1,a = 1ll * a * a % P)

		if (b & 1) ans = 1ll * ans * a % P;

	return ans;

}

inline LL inv(int x){

	if (x <= n) return INV[x];

	return qpow(x,P - 2);

}

int main(){

	n = read();

	REP(i,n) m[i] = read(),p[i][m[i]] = 1;

	INV[0] = 1; INV[1] = 1;

	for (int i = 2; i <= n; i++) INV[i] = 1ll * (P - P / i) * INV[P % i] % P;

	LL Q = read(),opt,u,v,pp,x,k;

	while (Q--){

		opt = read();

		if (!opt){

			x = read(); u = read(); v = read(); pp = u * inv(v) % P;

			p[x][0] = (p[x][0] + pp * p[x][1] % P) % P;

			for (int i = 1; i <= m[x]; i++)

				p[x][i] = ((p[x][i] * (1 - pp) % P + p[x][i + 1] * pp % P) % P + P) % P;

		}

		else {

			k = read();

			cls(g); g[0][0] = 1;

			for (int i = 1; i <= k; i++){

				u = id[i] = read();

				g[i][0] = g[i - 1][0] * p[u][0] % P;

				for (int j = 1; j <= i; j++){

					g[i][j] = ((g[i - 1][j] * p[u][0] % P + g[i - 1][j - 1] * (1 - p[u][0]) % P) % P + P) % P;

				}

			}

			for (int i = 1; i <= k; i++){

				u = id[i];

				LL ans = 0,Inv = inv(p[u][0]);

				if (!p[u][0]){

					for (int j = 0; j < k; j++)

						f[u][j] = g[k][j + 1];

				}

				else {

					f[u][0] = 1ll * g[k][0] * Inv % P;

					for (int j = 1; j < k; j++){

						f[u][j] = (1ll * (g[k][j] - 1ll * f[u][j - 1] * (1 - p[u][0]) % P) % P * Inv % P + P) % P;

					}

				}

				for (int j = 0; j < k; j++){

					ans = (ans + 1ll * f[u][j] * inv(j + 1) % P) % P;

				}

				ans = (1ll * ans * (1ll - p[u][0]) % P + P) % P;

				printf("%lld",ans);

				if (i < k) putchar(' ');

				else puts("");

			}

		}

	}

	for (int i = 1; i <= n; i++){

		LL ans = 0;

		for (int j = 1; j <= m[i]; j++)

			ans = (ans + 1ll * j * p[i][j] % P) % P;

		printf("%lld",ans);

		if (i < n) putchar(' ');

		else puts("");

	}

	return 0;

}

巴特西

BZOJ5340 [Ctsc2018]假面【概率dp】

题目链接

题解

最新文章

热门文章

巴特西

BZOJ5340 [Ctsc2018]假面 【概率dp】

题目链接

题解

最新文章

热门文章

BZOJ5340 [Ctsc2018]假面【概率dp】