概率与数学期望

数学

to be upd...

感觉到退役都学不会概率，哎

写的会比较乱，有空再排序吧

在早期OI问题中，充斥着各种离散型概率问题

但是在近期许多模拟赛中开始发现一些奇奇怪怪的连续型问题，特别难受

离散型随机变量的期望

设离散型随机变量 $X$ 的概率分布为 $p_i=P\{X=x_i\}$

若求和 $\sum p_i\times x_i$ 绝对收敛，则称其值为 $X$ 的期望，记为 $E_X$

P6154

考虑到每条路径等概率出现，所以 $E=\frac{\sum len}{num}$ 即总长除以路径条数

记忆化搜索即可，这是个DAG啊

P1297

本题得分是1，所以期望和概率是相等的

利用期望的线性性可以单独求每两个数的情况

此处是一个古典概型，即满足概率等于合法方案数除以总方案

于是 $P_i=\frac{\min(a_i,a_{i+1})}{a_i\times a_{i+1}}$

计算即可

好怪，为什么浮点数除整数的误差比浮点数除浮点数大，猜测是算法不一样导致的

SP1026

此处用了个经典的trick，简单介绍一下：

题意转化一下，转成概率最喜欢的卡牌

假如有 $n$ 种卡牌，你现在有 $x$ 种，下一次随机取一种，获得新牌的概率是 $\frac{n-x}{n}$，不获得的概率是 $\frac{x}{n}$

所以这一步得到卡牌数量的期望 是 $\frac{n-x}{n}$

反过来，获得这张牌的期望操作次数 就是 $\frac{n}{n-x}$

于是计算即可

这玩意貌似是什么几何概型？

于是本题递推即可

CF1042E

我们不妨把这 $nm$ 个点全部存下来并且按照权值排序，从小到大

于是我们可以设 $dp_i$ 表示用 $i$ 当起点的期望得分，那么有

其中 $m$ 是小于 $val_i$ 的位置的个数

复杂度 $O(n^2m^2)$，不可过

$dp$ 数组上个前缀和显然是可以的

盯一下 $dis$

$dis(i,j)=x_i^2+x_j^2-2x_ix_j+y_i^2+y_j^2-2y_iy_j$

再配一下

$\sum dis(i,j)=m\times x_i^2+m\times y_i^2+\sum x_j^2+\ sum y_j^2-2x_i\sum x_j-2y_i\sum y_j$

于是对 $dp、x^2、y^2、x、y$ 都记一下前缀和即可

实现有点细节，这个放一下码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int n,m;
int r,c;
struct node{
    int x,y;
    int val;
};
bool cmp(node x,node y){
    return x.val<y.val;
}
node a[1000005];
int cnt;
int s;
int dp[1000005];
int inv[1000005];
int sx1[1000005],sx2[1000005],sy1[1000005],sy2[1000005];
int sdp[1000005];
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cnt++;
            cin>>a[cnt].val;
            a[cnt].x=i,a[cnt].y=j;
        }
    }
    inv[0]=inv[1]=1;
    for(int i=2;i<=cnt;i++) inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    sort(a+1,a+cnt+1,cmp);
    for(int i=1;i<=cnt;i++){
        sx1[i]=(sx1[i-1]+a[i].x)%mod; 
        sx2[i]=(sx2[i-1]+a[i].x*a[i].x%mod)%mod;
        sy1[i]=(sy1[i-1]+a[i].y)%mod;
        sy2[i]=(sy2[i-1]+a[i].y*a[i].y%mod)%mod;
    }
    int l=0;
    for(int i=1;i<=cnt;i++){
        if(a[i].val!=a[i-1].val) l=i-1;
        dp[i]=sdp[l];
        dp[i]=(dp[i]+l*a[i].x*a[i].x%mod)%mod;
        dp[i]=(dp[i]+l*a[i].y*a[i].y%mod)%mod;
        dp[i]=(dp[i]+sx2[l])%mod;
        dp[i]=(dp[i]+sy2[l])%mod;
        dp[i]=(dp[i]-2*a[i].x*sx1[l]%mod+mod)%mod;
        dp[i]=(dp[i]-2*a[i].y*sy1[l]%mod+mod)%mod;
        dp[i]=(dp[i]*inv[l])%mod;
        sdp[i]=(sdp[i-1]+dp[i])%mod;
    }
    cin>>r>>c;
    for(int i=1;i<=cnt;i++){
        if(a[i].x==r and a[i].y==c) s=i;
    }
    cout<<dp[s];
}

P4316

我们设 $f_{i}$ 表示路径 $i\to n$ 的期望总路径长度，记得期望dp很多时候逆推都比顺着容易且正常

记忆化搜素容易写，转移是典的

P2634

emmmm有很多淀粉质的做法，我的评价是没啥必要吧

考虑dp，设 $f_{u, 0/1/2}$ 表示在 $u$ 的子树内到 $u$ 长度为 $0/1/2 \pmod 3$ 的方案数，转移也是显然的，输出更是简单的

用淀粉质有点牛刀了，而且我并不会淀粉质，朴素的dp复杂度更好而且也不难写，何苦呢xd

连续型随机变量的期望

定义为：$\int_{-\infty}^{\infty} xf(x)\mathrm dx$ 其中 $f(x)$ 为 $x$ 取值的密度分布函数，一定满足 $\int_{-\infty}^{\infty} f(x)\mathrm dx=1$（样本空间的总概率为 $1$）

P5104

直观由等概率可以看出第一次获得的钱的分布函数 $f(x)$ 在区间 $[0,w]$ 上都是 $\frac{1}{w}$，其余部分是 $0$ ,则期望为 $\int_{-\infty}^{\infty} \frac{x}{w} \mathrm dx=\frac{w}{2}$，后续每一步就是把 $w$ 替换为上一轮的期望，所以有结论 $E_k=\frac{w}{2^k}$