P16288 [蓝桥杯 2026 省 Python/Java A 组] 魔法骰子题解-开发者社区

P16288 [蓝桥杯 2026 省 Python/Java A 组] 魔法骰子

Link: https://www.luogu.com.cn/problem/P16288

题目描述

小蓝想用一个 6 面魔法骰子来测试自己的运气。抛掷这个骰子，点数1 , 2 , 3 , 4 , 5 , 6 1,2,3,4,5,61,2,3,4,5,6朝上的概率分别为p 1 , p 2 , p 3 , p 4 , p 5 , p 6 p_1, p_2, p_3, p_4, p_5, p_6p1,p2,p3,p4,p5,p6。

小蓝将连续抛掷这个骰子n nn次，并记录下每次抛掷的结果。令L LL为这n nn次结果中，数字6 66连续出现的最大长度。

现在，请你帮小蓝计算L LL的数学期望是多少。

注意：L LL的期望仅与数字6 66出现的概率p 6 p_6p6有关，其余概率p 1 , … , p 5 p_1,\dots,p_5p1,…,p5仅用于保证骰子概率分布的完整性。

输入格式

输入共两行：

第一行包含一个正整数n nn，表示抛掷次数。

第二行包含6 66个用空格分隔的浮点数p 1 , p 2 , p 3 , p 4 , p 5 , p 6 p_1, p_2, p_3, p_4, p_5, p_6p1,p2,p3,p4,p5,p6，分别表示点数1 , 2 , 3 , 4 , 5 , 6 1,2,3,4,5,61,2,3,4,5,6朝上的概率。

输出格式

输出一个浮点数，表示L LL的数学期望。结果四舍五入保留至小数点后两位。

输入输出样例 #1

输入 #1

10 0.1 0.2 0.2 0.1 0.2 0.2

输出 #1

1.23

说明/提示

【评测用例规模与约定】

对于30 % 30\%30%的评测用例，1 ≤ n ≤ 8 1 \leq n \leq 81≤n≤8；

对于所有的评测用例，1 ≤ n ≤ 500 1 \leq n \leq 5001≤n≤500，∑ i = 1 6 p i = 1 \sum_{i=1}^{6} p_i = 1∑i=16pi=1，p i ∈ [ 0 , 1 ] p_i \in [0, 1]pi∈[0,1]。洛谷测试数据保证p i p_ipi小数点后不超过6 66位，且不会出现“卡精度”的极端构造案例。

Solution

1. 题意

投掷一枚可能不均匀的骰子n nn次，已知每个面出现的概率，求最长的连续出现6 66的次数L LL的数学期望。

2. 分析

对于非负整数随机变量L LL，其期望可以表示为：

E ( L ) = ∑ k = 1 n P ( L ≥ k ) E(L) = \sum_{k=1}^{n} P(L \ge k)E(L)=k=1∑nP(L≥k)

即：期望等于所有P ( L ≥ k ) P(L \ge k)P(L≥k)之和。而P ( L ≥ k ) P(L \ge k)P(L≥k)表示“n nn次抛掷中至少出现一次连续k kk个6 66”的概率。

由于直接求“至少一次”比较麻烦，我们转而求其对立事件：“n nn次抛掷中一次都没有出现连续k kk个6 66”的概率，记为f ( i , k ) f(i,k)f(i,k)（i ii次抛掷后）。
显然P ( L ≥ k ) = 1 − f ( n , k ) P(L \ge k) = 1 - f(n,k)P(L≥k)=1−f(n,k)。

接下来就是老生常谈的 dp 了。

f ( i , k ) f(i,k)f(i,k)表示的是（i ii次试验没有连续k kk次6 66的概率），p pp表示的是单次出6 66的概率。

当i < k i < ki<k时，不可能出现连续k kk个6 66，此时f ( i , k ) = 1 f(i,k) = 1f(i,k)=1。

当i = k i = ki=k时，只有全为6 66这一种情况不满足，故f ( i , k ) = 1 − p k f(i,k) = 1 - p^kf(i,k)=1−pk。

