【概率+思维】LOJ2552 [CTSC2018] 假面

【题目】
原题地址
有n个人，每个敌人分别有mi​的生命值，接下来释放Q个技能。

• 指定一个敌人id，有p的概率使得这个敌人的生命−1
• 指定k个敌人，等概率的从这k个人中选取一个活着的人封印，问这k个人中每个人被封印的概率分别是多少。
  处理完所有操作后求每个人最终血量期望，血量不会低于0。
  n≤200,mi​≤100,Q≤2×105，二技能次数≤1000，答案对998244353取模。

【解题思路】
又是一道很妙的概率题。

首先我们不看二技能，实际上就是一个简单的DP，我们设fi,j​表示第i个人当前血量为j的概率，那么对于每次一技能fi,j′​=fi,j​×(1−p)+fi,j+1​×p，特别地，对于j=0,fi,0′​=fi,0​+fi,1​×p（即血量为0时不会继续扣血），这一部分的复杂度是O(mQ)的。

我们现在来考虑二技能，设alivex​和deadx​，分别表示x在当前情况下存活或死亡的概率，那么deadx​=fx,0​,alivex​=1−deadx​。令gj​表示当前选定集合中不包括当前封印的人情况下，有j个人仍然存活，每次新加入一个人x(不包括当前封印的人i)，则gj′​=alivex​×gj−1​+deadx​×gj​。

那么当前被封印的人为i的概率即为alivei​×∑j=0k−1​j+1gj​​。

这样做我们需要枚举被封印的人，再进行O(k2)的DP，每个询问是O(k3)的，需要考虑优化。

一个十分妙的情况在于上面的式子是可逆的，即gj​=deadx​gj′​−alivex​×gj−1​​，于是我们可以对所有人一起求出共有的g数组，最后回代一步，这样每个询问就是O(k2)的了。

总的时间复杂度就是O(mQ+n2C)的了。

表示sb了，有一个快速幂的log没有写到外面去一直70pt。

【参考代码】

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=405,mod=998244353;
int n,m,Q,a[N],d[N];
ll rem[N],g[N],inv[N],f[N][N];

int read()
{
	int ret=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) ret=ret*10+(c^48),c=getchar();
	return ret;
}
void write(ll x){if(x>9)write(x/10);putchar((x%10)^48);}
ll qpow(ll x,int y){ll res=1;for(;y;y>>=1,x=x*x%mod)if(y&1)res=res*x%mod;return res;}
ll upm(ll x){x%=mod;if(x<0)x+=mod;return x;}
void up(ll &x,ll y){x+

					

						
继续阅读与本文标签相同的文章
						

														无标签