魔法操作：石子移动游戏

【问题描述】

用C++解决。小明和小亮在玩一个石子游戏。刚开始，小明有n堆石子，小亮有m堆石子。且两人每一堆石子所包含的石子个数均不超过6。

现在，小明需要执行d次魔法操作。每次魔法操作会从当前还剩余的几堆石子中随机选择一堆（选择每一堆的概率相同），并从这一堆中去掉一个石子。

如果某一堆经过一次魔法操作后不再有任何石子，那么在下次魔法操作执行时则不会再考虑这一堆。

现在小明想知道，在经过d次魔法操作之后，小亮一堆石子都不剩的概率是多少？

【输入形式】

输入的第一行包含三个整数n,m和d(1 ≤ n, m ≤ 5; 1 ≤ d ≤ 100)。

接下来一行包含n个整数，表示小明每堆石子的初始石子数。

第三行包含m个整数，表示小亮每堆石子的初始石子数。所有石子数都在1到6之间（包括1和6）。

【输出形式】

输出经过d次魔法操作后，小亮一堆石子都不剩的概率。结果保留四位小数。

【样例输入】

1 2 2
2
1 1
【样例输出】

0.3333

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

const int MAXN = 5;
const int MAXM = 5;
const int MAXS = 6;
const int MAXD = 100;
const int MAXS2 = MAXS * MAXS * MAXS * MAXS * MAXS * MAXS;
double dp[2][MAXS2 + 10];

int n, m, d;
vector<int> a, b;

int get_idx(const vector<int>& v) {
    int res = 0;
    for (int i = 0; i < v.size(); i++) {
        res = res * MAXS + v[i];
    }
    return res;
}

vector<int> get_vec(int idx, int size) {
    vector<int> res;
    while (size--) {
        res.push_back(idx % MAXS);
        idx /= MAXS;
    }
    return res;
}

int main() {
    cin >> n >> m >> d;

    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    b.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }

    memset(dp, 0, sizeof(dp));
    int cur = 0, nxt = 1;
    dp[cur][get_idx(b)] = 1.0;

    for (int t = 0; t < d; t++) {
        memset(dp[nxt], 0, sizeof(dp[nxt]));

        for (int i = 0; i < MAXS; i++) {  // 选择哪一堆石子
            vector<int> tmpa = a;
            if (tmpa[i] > 0) {
                tmpa[i]--;
                for (int j = 0; j < MAXS; j++) {
                    vector<int> tmpb = b;
                    if (tmpb[j] > 0) {
                        tmpb[j]--;
                        int nxt_idx = get_idx(tmpb);
                        dp[nxt][nxt_idx] += dp[cur][get_idx(tmpa)] / (n * m);
                    }
                }
            }
        }

        cur ^= 1;
        nxt ^= 1;
    }

    double ans = 0.0;
    for (int i = 0; i < MAXS2; i++) {
        vector<int> tmpb = get_vec(i, m);
        bool flag = true;
        for (int j = 0; j < m; j++) {
            if (tmpb[j] > 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            ans += dp[cur][i];
        }
    }

    cout << fixed << setprecision(4) << ans << endl;

    return 0;
}