[笔记]概率与期望
本文最后更新于 193 天前,其中的信息可能已经有所发展或是发生改变。

主要记录了做的几道题。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。

原文链接:https://www.codein.icu/expectations/

前言

今天学习一下期望 DP,写点笔记。
由于概率与期望是高中数学内容,已经学过了,不再过多描述。

模型

写转移方程时算上概率罢了,常常用逆推。

例题

学习知识点的最好方法就是刷题。

SPOJ Favorite Dice

给一个 $n$ 面的骰子,问每面都被抛到的期望次数。

设 $f(i)$ 为剩余 $i$ 面要被抛到的期望次数。
$f(n) = f(n-1) + 1$,第一次抛怎么抛都可以。
$f(n-1) = \dfrac{n-1}{n} \times f(n-2) + \dfrac{1}{n} \times f(n-1) + 1$
$f(n-2) = \dfrac{n-2}{n} \times f(n-3) + \dfrac{2}{n} \times f(n-2) + 1$
依此类推,有:
$f(n – i) = \dfrac{n – i}{n} \times f(n – i – 1) + \dfrac{i}{n} \times f(n – i) + 1$,化简得到:
$\dfrac{n – i}{n} f(n-i) = \dfrac{n-i}{n} \times f(n-i-1) + 1$,继续化简得到:
$f(n – i) = f(n – i – 1) + \dfrac{n}{n-i}$,用 $x$ 替换 $n – i$ 得到:
$f(x) = f(x – 1) + \dfrac{n}{x}$

显然有 $f(1) = n$,递推即可。

这类题型相当常见,例如一样的题还有 [SHOI2002]百事世界杯之旅。

#include <cstdio>
int T,n;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d", &n);
        double last = n, now = 0;
        for (int i = 2; i <= n; ++i)
        {
            now = last + n * 1.0 / i;
            last = now;
        }
        printf("%.2f\n", last);
    }
    return 0;
}

[USACO08OCT]Bovine Bones G

给三个骰子,范围分别为 $[1,a]$,$[1,b]$,$[1,c]$,求三个骰子上的数字和,哪个和出现最频繁。

虽然计算期望并不严谨,但依然可以试试。

数字在 $[1,a]$ 中平均分布,期望为 $\dfrac{a – 1}{2} + 1$,其余同理。

可以得到整体期望为 $\dfrac{a + b + c + 3}{2}$

然而问题在于,原题中的数字并非实数线性分布,而是限制在整数域内。而要计算的是出现最频繁的和,而非期望和。因此这个解法显然是有问题的。

明显的问题在于可能计算出非整数期望。

正确的方法应该是算事件数,即求 $x_1 + x_2 + x_3 = k$ 的方案数,如果不考虑限定范围的话,显然就是经典高中数学排列组合题,$k – 1$ 个间隔中插入两个隔板即可。

限定范围后,可能可以计算出不合法数目,然后容斥一下。

当然,原题数据范围奇小,直接枚举暴力即可。

LuoguP1654 OSU!

给出每个位置为 $1$ 的概率,一整段长度为 $x$ 的 $1$ 对答案的贡献为 $x^3$,求期望得分。

定义 $p(i)$ 为位置 $i$ 为 $1$ 的概率。

考虑多一个 $1$ 对答案的贡献:$(x + 1)^3 – x^3 = 3x^2 + 3x + 1$,那么维护 $x^2$ 与 $x$ 的期望值即可进行转移。

定义 $f(i)$ 为结尾连续一段的 $x$ 的期望, $g(i)$ 为结尾连续一段的 $x^2$ 的期望,$h(i)$ 为得分的期望,有:
$f(i) = [f(i-1) + 1] \times p(i)$
$g(i) = [g(i-1) + 2f(i-1) + 1] \times p(i)$
$h(i) = h(i-1) + p(i) \times [3g(i-1) + 3f(i-1) + 1]$

#include <cstdio>
const int maxn = 1e5 + 100;
int n;
double p[maxn], f[maxn], g[maxn], h[maxn];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%lf", p + i);
    for (int i = 1; i <= n; ++i)
    {
        f[i] = (f[i - 1] + 1) * p[i];
        g[i] = (g[i - 1] + 2 * f[i - 1] + 1) * p[i];
        h[i] = h[i - 1] + (3 * g[i - 1] + 3 * f[i - 1] + 1) * p[i];
    }
    printf("%.1f",h[n]);
    return 0;
}

LuoguP4550 收集邮票

买第 $k$ 张邮票需要 $k$ 元,要收集全部邮票,求期望花费。
设 $f(i)$ 为现在取了 $i$ 张邮票,要取完剩下的邮票的期望次数。
初始有 $f(n) = 0$,考虑转移:
每次购买,有 $\dfrac{i}{n}$ 的概率取到有的,$\dfrac{n-i}{n}$ 的概率取到现在没有的,因此写出:
$f(i) = \dfrac{i}{n} \times f(i) + \dfrac{n-i}{n} \times f(i+1) + 1$,化简有:
$f(i) = f(i + 1) + \dfrac{n}{n-i}$,与上面的某题是一样的。

设 $g(i)$ 为现在取了 $i$ 张邮票,要取完剩下的邮票的期望花费。
初始有 $g(n) = 0$,考虑转移:
有 dfrac{i}{n} 的概率取到有的,在此之后,期望还要取的次数是 $f(i)$,考虑顺着买邮票与倒着买是相同的,相当于在此之前,买了 $f(i)$ 张,此时花费为 $f(i) + 1$,因此:此时 $g(i) = \dfrac{i}{n} \times [g(i) + f(i) + 1]$
有 $\dfrac{n-i}{n}$ 的概率取到没有的,在此之后,期望还要取的次数为 $f(i+1)$,同理转化为买了 $f(i+1)$ 张,花费为 $f(i+1) + 1$,此时有:$g(i) = \dfrac{n-i}{n} \times [g(i+1) + f(i+1) + 1]$,合并起来有:
$g(i) = \dfrac{i}{n} \times [g(i) + f(i) + 1] + \dfrac{n-i}{n} \times [g(i+1) + f(i+1) + 1]$,化简得:

