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输入 #110 0.1 0.2 0.2 0.1 0.2 0.2输出 #11.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_{i1}^{6} p_i 1∑i16pi1p i ∈ [ 0 , 1 ] p_i \in [0, 1]pi∈[0,1]。洛谷测试数据保证p i p_ipi小数点后不超过6 66位且不会出现“卡精度”的极端构造案例。Solution1. 题意投掷一枚可能不均匀的骰子n nn次已知每个面出现的概率求最长的连续出现6 66的次数L LL的数学期望。2. 分析对于非负整数随机变量L LL其期望可以表示为E ( L ) ∑ k 1 n P ( L ≥ k ) E(L) \sum_{k1}^{n} P(L \ge k)E(L)k1∑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 kik时不可能出现连续k kk个6 66此时f ( i , k ) 1 f(i,k) 1f(i,k)1。当i k i kik时只有全为6 66这一种情况不满足故f ( i , k ) 1 − p k f(i,k) 1 - p^kf(i,k)1−pk。当i k i kik时可以从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 , ik \\ 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),ik,ik,ik汇总上面的结果就得到了分布列前面之所以有“1 − 1-1−”是因为我们之前求的是对立事件的概率k kk0 001 112 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 ⋯ k1,k2\cdotsk1,k2⋯连的情况只需要将上述分布列里的概率直接累加就是最终的答案了。即E ( L ) ∑ k 1 n [ 1 − f ( n , k ) ] n − ∑ k 1 n f ( n , k ) E(L) \sum_{k1}^n [1-f(n, k)] \boxed{n - \sum_{k1}^n f(n, k)}E(L)k1∑n[1−f(n,k)]n−k1∑nf(n,k)特别的将上面那个分布列里的相邻两项依次做差能求得具体到“恰好出现k kk连”的概率。换句话说上面的分布列类似于离散的累积概率分布这种反着来的自右往左累积的概率分布一般称为互补累积分布函数也叫右尾累积分布、生存函数等。最后总体的时间复杂度为O ( n 2 ) O(n^2)O(n2)。3. 代码Pythonimportsysdefsolve()-None:datasys.stdin.read().split()ifnotdata:returnnint(data[0])pfloat(data[6])q1.0-pifp0.0:print(0.00)returnifp1.0:print(f{n:.2f})returnexpectation0.0pkpforkinrange(1,n1):dp[0.0]*(n1)foriinrange(k):dp[i]1.0dp[k]1.0-pkforiinrange(k1,n1):dp[i]dp[i-1]-q*pk*dp[i-k-1]prob_ge_k1.0-dp[n]ifprob_ge_k0.0:prob_ge_k0.0ifprob_ge_k1.0:prob_ge_k1.0expectationprob_ge_k pk*pprint(f{expectation:.2f})if__name____main__:solve()4. 轶事在电子游戏里“连续出现”一般会使用英文单词 streakn. 条纹、条带、一连串 v. 奔跑、留下条纹题目里的L LL英语一般称为 longest streak。许多网站的连续登陆打卡也会使用这个单词比如Kaggle。
