再谈概率期望（三）：我说爬塔学随机是对的。

· · 算法·理论

以防你忘了前两篇文章写了什么：

例题

是的，这次先从一道经典的题目开始。

::anti-ai[本文作者是 clx201022，洛谷 UID 为 552688，原文：https://www.luogu.com.cn/article/3dx8jgbc 如果您能直接看到这段文字而在本页没有转载提示，或以“原创”名义发出，说明您访问的是侵权内容，请联系管理员删除文章并处罚侵权人，十分感谢您的见义勇为之举。]

P5299 [PKUWC2018] Slay the Spire

题意简述

九条可怜有强化牌和攻击牌各 n 张。攻击牌可以打伤害，强化牌则可以强化攻击牌，让其造成的伤害乘上一个倍率。

现在九条可怜会等概率随机从卡组中抽出 m 张牌，由于费用限制，九条可怜最多打出 k 张牌，假设九条可怜永远都会采取能造成最多伤害的策略，求她期望造成多少伤害。

做法分析

注意到题目中最后的答案乘上的神秘数字正好为从 2n 张牌中选 m 张打出的方案数，因此事实上只需要将所有可能的方案数的最优收益加起来即可。

性质推导

考虑如何达成最优解。首先对于相同种类的卡牌，肯定是优先打出数值最高的；又注意到强化牌的数值 w_i\ge 2，因此在确定打出一张最大的攻击牌后，在打出攻击牌前多打一张强化牌必然是不劣的。

综上，最优方案即为：先打出最大的攻击牌，再从大到小打出所有强化牌，最后若还有剩余费用，再打出其他攻击牌。注意这里因为出牌的顺序在一个方案的收益内是可以随意调整的，所以为了方便处理，此处将强化牌的收益扩大到了打出强化牌前打出的攻击牌上。

为了方便起见，下文默认同类牌按从大到小的顺序排列。

设选择攻击牌为 {atk}，强化牌为 w，则最终伤害为：

(\sum {atk})(\prod w)

状态设计

发现似乎没什么性质可拆了。没性质可拆就是大哥，看到大哥就要想到 DP，考虑状态设计。注意到如果一张牌被抽中了但没有被打出，那么抽上来的牌是哪一张都没有关系。所以状态设计限定的应当是选了哪张牌，再从选了哪张牌当中出发去进行状态转移。可以类比于条件概率一类，即只算打出这张牌是最优解的情况。

设 f_{i,j} 表示所有强化牌中，前 i 张牌中打出 j 张牌且第 i 张牌必须被打出时所有强化牌的乘积（即总倍率）之和；g_{i,j} 则为所有攻击牌中，前 i 张牌中打出 j 张牌且第 i 张牌必须被打出时所有攻击牌的和（即总基础伤害）之和。（注意，这里只规定了打出哪些牌，并没有限制抽到的牌有哪些）

转移方程

f_{i,j}\gets w_i\sum_{x=1}^{i-1}f_{x,j-1}

即从前面所有可能的方案中再多选一张强化牌 i。

g_{i,j}\gets atk_i\times\binom{i-1}{j-1}+\sum_{x=1}^{i-1}g_{x,j-1}

即从前面所有可能的方案中再多选一张攻击牌 i。

组合数学

发现强化牌数量小于 k-1 张和不小于 k-1 张时决策情况是不同的，因此考虑分类讨论，然后根据加法原理^jia计算出答案。

强化牌数量小于 k-1 张时

此时必然选上所有的强化牌和数值最高的一些攻击牌。

因为所有强化牌都必然被打出，所以枚举强化牌的数量 i 张。

但注意到仅仅确定强化牌的数量远远不够，还要枚举攻击牌相关的一些值。攻击牌的数量已经确定，因此考虑枚举最后选中的攻击牌 j。

但是因为求的是总方案数，所以还要乘上剩下不出的牌的抽上来的方案数。这些不出的牌里面必然没有强化牌，因为强化牌有就会马上出；于是其中只可能有攻击牌。但这些攻击牌不可能比 j 更优。剩下就没有限制了。

\sum_{i=0}^{k-2}\sum_{j=1}^{n} (\sum_{x=1}^{n}f_{x,i})\cdot g_{j,k-i}\cdot \binom{n-j}{m-k}

注意这里可能会出现一张强化牌都没有的情况，跟其他方案一并处理即可。

强化牌数量大于等于 k-1 张时

选一张最大的攻击牌，剩下必定是全选强化牌。

枚举最后被选中的强化牌 i 和选择的唯一攻击牌 j。

\sum_{i=k-1}^{n}\sum_{j=1}^{n} f_{i,k-1}\cdot {atk}_{j}\cdot \binom{2n-i-j}{m-k}

注意 k-1 的情况不能和小于 k-1 的情况一起处理，因为强化牌正好为 k-1 张时抽到但不用的牌是有可能为强化牌的。

实现

:::success[\green{Accepted}]

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll modp = 998244353;
class C_calculator
{
    using vt = ll;
    vector<vt> fac, infac;
    static vt exgcd(vt a, vt b, vt &x, vt &y)
    {
        if (b == 0)
        {
            x = 1;
            y = 0;
            return a;
            /*a=gcd(a,0) => a=gcd(a,b) => a+0b=gcd(a,b) => ax+by=gcd(a,b)*/
        }
        vt d = exgcd(b, a % b, y, x); // 这里交换了x和y
        y -= std::floor(a / b) * x;
        return d;
    }
    static vt ExGcd_Inv(vt a, vt b)
    {
        vt x, y;
        exgcd(a, b, x, y);
        return (x % b + b) % b;
    }
public:
    void get_fac(size_t x)
    {
        fac.clear();
        infac.clear();
        if (x == 0)
            return;
        fac = vector<vt>(x, 1);
        infac = vector<vt>(x, 1);
        for (size_t i = 1; i <= x - 1; i++)
        {
            fac[i] = fac[i - 1] * i % modp;
        }
        infac[x - 1] = ExGcd_Inv(fac[x - 1], modp);
        for (size_t i = x - 2; i < x; i--)
        {
            infac[i] = infac[i + 1] * (i + 1) % modp;
        }
    }
    C_calculator(size_t x = 0)
    {
        get_fac(x);
    }
    vt C(vt n, vt m)
    {
        if (n < m || m < 0)
            return 0;
        if(fac.size() <= n)
            get_fac(n + 1);
        return fac[n] * infac[m] % modp * infac[n - m] % modp;
    }
    vt getinv(vt n)
    {
        if(infac.size() <= n)
            get_fac(n + 1);
        return fac[n - 1] * infac[n] % modp;
    }
} cc(0);
const int maxn = 6000 + 10, maxm = 6000 + 10;
ll atk[maxn + 1], w[maxn + 1], f[maxn + 1][maxn + 1], f_sum[maxn + 1][maxn + 1], g[maxn + 1][maxn + 1], g_sum[maxn + 1][maxn + 1], ans;
ll n, m, k;
void solve()
{
    ans = 0;
    cin >> n >> m >> k;
    // 牌序肯定是先强化再攻击 
    // f[i][j] 前 i 张强化牌随机抽 j 张最大强化值期望，因为乘了个数所以等同于和 
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i]; // 数值特别高
    }
    for(int i = 1; i <= n; i++)
    {
        cin >> atk[i]; // 有无煎饼大鸡？？？
    }
    sort(w + 1, w + n + 1, greater<ll>());
    sort(atk + 1, atk + n + 1, greater<ll>());
    f[0][0] = 1;
    f_sum[0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        f_sum[i][0] = 1; // 基础倍率
        for(int j = 1; j <= i; j++)
        {
            f[i][j] = w[i] * f_sum[i - 1][j - 1] % modp;
            f_sum[i][j] = (f[i][j] + f_sum[i - 1][j]) % modp;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            g[i][j] = (atk[i] * cc.C(i - 1, j - 1) % modp + g_sum[i - 1][j - 1]) % modp;
            g_sum[i][j] = (g[i][j] + g_sum[i - 1][j]) % modp;
        }
    }
    for(int i = 0; i < k - 1; i++)
    {
        for(int j = k - i; j <= n; j++)
        {
            ans += f_sum[n][i] * g[j][k - i] % modp * cc.C(n - j, m - k) % modp;
            ans %= modp;
        } // 剩下最后一张攻鸡排
    }
    for(int i = k - 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            ans += f[i][k - 1] * atk[j] % modp * cc.C(2 * n - i - j, m - k) % modp;
            ans %= modp;
        }
    }
    cout << ans << endl;
}

