[CTSC2018]假面 题解
概率期望 DP
Statement
\(n\le 200\) 个人，每一个人初始有 \(a_i(\le 100)\) 血量，有两种操作：
- 以 \(p\) 概率使得 \(a_x\) 减 \(1\) ，血量 \(\le 0\) 认为这个人死亡
- 在 \(k\) 个人中的活人中等概率地选择某一个人，求这 \(k\) 个人各自被选择的概率
同时，在所有操作结束之后，需要求解所有人剩余生命值的期望
其中，第二个操作出现次数 \(\le 1000\) ，操作总数 \(\le 2e5\)
Solution
容易想到设 \(p[i][j]\) 表示第 \(i\) 个人还有 \(j\) 血的概率，这个可以 \(O(qa)\) 暴力维护，具体的，对于每一次一操作：
\[p[i][j]= \begin{cases} p[i][j]&+&p[i][j+1]\times p&,j=0\\ p[i][j]\times (1-p)&+&p[i][j+1]\times p&,j>0\\ \end{cases} \]通过这样，我们可以回答所有人剩余血的期望
考虑处理第二种操作，当处理到第 \(i\) 个人被选中的期望时， \(i\) 肯定是要存活的，我们还关系除了 \(i\) 之外有多少个人存活
设 \(f[i][j]\) 表示除了 \(i\) 之外有 \(j\) 个人存活的概率，记 \(live[i]=1-p[i][0]\)
第 \(i\) 个人的答案就是
\[live[i]\times\sum_{j=0}^{k-1}\frac{f[i][j]}{j+1} \]考虑求解 \(f\)，枚举另外一个数 \(x\)
\[f[i][j]^{\prime}=f[i][j-1]\times live[x]+f[i][j]\times(1-live[x]) \]\(f\) 的求解是 \(O(n^3)\) 的，总复杂度 \(O(qa+cn^3)\) ，卡常大师可以过，过个毛线
然后整道题最秀的一步出现了，首先 \(f[i][j]\) 的迭代中，\(x\) 的枚举顺序显然是没有任何影响的，我们脑洞大开，虽然 \(f[i][j]\) 的定义是不包括 \(i\) 下 \(j\) 个人存活，我们强行用 \(i\) 迭代，即把 \(i\) 放在最后一次迭代，观察：
\[f[i][j]^{\prime}=f[i][j-1]\times live[i]+f[i][j]\times(1-live[i])\\ f[i][j]=\frac{f[i][j]^{\prime}-f[i][j-1]\times live[i]}{1-live[i]} \]此时，由于我们破坏了 \(f[i][j]\) 原本的定义，所以设 \(g[i]\) 表示随便 \(i\) 个人存活的概率
\[f[i][j]=\frac{g[j]-f[i][j-1]\times live[i]}{1-live[i]} \]如果我们知道 \(g[j]\) 的话，我们就得到了 \(O(n)\) 得到 \(f[i]\) 的手段，即 \(O(n^2)\) 得到 \(f\) （不用枚举 \(x\) 了）
特殊的，如果 \(live[i]==1\) ，那么 \(f[i][j]=g[j+1]\)
我们考虑 \(g\) 怎么求，枚举每一个人：
\[g[i]=g[i-1]\times live[j]+g[i]\times (1-live[j]) \]发现这个的复杂度是 \(O(n^2)\) ！很好，很有精神。
于是，总复杂度变成了 \(O(qa+cn^2)\) ，很稳
Code
#include
using namespace std;
const int N = 205;
const int M = 105;
const int mod = 998244353;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
int s=0,w=1; char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
return s*w;
}
int p[N][M],live[N];
int f[N],g[N];
int m[N],inv[N];
int n,q;
void inc(int&a,int b){a=a>=mod-b?a-mod+b:a+b;}
void dec(int&a,int b){a=a>=b?a-b:a+mod-b;}
int add(int a,int b){return a>=mod-b?a-mod+b:a+b;}
int red(int a,int b){return a>=b?a-b:a+mod-b;}
int invx(int x){return x