202109-4 收集卡牌

20% 数据——搜索

对于这种需要枚举状态的期望类问题，我们可以直接深搜解决。一般而言，搜索有两种方式：

正推。考虑从一个状态出发能够推及到的状态，在递归终点时对答案进行更新，也可以选择将值回传给上个状态。
逆推。考虑一个状态能从哪几个后继状态转移而来，先递归到终点，再逐渐返回更新。

对于本题而言，笔者认为逆推相对容易实现。

正推

考虑需要维护的状态量：

目前抽了几次卡 \(cost\)，用来计算期望；
转移到某个抽卡状态的概率 \(p\)，用来计算期望；
目前持有卡的状态 \(state\)，用来统计获得卡片还是获得金币，以及判断游戏结束。注意这里是统计每张卡牌的情况，而不是总共有多少张牌；
硬币个数 \(coin\)，用来判断游戏结束；

注：这步状态设计存在冗余的量：通过 \(state\) 和 \(coin\) 可以推算出目前抽了几次卡 \(cost\)。但为了方便进行讲解，这里不进行合并。

假设目前的状态是 \((cost, p, state, coin)\)，考虑下一步转移的方向：

通过 \(state\) 可以得知未获得的牌的个数 \(tot\)，若 \(coin \ge tot * k\)，则说明目前可以用硬币买到所有的卡牌，对答案贡献 \(p\cdot cost\)；
否则，我们要继续抽卡，枚举抽到牌的所有情况。假设目前抽到的卡牌为 \(i\)，结果分为两种情况：
1. 目前抽到的卡牌已经存在，即 \(2^i\ \&\ state \not= 0\)。该卡牌会转换为一个硬币，转移到的下个状态为 \((cost + 1, p \cdot p_i, state, coin + 1)\)；
2. 目前抽到的卡牌不存在，即 \(2^i\ \&\ state = 0\)。需要更新持有卡牌的状态，转移到下个状态为 \((cost + 1, p \cdot p_i, state\ |\ 2^i, coin)\)；

考虑一下时间复杂度：每一次从 \(n\) 种卡牌中随机选择一张，最多抽卡次数 \(k(n-1)+1\)，总体复杂度 \(\mathrm{O}(n^{k(n-1)+1})\)，明显过不了。但从实际上考虑，可能的状态没有这么多（比如抽卡次数最多的几次，需要保证全程只能抽到同一张卡牌）。笔者的程序在 \(n=k=5\) 的时候，进入不同状态的次数为 \(46459906\)。

逆推

相比正推，逆推的主要思路是：所有能转移到的后继状态的期望和 +1，相比正推，只需要维护两个量：

目前持有卡的状态 \(state\)；
目前持有的硬币数 \(coin\)。

设目前的状态是 \((state, coin)\)，考虑下一步转移的方向：

通过 \(state\) 可以得知未获得的牌的个数 \(tot\)，若 \(coin \ge tot * k\)，则说明目前可以用硬币买到所有的卡牌，返回 0 即可（因为不用再抽了）；
否则，枚举抽到牌的所有情况，统计所有的期望和，最后 +1。假设抽到的卡牌为 \(i\)，结果分为两种情况：
1. 目前抽到的卡牌已经存在，即 \(2^i\ \&\ state \not= 0\)。该卡牌会转换为一个硬币，所以对应状态比目前硬币数多一，即 \((state, coin + 1)\)；
2. 目前抽到的卡牌不存在，即 \(2^i\ \&\ state = 0\)。需要更新持有卡牌的状态，所对应的状态为 \((state\ |\ 2^i, coin)\)；

代码实现