/*
最后乘上了一个数
所以实际上是求所有可能情况能造成的伤害总和
*/

int main()
{
    int T;
    cin >> T;
    while(T--)
        solve();
    return 0;
}

:::

期望在哪

注意到这道题有期望标签。

但整篇题解里没有期望。期望没了，我们学什么？

随机变量

随机变量和期望的关系就像一对笑面虎，两头乌角鲨。不学随机变量学期望，就像学数论不学剩余系一样，虽然能学，但是很难学。

一个从样本空间映射到实数域的函数为随机变量。随机变量 X 的期望 E[X] 满足

E[X]=\sum_{\omega}P(\omega)X(\omega)=\sum_xP(X=x)

其中 P(X=x) 为一个事件，等价于集合 \{\omega|\omega\in \Omega,X(\omega)=x\}。前一个式子从样本空间的输入出发，后一个式子则从输出出发，将结果相同的事件合在一起计算。

随机变量独立跟事件独立性差不多，即称随机变量 X_1,X_2 相互独立当且仅当 P(X_1=x_1,X_2=x_2)=P(X_1=x_1)P(X_2=x_2)。

独立的随机变量 X_1,X_2 满足 E[X_1][X_2]=E[X_1]E[X_2]，即积的期望等于期望的积。

不管随机变量 X_1,X_2 是否独立，其总满足 E[\alpha X_1+\beta X_2]=\alpha E[X_1]+\beta E[X_2]，即线性可加性。

