题目链接：https://ac.nowcoder.com/acm/problem/213374

到主站看：https://blog.csdn.net/weixin_43346722/article/details/109430120

题目

牛牛在玩飞行棋。

有无限个格子排成一行，从左到右，标号为 ，终点为 ，有一架飞机一开始在 号位置。

排骨龙每回合可以先投掷一次 面的骰子， 到 等概率出现。

投出点数 后，飞机会移动 步，每步移动一格，方向初始向左移动，若到达终点，会向右移动。
若投出的点数为 点，可以继续投掷，直到投出的点数不是 点。
求让这架飞机停在终点回合数的期望。

输入

第一行一个数字 表示 组数据。

接下来每行两个正整数

输出

输出 行，每行保留两位小数输出答案。

样例输入

6
1 6
2 6
3 6
4 6
5 6
6 6

样例输出

5.00
5.00
5.00
5.00
5.00
5.17

数据范围

对于 数据，
对于 数据，
对于 数据，

思路

这道题就是期望 dp 加上一点点数学。

首先我们分三种情况：

第一种，飞行棋在 以上的位置，那设现在在 ，那我们就可以走到 的位置，那这个就可以 dp。（注意，如果走了 是不需要算步数的）
有因为拿的是一段连续的值，那我们可以用前缀和减少时间。

第二种，飞行棋在 ，那其实转移和上面差不多。
但是有一点不同，就是就算摇了 ，可以继续走不算步数，但是这时候已经到终点了。所以这一步还是要算上。

第三种，飞行棋在 以下的位置，我们通过化公式可以得出期望一定是 ，下面我们来求出：

首先，我们要知道这里面每个点的概率都是相同的。
因为无论你怎么走，你都走不出 。（最多从 走到 ）
而且，每次走，有 的几率到终点，其它的几率分别到 里面的点。
每一个点都是这样，每一次走到终点的概率都一样，那期望也就一样了。

接着，那我们可以设期望为 ，然后列出式子：

然后欢乐化简：

然后我们就发现 ，那就求出来了。

比赛时

找规律找出了飞行棋在 以下的规律。
dp 也大概推出来了，结果忘记如果摇到 可以继续摇的规则，然后欢乐爆蛋。

代码

#include<cstdio>
#include<iostream>
#define ll long long 

using namespace std;

ll T, n, d;
double ans, a[100001], q[100001];

int main() {
    scanf("%lld", &T);
    for (int times = 1; times <= T; times++) {
        ans = 0;

        scanf("%lld %lld", &n, &d);

        for (int i = 1; i <= n; i++)
            if (i < d) {
                a[i] = d - 1;
                q[i] = q[i - 1] + a[i];
            }
            else if (i > d) {
                a[i] = (q[i - 1] - q[i - d - 1]) / (1.0 * d) + 1.0 - 1.0 / d;
                //转移，+1.0是多走一步，但是因为如果摇到 d 不算步数，所以要减去 1.0 / d（有这个记录摇到 d）
                q[i] = q[i - 1] + a[i];
            }
            else {
                a[i] = d - 1.0 + 1.0 / d;//这里不能减，因为就算摇了 d，走到终点之后还是要算一步的
                q[i] = q[i - 1] + a[i]; 
            }

        printf("%.2lf\n", q[n] - q[n - 1]);
    }

    return 0;
}