数学期望
pengze36
·
·
个人记录
期望即每个可能发生的值乘以它的概率，求和
即值 x_1,x_2..x_n 对应概率 p_1,p_2...p_n
期望=\frac{x_1}{p_1}+\frac{x_2}{p_2}+..+\frac{x_n}{p_n}
例子：
13张牌，摸一次不是a陪1￥，摸到a得10￥，求期望
期望E(x)=\frac{1}{13}*10-\frac{12}{13}*1=-\frac{2}{13}
P4316 绿豆蛙的归宿
设f_i为1~i的期望，d表所有路径，p表对应概率，即d_1(p_1),d_2(p_2)..d_n(p_n),一节点期望$E(x)= d_1p_1+d_2p_2+..+d_n*p_n
得
$$
E(x)=\sum_{i=1}^{n}d_1*p_1=\sum_{i \in son(x)}^{}(d_{son(i)}*p_{son(i)}+edge*p_{son(i)})*\frac{1}{out(i)}
$$
则
$$
E(x)=\sum_{i \in son(x)}^{}(E(i)+edge*p_{son(i)}*\frac{1}{out(i)})
$$
$$
P_x=\sum_{i \in son(x)}^{}P_i*\frac{1}{out(i)}
$$
```
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
int n,m;
struct e{
int v;
ll w;
};
vector<e> g[100005];
queue<int> q;
int out[100005];
double f[100005];
ll ru[100005];
double p[100005];
void topu(){
q.push(1);
p[1]=1;
while(!q.empty()){
int u=q.front();
q.pop();
int k=g[u].size();
for(int i=0;i<k;++i){
int v=g[u][i].v;
ru[v]--;
f[v]+=(f[u]+g[u][i].w*p[u])/out[u];
p[v]+=p[u]/out[u];
if(!ru[v]) q.push(v);
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int u,v;
ll w;
scanf("%d%d%lld",&u,&v,&w);
g[u].push_back({v,w});
out[u]++;
ru[v]++;
}
topu();
printf("%.2lf\n",f[n]);
return 0;
}
```
# [P8774 [蓝桥杯 2022 省 A] 爬树的甲壳虫](https://vjudge.net/contest/640254#problem/B)
设$f_i$为i爬到n的期望，答案为$f_0
则f_i=1+P_{i+1}*f_0+(1-P_{i+1})*f_{i+1}
f_i必须有式子上的1，因为进行1步，且必定进行（概率为1），就是加了E=1/1
求 f_i要知道f_0，f_{i+1}，带入求解
，找规律
\begin{cases}
f_0=1+P_1*f_0+(1-P_1)*f_1 ①\\
f_1=1+P_2*f_0+(1-P_2)*f_2 ②\\
f_2=1+P_3*f_0+(1-P_3)*f_3 ③\\
....\\
\end{cases}
①式中只有f_0,f_1为变量，f_0为答案
f_0=1+P_1f_0+(1-P_1)(1+P_2f_0+(1-P_2)f_2)④$
化简
得
f_0=1+P_1*f_0+(1-P_1)+(1-P_1)*P_2*f_0+(1-P_1)(1-P_2)*f_2 ⑤
$f_0=1+P_1*f_0+(1-P_1)+(1-P_1)*P_2*f_0+(1-P_1)(1-P_2)*(1+P_3*f_0+(1-P_3)*f_3)
化简
得
f_0=1+P_1*f_0+(1-P_1)+(1-P_1)*P_2*f_0+(1-P_1)(1-P_2)+(1-P_1)(1-P_2)*P_3*f_0+(1-P_1)(1-P_2)(1-P_3)*f_3
将含P的项合并，含f的项合并
得
f_0=1+(1-P_1)+(1-P_1)(1-P_2)+f_0(P_1+(1-P_1)*P_2+(1-P_1)(1-P_2)*P_3)+(1-P_1)(1-P_2)(1-P_3)*f_3
再代入f_3...,一直代完f_n
得
f_0=1+(1-P_1)+(1-P_1)(1-P_2)+....+(1-P_1)(1-P_2)*....*(1-P_{n-1})+f_0(P_1+(1-P_1)*P_2+(1-P_1)(1-P_2)*P_3+...+(1-P_1)(1-P_2)*....*(1-P_{n-1})*P_n)+(1-P_1)(1-P_2)*....*(1-P_n)*f_n
因为f_0已到n，步数为0,so f_0=0
得
f_0=1+(1-P_1)+(1-P_1)(1-P_2)+....+(1-P_1)(1-P_2)*....*(1-P_{n-1})+f_0(P_1+(1-P_1)*P_2+(1-P_1)(1-P_2)*P_3+...+(1-P_1)(1-P_2)*....*(1-P_{n-1})*P_n)+(1-P_1)(1-P_2)*....*(1-P_n)*0
则
f_0=1+(1-P_1)+(1-P_1)(1-P_2)+....+(1-P_1)(1-P_2)*....*(1-P_{n-1})+f_0(P_1+(1-P_1)*P_2+(1-P_1)(1-P_2)*P_3+...+(1-P_1)(1-P_2)*....*(1-P_{n-1})*P_n)
$(1-(P_1+(1-P_1)*P_2+(1-P_1)(1-P_2)*P_3+...+(1-P_1)(1-P_2)*....*(1-P_{n-1})*P_n))f_0=1+(1-P_1)+(1-P_1)(1-P_2)+....+(1-P_1)(1-P_2)*....*(1-P_{n-1})
f_0=\frac{1+(1-P_1)+(1-P_1)(1-P_2)+....+(1-P_1)(1-P_2)*....*(1-P_{n-1})}{1-(P_1+(1-P_1)*P_2+(1-P_1)(1-P_2)*P_3+...+(1-P_1)(1-P_2)*....*(1-P_{n-1})*P_n)}
因为P_i=\frac{x_i}{y_i}是分数，又要取模，则要求出y_i 的逆元，用快速幂解决
关于逆元：
费马小定理：
a_{p-1}mod p=1,则a_{p-2} mod p=\frac{1}{a}
\frac{x_i}{y_i}=x_i*(y_i)^{p-2}
关于取模：
设1+(1-P_1)+(1-P_1)(1-P_2)+....+(1-P_1)(1-P_2)*....*(1-P_{n-1})=x,\\
(P_1+(1-P_1)*P_2+(1-P_1)(1-P_2)*P_3+...+(1-P_1)(1-P_2)*....*(1-P_{n-1})*P_n)=y,则\\
f_0=\frac{x}{1-y},\\
1-y取模p时要（1-y+p)\bmod p,
(1-P_i)先算P_i再减会导致取模错误，1-P_i=1-\frac{x_i}{y_i}=\frac{y_i-x_i}{y_i},算(y_i-x_i)*(y_i)^{p-2}即可
一定边算边取模！！
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll mod=998244353 ;
int n;
ll x[100005],y[100005];
ll c[100005];
ll s[100005];
ll inv(ll a){
ll res=1;
ll b=mod-2;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%lld%lld",&x[i],&y[i]);
c[i]=(y[i]-x[i]+mod)%mod*inv(y[i])%mod;
}
s[0]=1;
for(int i=1;i<=n;++i){
s[i]=(s[i-1]*c[i])%mod;
}
ll fx=1;
for(int i=1;i<n;++i){
fx=(fx+s[i])%mod;
}
ll fy=x[1]*inv(y[1])%mod;
for(int i=2;i<=n;++i){
fy=(fy+s[i-1]*x[i]%mod*inv(y[i])%mod)%mod;
}
fy=(1-fy+mod)%mod;
printf("%lld\n",fx*inv(fy)%mod);
return 0;
}
ボール
见题解
补充：一个串s,在i位置打了一下，就是在i上&0，其他位置&1，相当于s&(~(1<<(i-1)))
设串a,b,c为s串中朝x点投球后三种情况，
\begin{aligned}
f_s &=1+\frac{f_a}{3}+\frac{f_b}{3}+\frac{f_c}{3}
\\\end{aligned}
其中可能有一些串与s相同，设此串为a
\begin{aligned}
f_s &=1+\frac{f_s}{3}+\frac{f_b}{3}+\frac{f_c}{3}\\
\frac{2}{3}*f_s=1+\frac{f_b}{3}+\frac{f_c}{3}
\\\end{aligned}\\ f_s=\frac{2}{3}+\frac{f_b}{2}+\frac{f_c}{2}
设cnt个串与s相同
f_s=\frac{3}{3-cnt}*(1+(f..)/3),f..为与s不同的串的f的和
如果往0或15投的话可能投到-1或16，1/3的概率就浪费了，所以只需在[1,14]投就行了，手摸一下样例就行了
给double赋值max要
memset(f,127,sizeof f);
或者for遍历赋值0x3f3f3f3f就行