🐰牛局长的 New 21 点-中
🃏 “牛局长的 New 21 点”
（兔猫信奥学院 · 牛局长 ✧ 闪电 ✧ 豹警官 ✧ 朱迪 ✧ 尼克）
📜 故事背景
课间，牛局长 带来一副改良的 “21 点” 纸牌游戏：“迷你马概率实验太成功啦！今天咱们玩牌。” 规则很简单：
- 爱丽丝以 $0$ 分开局；
- 只要当前分数 $<k$，就必须继续抽牌；
- 每次抽到 $1\sim\text{maxPts}$ 的随机整数，各数出现概率相等；
- 一旦分数 $\ge k$ 就立刻停牌。
请你帮牛局长计算：最终得分 $\le n$ 的概率。 （误差 $\le10^{-5}$ 视为正确）
🌟 题目描述
给定整数 $n,k,\text{maxPts}$：
- 爱丽丝在得分 $<k$ 时不停抽牌，每张牌得分均匀随机自 ${1,\dots,\text{maxPts}}$；
- 抽牌独立同分布；
- 得分 $\ge k$ 立刻停牌。
求爱丽丝最终得分 $\le n$ 的概率 $P$，输出 $P$（双精度）。
🚪 输入格式
n k maxPts
🎯 输出格式
probability
🧩 样例
10 1 10
1.00000
解释：$k=1$，爱丽丝抽一张即停。牌面 $1\sim10$ 都 $\le n$，故概率 $1$。
6 1 10
0.60000
解释：仍只抽一张。10 种等可能结果中，只有 $1\sim6$ 满足 $\le6$，故概率 $6/10=0.6$。
🔢 数据范围
| 参数 | 取值 |
|---|---|
| $0\le k\le n\le10^{4}$ | |
| $1\le\text{maxPts}\le10^{4}$ |
💡 解题思路
设 $\displaystyle dp[i]=\Pr(\text{最终得分}=i)$。 当 $i<k$ 必须继续抽，状态转移：
$$dp[i]=\frac1{\text{maxPts}}\sum_{t=1}^{\text{maxPts}}dp[i-t] \quad(\text{仅当 }i-t\ge0) $$观察可知 得分区间 $[k,n]$ 才会被统计进答案。 用滑动窗口维护最近 $\text{maxPts}$ 个 $dp$ 前缀和，可在 $O(n)$ 内完成。
🐮✨🐰 祝 AC 顺利！