$g(i) = \dfrac{i}{n-i} \times f(i)+g(i+1)+f(i+1)+\dfrac{n}{n-i}$

转移即可。

#include <cstdio>
const int maxn = 1e5 + 100;
int n;
double f[maxn],g[maxn];
int main()
{
    scanf("%d",&n);
    for(int i = n - 1;i>=0;--i)
    {
        f[i] = f[i + 1] + 1.0 * n / (1.0 * n - i);
        g[i] = (1.0 * i) / (n - i) * f[i] + g[i + 1] + f[i + 1] + (1.0 * n) / (n - i);
    }
    printf("%.2f",g[0]);
    return 0;
}

LuoguP3802 小魔女帕琪

七种物品,每种有 $a_i$ 个,每次等概率取出一个。连续 $7$ 种不同的物品会触发一次终极魔法,而不同终极魔法对应的物品可以有重合。

求终极魔法触发的期望次数。

先考虑前七次就触发魔法的概率:

$\prod_{i=1}^7 \dfrac{a_i}{n – i + 1}$

而该 $a_i$ 的顺序如何排列是不会影响触发魔法的,因此 $7!$ 种排列都是可行的。

概率为:$7! \times \prod_{i=1}^7 \dfrac{a_i}{n – i + 1}$

考虑将前七次拓展到所有次数,可以发现,这七次连续抽取的段无论在哪里,概率都是上式。

这类似于抽签游戏,在条件概率下是公平的。严格证明如下:

假定第一次取走一个 $a_1$,剩余 $n – 1$ 个球,第 $2$ 至 $8$ 个抽取满足条件的概率为:

$\dfrac{a_1}{n} \times 7! \times \dfrac{a_2}{n – 1}\times \dfrac{a_3}{n – 2} \times \dfrac{a_4}{n – 3} \times \dfrac{a_5}{n – 4} \times \dfrac{a_6}{n – 5} \times \dfrac{a_7}{n – 6} \times \dfrac{a_1 – 1}{n – 7}$

其余同理,将第一次取走 $a_x$ 的概率累加得到:

$7! \times \prod _{i=1}^7 \dfrac{a_i}{n-i+1} \times \sum _{i=1}^7 \dfrac{a_i – 1}{n – 7}$

显然最后这部分的和为 $1$,因此取走第一个物品后,开头的前七次触发魔法的概率与未取时相等。

依此推广到取 $m$ 个物品时,概率都不变。直到只剩下 $7$ 个物品为止。

最后答案就是:

$7! \times \prod _{i=1}^7 \dfrac{a_i}{n-i+1} \times (n – 6)$

需要特判零的情况,避免除数为零。

#include <cstdio>
using namespace std;
long long a[10];
int main()
{
    long long n = 0;
    for (int i = 1; i <= 7; ++i) scanf("%lld", a + i), n += a[i];
    double ans = 7 * 6 * 5 * 4 * 3 * 2 * 1 * (n - 6);
    if(n <= 6) 
    {
        puts("0.000");
        return 0;
    }
    for (int i = 1; i <= 7; ++i) ans = ans / (n - i + 1) * a[i];
    printf("%.3f", ans);
    return 0;
}

LuoguP6154 游走

给一个有向无环图,随机选择一条路径,求路径期望长度。

假定有 $num$ 条路径,所有路径长度总和为 $len$,那么答案就是 $\dfrac{len}{num}$。

考虑如何求出 $num$ 与 $len$,定义 $f(i)$ 为以 $i$ 为结尾的路径条数,定义 $g(i)$ 为以 $i$ 结尾的路径长度和。

显然有 $f(v) += f(u)$,$g(v) += g(u) + f(u)$

拓扑排序转移即可。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
using namespace std;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
#define int long long
const int mod = 998244353;
const int maxn = 1e5 + 100;
vector<int> E[maxn];
int n, m;
int f[maxn], g[maxn], in[maxn];
int q[maxn], qh, qt;
int fastpow(int x,int k)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (1ll * res * x) % mod;
        x = (1ll * x * x) % mod;
        k >>= 1;
    }
    return res;
}
int inv(int x) { return fastpow(x, mod - 2); }
signed main()
{
    read(n), read(m);
    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        read(x), read(y), E[x].push_back(y), in[y]++;
    }
    qh = 1, qt = 0;
    for (int i = 1; i <= n; f[i] = 1, ++i) if (in[i] == 0) q[++qt] = i;
    while(qt >= qh)
    {
        int u = q[qh++];
        for (vector<int>::iterator it = E[u].begin(); it != E[u].end(); ++it)
        {
            int v = *it;
            (f[v] += f[u]) %= mod;
            (g[v] += g[u] + f[u]) %= mod;
            if (--in[v] == 0) q[++qt] = v;
        }
    }
    int sf = 0,sg = 0;
    for (int i = 1; i <= n; ++i) sf = (sf + f[i]) % mod, sg = (sg + g[i]) % mod;
    printf("%lld\n", (1ll * sg * inv(sf)) % mod);
    return 0;
}
本文标题:[笔记]概率与期望
本文作者:Clouder
本文链接: https://www.codein.icu/expectations/
转载请标明。

评论

  1. 6月前
    2020-8-26 10:33:18

    您都会期望了orz

  2. mofianger
    Windows Chrome 85.0.4183.121
    3月前
    2020-12-02 12:49:41

    orz

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