题解：UVA10759 Dice Throwing

He_Jie · 2025-06-10 21:58:37 · 题解

翻译

有 n 个骰子，问掷出的点数之和至少为 x 的概率是多少。用分数表示。

解法

刚开始想用数学的方法来解，但数学对我来说太神秘了，所以没想出来。我也不知道能不能用数学方法解出来，如果有，欢迎告诉我做法，感谢！

因此，如果用动态规划（DP）来解决这个问题的话，定义 dp_{i,j} 表示掷了 i 个骰子，所得点数之和为 j 的方法数。我们可以发现，最后一个骰子掷出的点数为 1 到 6，那么 dp_{i, j} 的值等于少掷一个骰子，点数分别少 1 到 6 的方法数之和，即：

设置初始值 dp_{0, 0} = 1，并进行状态转移。

注意，题目问的是点数之和至少为 x，所以还需要计算后缀和。概率等于满足条件的状态数除以所有可能的状态数，最后分子和分母要除以它们的最大公约数（gcd）进行约分。

代码

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

ull gcd(ull a, ull b) {
    return a ? gcd(b % a, a) : b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<vector<ull>> dp(25, vector<ull>(151));
    dp[0][0] = 1;

    for (int i = 1; i <= 24; i++) {
        for (int j = i; j <= i * 6; j++) {
            for (int k = 1; k <= 6 && j - k >= 0; k++) {
                dp[i][j] += dp[i - 1][j - k];
            }
        }
    }

    for (int i = 0; i <= 24; i++) {
        for (int j = 149; j >= 0; j--) {
            dp[i][j] += dp[i][j + 1];
        }
    }

    vector<ull> res(25);
    res[0] = 1;
    for (int i = 1; i < 25; i++) {
        res[i] = res[i - 1] * 6;
    }

    int n, x;
    while (cin >> n >> x, n || x) {
        if (dp[n][x] == 0) {
            cout << "0\n";
        } else if (dp[n][x] == res[n]) {
            cout << "1\n";
        } else {
            ull common_divisor = gcd(res[n], dp[n][x]);
            cout << dp[n][x] / common_divisor << '/' << res[n] / common_divisor << '\n';
        }
    }

    return 0;
}