首页 > 试题广场 >

和为p点游戏

[编程题]和为p点游戏
  • 热度指数：4 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}一个骰子由六个面组成，每一个面上的数字分别是 1,2,3,4,5,6。投出骰子后，顶上面的数字即为投掷结果。可以视作投出每一个数字的概率都是相等的，为 \tfrac{1}{6}。
\hspace{15pt}小歪有 k 个骰子，每一轮他会投掷所有骰子，然后记录下所有骰子投掷结果的和。
\hspace{15pt}小歪可以投掷若干轮，并累加投掷结果，他想知道，投掷任意多轮，总点数之和为 p 的概率是多少。你需要将答案对 (10^9+7) 取模后输出。

\hspace{15pt}提示：本题中，在进行除法的取模时，即计算 \left(p \times q^{-1} \bmod M\right)，其中，q^{-1} 可以使用公式 \left(q^{M-2} \bmod M \right) 得到：例如，在计算 \tfrac{5}{4} \bmod M 时，根据公式 4^{-1} = \left(4^{M-2} \bmod M\right) = 250\,000\,002，得到 \left(p \times q^{-1} \bmod M\right) = 5 \times 250\,000\,002 \bmod M = 250\,000\,003。

输入描述:
\hspace{15pt}第一行输入两个正整数 k,p\left(1\leqq k, p \leqq 10^3\right) 代表骰子数量、目标点数。


输出描述:
\hspace{15pt}输出一个整数，代表小歪投出总点数之和为 p 的概率。

\hspace{15pt}可以证明答案可以表示为一个不可约分数 \tfrac{p}{q}，为了避免精度问题，请直接输出整数 \left(p \cdot q^{-1} \bmod M\right) 作为答案，其中 M = 10^9+7 ，q^{-1} 是满足 q\times q^{-1} \equiv 1 \pmod{M} 的整数。
\hspace{15pt}更具体地，你需要找到一个整数 x \in [0, 10^9+7) 满足 x \times q 对 10^9+7 取模等于 p，您可以查看样例解释得到更具体的说明。
示例1

输入

5 5

输出

490869345

说明

\hspace{15pt}在这个样例中，唯一一种可以投掷出 5 点的情况为，投掷一轮，且每一个骰子的点数均为 1，因此概率为 \tfrac{1}{6^5}=\tfrac{1}{7776}。
\hspace{15pt}我们可以找到，490\,869\,345 \times 7776 = 3\,817\,000\,026\,720，对 M 取模后为 1。所以输出即为 490\,869\,345。
示例2

输入

1 3

输出

893518525

说明

\hspace{15pt}在这个样例中，有且仅有以下四种投掷方法：
\hspace{23pt}\bullet\,投掷一轮，且投出 3 点；
\hspace{23pt}\bullet\,投掷两轮，第一轮投出 1 点，第二轮投出 2 点；
\hspace{23pt}\bullet\,投掷两轮，第一轮投出 2 点，第二轮投出 1 点；
\hspace{23pt}\bullet\,投掷三轮，第一轮投出 1 点，第二轮投出 1 点，第三轮投出 1 点。
\hspace{15pt}总概率为 \tfrac{1}{6} + \tfrac{1}{6^2} + \tfrac{1}{6^2} + \tfrac{1}{6^3}。
示例3

输入

2 3

输出

55555556

说明

\hspace{15pt}在这个样例中，有且仅有以下两种投掷方法：
\hspace{23pt}\bullet\,投掷一轮，第一个筛子投出 1 点，第二个筛子投出 2 点；
\hspace{23pt}\bullet\,投掷一轮，第一个筛子投出 2 点，第二个筛子投出 1 点。
\hspace{15pt}总概率为 \tfrac{1}{6} + \tfrac{1}{6}。
算法知识视频讲解
添加回答
歌手淘汰250加7我不忍啦头像 歌手淘汰250加7我不忍啦 
k, p = map(int, input().split())
MOD = 10 ** 9 + 7
import math

dp = [[0 for _ in range(p + 1)] for _ in range(k + 1)]

for x in range(1, min(7, p + 1)):
    dp[1][x] = 1

for i in range(2, k + 1):
    for j in range(i, min(6 * i + 1, p + 1)):
        for x in range(max(1, j - 6), j):
            dp[i][j] += dp[i - 1][x]

fenzi = dp[k][p]
fenmu = 6 ** k

g = math.gcd(fenmu, fenzi)
fenmu = fenmu // g
fenzi = fenzi // g
fenzi = fenzi % MOD

def mod_pow(a, b, mod):
    result = 1
    a = a % mod
    while b > 0:
        if b % 2 == 1:
            result = (result * a) % mod
        a = (a * a) % mod
        b = b // 2
    return result

inv_fenmu = mod_pow(fenmu, MOD - 2, MOD)

final_result = (inv_fenmu * fenzi) % MOD
print(final_result)
有没有老哥帮我看看代码哪里有问题，跑下来对了11个，无奈了
发表于 2025-06-23 16:54:45 回复(0)
提交观点

问题信息

难度：
1条回答 13浏览

热门推荐

相关试题

和为p点游戏

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号