F - 期望
F - 期望
题意
你有 \(n\) 个开关，每个开关进行操作需要 \(t_i\) 的时间，有 \(\frac{a_i}{b_i}\) 的概率可以打开，剩下的概率会导致全部开关关闭，求开启所有开关的期望时间。
思路
很容易想到先搞出期望 DP 转移方程，然后就可以贪心地唯一确定操作开关的顺序，即使不幸失败导致所有开关关闭了也依然按照这个顺序依次尝试所有开关。
设 \(p_i=\frac{a_i}{b_i}\)。
设 \(f_i\) 表示开启了前 \(i\) 个开关期望时间。
几个错误的 DP 转移方程：
- \(f_{i-1}\times p_i+t_i=f_i,f_{i-1}\times (1-p_i)+t_i=f_0\)
- \(f_i=p_if_{i-1} + (1-p_i) f_i + t_i\)
- \(f_i=p_i(f_{i-1}+t_i)+(1-p_i)f_i\)
错因大概都是：不可以使用期望 $\times $ 概率。
正确转移方程：
\[f_i=(f_{i-1}+t_i)\frac{1}{p_i}
\]
含义为，成功的用时是 \(f_{i-1}+t_i\)，那么期望尝试 \(\frac{1}{p_i}\) 次才能成功。
然后如何确定开关的顺序呢？
对于开关 \(i,j\)，考虑两种相对顺序的用时。
\[(i,j)=((f_x+t_i)\frac{1}{p_i}+t_j)\frac{1}{p_j}\\
(j,i)=((f_x+t_j)\frac{1}{p_j}+t_i)\frac{1}{p_i}\]
其实我们不用关心 \(f_x\)，因为我们只需要关心 \(i,j\) 对 \(f_{x+2}\) 的增量就可以了。因此忽略 \(f_x\)，然后按照上面柿子的大小关系排序开关。最后线性算出 DP 即可。
时间复杂度 \(O(n\log n)\)。
code
代码十分好写，注意排序需要使用浮点数比较，因为取模后大小关系会改变。
#include<bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
const int N=2e5+7,mod=998244353;
ll ksm(ll a,ll b=mod-2) {
ll s=1;
while(b) {
if(b&1) s=s*a%mod;
a=a*a%mod;
b>>=1;
}
return s;
}
struct node {
ll t,a,b;
}x[N];
int n;
bool cmp (node x,node y) {
return ((long double)1.0*x.t*x.b/x.a+y.t)*y.b/y.a < ((long double)1.0*y.t*y.b/y.a+x.t)*x.b/x.a;
}
int main() {
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("my.out","w",stdout);
#endif
sf("%d",&n);
rep(i,1,n) sf("%lld%lld%lld",&x[i].t,&x[i].a,&x[i].b);
sort(x+1,x+n+1,cmp);
ll f=0;
rep(i,1,n) {
f=(f+x[i].t)*x[i].b%mod*ksm(x[i].a)%mod;
}
pf("%lld\n",f);
}