期望又是什么？

原题题解都是基于计数的角度来做的。这部分做法并没有问题，或者说，这也是期望的一个侧面。

因为每种情况是等概率的，又情况总数为 \binom{2n}{m}，所以一种可能最优方案的期望（设其伤害为 d）为 d\binom{2n}{m}，所以所求

\frac{\sum d}{\binom{2n}{m}}\times \binom{2n}{m} = \sum d

即为所有方案伤害的总和。

平时遇到期望题应当怎么做？

事实上，绝大多数概率期望题都只涉及等概率的古典概型。因此，简单地乘上所有方案的总数即可转化为计数题。

但其中还是有些例外的。有些时候，从更深层次的角度出发，反而可以更简单地解决问题，这也许就是成语“深入浅出”的含义吧！

还是例题

爬塔爬完了，很明显不够，还是需要走一下迷宫才行。

我说尖塔和迷宫真是一对苦命鸳鸯啊！

CF123E Maze

首先明确样本空间 \Omega 为所有从起点到终点的路径的集合，每条路径为一个样本点，一些路径的集合为一个事件。

设 A 为一个事件，则概率测度 P(A)=\sum_{\omega\in A}P(\omega)，其中 P 为一个由事件到实数域的函数。这个概率很难算。

既然难算，那就别算了！

注意到我们要求的是 E[X]，不妨将其拆开来看一看：

E[X]=\sum_{\omega}P(\omega)X(\omega)=\sum_xP(X=x)

其中 X(\omega) 为这条路径的总长，也就是经过边次数的总和。不妨转换视角，由每条边出发去看，那路径总长也就等于每条边被经过的次数之和，即 X(\omega)=\sum_e X_e(\omega)，其中 X_e(\omega) 为边 e 被路径 \omega 经过的次数总和。

此时，由概率的线性性质可知，E[X]=\sum_e E[X_e]。

:::warning[一些补充]

前文没有对概率的线性性质做过多说明，因此这里可能会有些难懂。

现将 E[\sum_e X_e(\omega)] 拆开：

\begin{aligned} E[\sum_e X_e(\omega)]&=\sum_{\omega}P(\omega)\sum_e X_e(\omega)\\ &=\sum_e\sum_{\omega}P(\omega)X_e(\omega)\\ &=\sum_e E[X_e] \end{aligned}

:::

因此，接下来只需要求 E[X_e]，即每条边被经过次数的期望。

因为原图是一颗树，而根据树上两点简单路径的性质，要么一条边被经过且仅经过一次，要么不经过这条边。但由于本题是 DFS，所以可能会有一些本来无需经过的边会被经过两次。

所有在必经路径上的边必然都会被经过 1 次。

而对于不在必经路径上的边，其要么被经过 0 次，要么被经过 2 次，这是由树的性质决定的。

那什么时候一条不在必经路上的边会被经过两次呢？

原图是一颗无根树，因此我们假设起点 S 为根。

考虑到终点 T 的路径可以被表示为一些排列，从 S 到 T 的这一段即为被提取出来的排列，那么一条边是否会被经过就取决于它在排列中的位置是在 T 前面还是 T 后面。

设以 S 为根时所有可能的排列为一个样本空间 \Omega_S。

对于 T 子树内的节点，由于 DFS 序的性质，其必然在 T 后面；而对于非 T 子树内的点 x，每一个可能的它在 T 后面的样本点都必然对应一个相反的样本点，因此其概率 P(\omega_x)=\frac{1}{2}，期望为 2\times \frac{1}{2}=1。

这时的 \sum_e E[X_e] 即为总结点数 n 减去 T 的子树的大小。

这坨东西也是随机的，可以理解为从所有可能的 S,T 点对概率空间中选取，S 为根时 n-size_T 即为随机变量，设其为 Y，下面 P(i) 为点 i 被选取的概率。

E[Y]=\sum_S P(S)\sum_T P(T)Y(S,T)

可以用树形 DP 优化，原题链接下面有很多题解，这里就不再过多赘述。

通过记录

后续题解可见《迷宫笑传之猜猜边》。

尾声

虽然关于期望还有很多地方没讲，但这系列可能要咕一段时间，最早也得等我省选游寄写完再说。

以及……

塔二发售了快去玩故障机器人。\ 塔二发售了快去玩故障机器人。

关于我为什么省选前一天还在学概率这种神人东西：战个未来吧。（没开辉眼）

参考文献

胡渊鸣，《浅析信息学竞赛中概率论的基础与应用》，《国家集训队 2013 论文集》

创作声明

本文遵循 CC BY-SA 4.0 协议。

保证本文未使用 AI 工具辅助创作。（我说创造性 AI 卡我启动了）