我将只在这里集中在算法层面。
该问题等价于计算出比k步后的概率，其值之和大于n。
让我们打电话 p 在给定的一步中，元素被选中的概率

p = 1/(M+1)

其思想是以多项式形式表示一次试验的概率集：

A[x] = p * (1 + x^2 + x^3 + ... + x^{M-1})

之后 K 步骤，概率集由下式给出：

F[x] = p^K * (1 + x^2 + x^3 + ... + x^{M-1})^K = p^K A[x]^K

最后，如果 F[x] = sum_i p_i x^i ，则概率为：

P = sum_{i >= N} p_i

问题是如何计算多项式的幂 A[x]^k .
第一次尝试考虑递归地计算它：然后我们得到了与第一个答案中提供的解等价的东西，同样的复杂性。
第二个尝试是隐式地考虑 K .
伪代码：

F[x] = 1
T[x] = A[x]
Power = K
while (Power != 0)
    if (Power mod 2 == 1) F[x] = F[x] * T[x]
    T[x] = T[x] * T[x]
    Power = Power / 2
end while

步数等于 log2(K) .
在每次迭代中，多项式的次数乘以2：复杂度由最后一步决定，其中多项式的阶数等于 KM .
最后一步很复杂 O(K^2 M^2) .
如果 C = K^2 M^2 ，功率计算的全局复杂性为 O(C + C/4 + C/8 + ...) = O(C) = O(K^2M^2) .
与第一种方法相比，这种方法似乎没有任何优势（我可能在复杂性评估中出错了！）。
第三种方法在于考虑多项式乘法等效于卷积，并且可以通过fft过程来执行。由于最终尺寸为o（km），则复杂性为 O(M K (log M + log K)) .
在这里详细描述这个方法会花费很多时间。你可以在网上找到许多关于这个问题的参考资料，例如这里
旁注：很遗憾不能在这里插入乳胶数学公式。。。

这是一个计算所需概率的程序

N = 2
M = 1
K = 3

count = [0] * (N+1)
prev = [0] * (N+1)

count[0] = 1 # empty set

for i in range(K):
    # move count to prev
    for index in range(N+1):
        prev[index] = count[index]
        count[index] = 0

    # calculate new counts
    for prevSum in range(N+1):
        for value in range(M+1):
            newSum = min(N, prevSum+value)
            count[newSum] += prev[prevSum]

ans = (count[N] / pow(M+1, K))
print(ans)

工作代码链接
在这里，我们跟踪集合的计数，这些集合相加到给定的和 count[] 数组
任何加起来大于 N 已添加到 count[N] 这是怎么回事？
起初， count[0] = 1 ，因为我们只有空集 {} （k=1）：尝试向所有现有集添加一个元素： {} + 0, {} + 1 . 我们得到 {0}, {1} 所以呢 count[0] = 1 , count[1] = 1 （k=2）：现在再次向所有现有集合添加一个元素： {0} + 0, {0} + 1, {1} + 0, {1} + 1 . 我们得到 {0,0},{0,1},{1,0},{1,1} 所以呢 count[0] = 1 , count[1] = 2 , count[2] = 1 （k=3）：现在再次向所有现有集合添加一个元素。我们会得到 {0,0,0}, {0,0,1}, {0,1,0}, {1,0,0}, {0, 1, 1}, {1, 0, 1}, {1,1,0}, {1,1,1} . 所以呢 count[0] = 1 , count[1] = 3 , count[2] = 4 在最后一步中，我们还添加了 {1,1,1} 至 count[2] 因为我们加上所有和为 >= N 至 count[N] 最后，我们来计算概率 count[N] （总数为 >=N )所有可能集合的计数，即， (M+1)^K 复杂性是 O(N*M*K) . 在最坏的情况下 N=M*K ，因此时间复杂度可以重写为： O((M*K)^2) 优化1：
如果你写下 count[] 每次迭代的数组 K 你可以发现一个有趣的观察结果：

M=1

sum: 0 1 2 3 4
K=0: 1 0 0 0 0 (if empty consider value as 0 from now on)
K=1: 1 1
K=2: 1 2 1
K=3: 1 3 3 1
K=4: 1 4 6 4 1

M=2

sum: 0  1  2  3  4  5  6  7  8
K=0: 1
K=1: 1  1  1
K=2: 1  2  3  2  1
K=3: 1  3  6  7  6  3  1
K=4: 1  4 10 16 19 16 10  4  1

这里的观察是：

通过保持以前m值的滚动总和，我们可以编写优化版本的代码：

N = 2
M = 1
K = 3
maxValue = M*K

count = [0] * (maxValue+1)
prev = [0] * (maxValue+1)

count[0] = 1 # empty set

for i in range(K):
    # move count to prev
    for index in range(maxValue+1):
        prev[index] = count[index]
        count[index] = 0

    rollingSum = 0

    # calculate new counts
    for Sum in range(maxValue+1):
        rollingSum += prev[Sum]
        if (Sum > M):
            rollingSum -= prev[Sum - (M + 1)]
        count[Sum] = rollingSum

# add all counts of sets whose sum is >= N

ans = sum(count[N:]) / pow(M+1,K)
print(ans)

工作代码链接
这种方法的时间复杂性是 O(M*(K^2))