C++ 正推C++ 逆推

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 20;
int n, k;
double p[maxn];
inline int calc(int state) {
    // 返回目前已经抽到了几张卡
    int cur = 0;
    for (int i = 0; i < n; ++i) {
        if (state & (1 << i))
            ++cur;
    }
    return cur;
}
// 注：存在另一种常见的写法，维护一个整体 ans，在每个递归终点更新。
double dfs(int cost, double curp, int state, int coin) {
    /*
        cost:  目前是第几次抽卡
        curp:  到达目前状态的概率
        state: 目前持有卡牌状态
        coin:  目前持有硬币个数
    */
    int cur = calc(state);
    if ((n - cur) * k <= coin) {
        // 当前硬币足以兑换所有未获得卡牌，结束
        return cost * curp;
    }
    double res = 0;
    for (int i = 0; i < n; ++i) {
        if (state & (1 << i)) {
            // 抽到已经获得的卡牌
            res += dfs(cost + 1, curp * p[i], state, coin + 1);
        } else {
            // 抽到未获得的卡牌
            res += dfs(cost + 1, curp * p[i], state | (1 << i), coin);
        }
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%lf", &p[i]);
    }
    printf("%.10lf\n", dfs(0, 1, 0, 0));
    return 0;
}

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 20;
int n, k;
double p[maxn];
inline int calc(int state) {
    // 返回目前已经抽到了几张卡
    int cur = 0;
    for (int i = 0; i < n; ++i) {
        if (state & (1 << i))
            ++cur;
    }
    return cur;
}
double dfs(int state, int coin) {
    /*
        state: 目前持有卡牌状态
        coin:  目前持有硬币个数
    */
    int cur = calc(state);
    if ((n - cur) * k <= coin) {
        // 当前硬币足以兑换所有未获得卡牌，结束
        return 0;
    }
    double res = 0;
    for (int i = 0; i < n; ++i) {
        if (state & (1 << i)) {
            // 抽到已经获得的卡牌
            res += p[i] * dfs(state, coin + 1);
        } else {
            // 抽到未获得的卡牌
            res += p[i] * dfs(state | (1 << i), coin);
        }
    }
    return res + 1;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%lf", &p[i]);
    }
    printf("%.10lf\n", dfs(0, 0));
    return 0;
}

抽到每张卡概率相同——化简状态后打表或记忆化搜索

考虑在原本的基础上修改转移方程：

由于抽到每张卡牌的概率是相同的，所以我们可以把 \(n\) 张卡牌化简为 \(2\) 种：抽到已有的卡牌和抽到新的卡牌，将转移方向从 \(n\) 种转变为 \(2\) 种。

但是这样复杂度还是不允许。笔者的程序在 \(n=16,k=5\) 的时候，进入搜索 \(1127462785\) 次，在时间允许范围内无法得出结果。需要对这种方法进行一定优化。

打表

因为抽到每张卡牌的概率都是 \(\frac{1}{n}\)，所以实际有效的值为 \(n, k\)，而 \(n,k\) 组合的有效取值只有 \(16\times 5 = 80\) 种。

在 \(n=16,k=5\) 的时候进入搜索 \(1127462785\) 次，按照一秒 \(10^7\) 次运算的话大概需要不到 2min 就可以得出结果，在比赛时是有时间打完的（当然，前提是读到这道题时比赛时间剩的不是太少）。

记忆化搜索

考虑重复计算的部分：当目前持有卡牌数量和持有金币数量确定的时候，在消除到这一步的概率的影响后，对最终答案的贡献是一定的。

如果想到记忆化搜索了，基本上就能想出正解了。

100% 数据——记忆化搜索

使用记忆化搜索时，采用逆推的方法比较容易理解。

正推

考虑重复计算的部分：当目前持有卡牌情况和持有金币数量确定的时候，在消除到这一步的概率的影响后，对最终答案的贡献是一定的。

一个例子

设 \(n=3,k=5\)。假设我们目前已经抽到了卡片 \(A,B\) 且持有硬币 \(3\) 枚（由此可以得知我们已经抽了 5 次卡），转移到该状态的概率为 \(p_{cur}\)，那么我们下一步抽卡则分为两种情况：

以 \(p_c\) 的概率抽到卡片 \(C\)，则结束。对答案的贡献为 \(p_{cur}\cdot (6p_c)\)；
以 \(p_a\) 的概率抽到卡片 \(A\)，则状态转变为持有 4 枚硬币。接下来无论抽到哪张卡牌都会结束。对答案的贡献为 \(p_{cur}\cdot (7p_a)\)；
以 \(p_b\) 的概率抽到卡片 \(B\)，与上一条相似。对答案的贡献为 \(p_{cur}\cdot (7p_b)\)；

综合下来，该部分对答案的贡献为 \(p_{cur}\cdot (6p_c+7p_a+7p_b)\)。可以发现在消去 \(p_{cur}\) 的影响后，该部分的值是一定的。

我们在搜索的时候记录状态，不去重复计算结果即可。

考虑时间复杂度：持有卡牌情况为 \(\mathrm{O}(2^n)\)，持有硬币的数量为 \(\mathrm{O}(nk)\)，最终复杂度为 \(\mathrm{O}(2^n\cdot nk)\)。

逆推

考虑重复计算的部分：当目前持有卡牌情况和持有金币数量确定的时候，期望步数是确定的。

我们在搜索时记录状态，减少重复计算即可。

时间复杂度 \(\mathrm{O}(2^n\cdot nk)\)。