[CTSC2018]假面

题目

先来考虑一下第一问，血量有\(P\)的概率减\(1\)

由于我们最后需要求每一个人的期望血量，于是考虑维护出每个人处于不同血量时候的概率

一个简单\(dp\)即可

\[dp_{i,j}=dp_{i,j+1}P+dp_{i,j}\times (1-P)
\]

\(dp_{i,j}\)表示第\(i\)个人血量为\(j\)的概率

第二问，发现概率的选中的人中的存活人数有关

于是每一个人只有两种状态，生或者是死，我们考虑求出每种存活人数对应的概率是多少

显然这里我们有一个这样的\(dp\)

\[f_{i,j}=f_{i-1,j-1}\times p_i+f_{i-1,j}\times (1-p_i)
\]

\(f_{i,j}\)表示前\(i\)个人里存活\(j\)个人的概率

发现做一次这个\(dp\)是\(O(n^2)\)的，对每一个人做一遍复杂度就是\(O(n^3)\)了

考虑消除某一个人的影响

设\(f_{j}=f_{n,j},g_{j}=g_{n-1,j}\)，我们要消除第\(n\)的人的影响

显然边界条件有

\[f_0=g_0\times (1-p_n)
\]

于是

\[g_0=\frac{f_0}{1-p_n}
\]

求得了\(g_0\)，我们就可以递推了

\[f_j=g_{j-1}\times p_n+g_{j}\times (1-p_n)
\]

于是就有

\[g_j=\frac{f_j-g_{j-1}\times p_n}{1-p_n}
\]

但是需要特别注意\(p_n=1\)的时候我们需要特殊处理一波，也非常简单就是

\[g_{j-1}=f_j
\]

代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#define re register

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

const int maxn=205;

const LL mod=998244353;

inline int read() {

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

int n,h[maxn],m,opt,a[maxn];

LL dp[maxn][105],t[maxn],f[maxn],inv[maxn],g[maxn];

inline LL ksm(LL a,LL b) {

	LL S=1;

	while(b) {if(b&1) S=S*a%mod;b>>=1;a=a*a%mod;}

	return S;

}

int main() {

	n=read();

	for(re int i=1;i<=n;i++) h[i]=read(),dp[i][h[i]]=1;

	m=read();

	inv[1]=1;

	for(re int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;

	while(m--) {

		opt=read();

		if(opt==0) {

			int pos=read();

			LL u=read(),v=read();

			LL P=ksm(v,mod-2)*u%mod;

			for(re int i=0;i<=h[pos];i++)

				dp[pos][i]=(dp[pos][i]*(1-P+mod)%mod+dp[pos][i+1]*P%mod)%mod;

		}

		if(opt==1) {

			int k=read();

			for(re int i=1;i<=k;i++) a[i]=read();

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

				t[a[i]]=0;

				for(re int j=1;j<=h[a[i]];j++)

					t[a[i]]=(t[a[i]]+dp[a[i]][j])%mod;

			}

			memset(f,0,sizeof(f));

			f[0]=1;

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

				for(re int j=i;j>=0;--j) {

					f[j]=(f[j]*(1-t[a[i]]+mod)%mod)%mod;

					if(j-1>=0) f[j]=(f[j]+f[j-1]*t[a[i]]%mod)%mod;

				}

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

				memset(g,0,sizeof(g));

				if(t[a[i]]!=1) {

					LL d=ksm((1-t[a[i]]+mod)%mod,mod-2);

					g[0]=f[0]*d%mod;

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

					g[j]=(f[j]-g[j-1]*t[a[i]]%mod+mod)*d%mod;

				}

				else for(re int j=1;j<=k;j++) g[j-1]=f[j];

				LL ans=0;

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

					ans=(ans+g[j]*inv[j+1]%mod)%mod;

				printf("%lld ",ans*t[a[i]]%mod);

			}

			putchar(10);

		}

	}

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

		LL now=0;

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

			now=(now+dp[i][j]*(LL)j%mod)%mod;

		printf("%lld ",now);

	}

	return 0;

}

巴特西

[CTSC2018]假面

最新文章

热门文章