当i > k i > ki>k时，可以从i − 1 i-1i−1的状态转移过来。具体说来，若设g ( i , k ) g(i,k)g(i,k)表示的是第i ii次恰好首次形成连续k kk个6 66，则：

f ( i , k ) = f ( i − 1 , k ) − g ( i , k ) f(i,k) = f(i-1,k) - g(i,k)f(i,k)=f(i−1,k)−g(i,k)

要使第i ii次首次形成连续k kk个6 66，序列末尾必须不为6 66，倒数第二次往前出现k kk个6 66，且前i − k − 1 i-k-1i−k−1次没有出现过连续k kk个6 66。其概率为g ( i , k ) = ( 1 − p ) ⋅ p k ⋅ f ( i − k − 1 , k ) g(i,k) = (1-p) \cdot p^k \cdot f(i-k-1,k)g(i,k)=(1−p)⋅pk⋅f(i−k−1,k)。

综上所述，转移方程就是

f ( i , k ) = { 1 , i < k 1 − p k , i = k f ( i − 1 , k ) − ( 1 − p ) ⋅ p k ⋅ f ( i − k − 1 , k ) , i > k f(i,k) = \begin{cases} 1 &, i < k \\ 1-p^k &, i=k \\ f(i-1,k) - (1-p) \cdot p^k \cdot f(i-k-1,k) &, i > k \end{cases}f(i,k)=⎩⎨⎧11−pkf(i−1,k)−(1−p)⋅pk⋅f(i−k−1,k),i<k,i=k,i>k

汇总上面的结果，就得到了分布列（前面之所以有“1 − 1-1−”是因为我们之前求的是对立事件的概率）：

k kk	0 00	1 11	2 22	⋯ \cdots⋯	k kk	⋯ \cdots⋯	n nn
至少出现一次k kk连的概率P ( L ≥ k ) P(L\ge k)P(L≥k)	1 − f ( n , 0 ) 1-f(n,0)1−f(n,0)	1 − f ( n , 1 ) 1-f(n,1)1−f(n,1)	1 − f ( n , 2 ) 1-f(n,2)1−f(n,2)	⋯ \cdots⋯	1 − f ( n , k ) 1-f(n,k)1−f(n,k)	⋯ \cdots⋯	1 − f ( n , n ) 1-f(n,n)1−f(n,n)

由于这个概率是“至少出现一次k kk连”的概率，因此上述分布列的每一项概率都自动涵盖了具体出现k + 1 , k + 2 ⋯ k+1,k+2\cdotsk+1,k+2⋯连的情况，只需要将上述分布列里的概率直接累加，就是最终的答案了。即

E ( L ) = ∑ k = 1 n [ 1 − f ( n , k ) ] = n − ∑ k = 1 n f ( n , k ) E(L) = \sum_{k=1}^n [1-f(n, k)] = \boxed{n - \sum_{k=1}^n f(n, k)}E(L)=k=1∑n[1−f(n,k)]=n−k=1∑nf(n,k)

特别的，将上面那个分布列里的相邻两项依次做差，能求得具体到“恰好出现k kk连”的概率。换句话说，上面的分布列类似于离散的累积概率分布，这种反着来的，自右往左累积的概率分布，一般称为互补累积分布函数（也叫右尾累积分布、生存函数等）。

最后总体的时间复杂度为O ( n 2 ) O(n^2)O(n2)。

3. 代码

Python

importsysdefsolve()->None:data=sys.stdin.read().split()ifnotdata:returnn=int(data[0])p=float(data[6])q=1.0-pifp==0.0:print("0.00")returnifp==1.0:print(f"{n:.2f}")returnexpectation=0.0pk=pforkinrange(1,n+1):dp=[0.0]*(n+1)foriinrange(k):dp[i]=1.0dp[k]=1.0-pkforiinrange(k+1,n+1):dp[i]=dp[i-1]-q*pk*dp[i-k-1]prob_ge_k=1.0-dp[n]ifprob_ge_k<0.0:prob_ge_k=0.0ifprob_ge_k>1.0:prob_ge_k=1.0expectation+=prob_ge_k pk*=pprint(f"{expectation:.2f}")if__name__=="__main__":solve()