思路
发现自己与庄家的操作是完全独立的，所以考虑分别计算它们。
首先考虑自己的情况，定义 \(dp_i\) 表示掷出骰子的和为 \(i\) 获胜的概率，并记 \(f(i)\) 表示 \(x = i\) 时就不掷的获胜概率。
对于每一步我们要么掷骰子（并且掷出的值等概率的在 \(1 \sim D\) 中），要么直接结束。两种情况结合容易得出状态转移方程：
\[dp_i = \max(\frac{\sum_{j = i + 1}^{i + D}{dp_j}}{D},f(i)) \]于是现在的问题就转化为了如何计算 \(f(i)\)。根据题目，获胜有两种情况，\(y > n\) 或者 \(x > y\)。现在 \(x,n\) 都已知，关键点就在于 \(y\)。
定义 \(g_i\) 表示庄家最终掷出结果为 \(i\) 的概率。那么 \(y > n\) 的情况就是 \(1 - \sum_{i = 1}^{n}{g_i}\)；\(x > y\) 的情况就是 \(\sum_{i = 1}^{x - 1}{g_i}\)。显然可以前缀和优化一下。
考虑如何求 \(g\)。发现 \(g_i\) 会等概率地贡献给 \(g_{(i + 1) \sim (i + D)}\)，因此每次：
\[\forall j \in [i + 1,i + D],g_j \leftarrow g_j + \frac{g_i}{D} \]但是这样转移是 \(\Theta(LD)\) 的，同时注意到转移本质上是一个区间修改，单点查询，可以使用树状数组维护。
同时，根据题目，当 \(y < L\) 时是还会继续掷骰子的，因此需要将 \(g_{1 \sim (L - 1)}\) 在转移完成后清零。
Code
#include <bits/stdc++.h>
#define re register
#define double long double
using namespace std;
const int N = 4e5 + 10;
int n,l,d;
double g[N],dp[N];
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
struct BIT{
#define lowbit(x) (x & -x)
double tr[N];
inline void modify(int x,double k){
for (re int i = x;i <= 4e5;i += lowbit(i)) tr[i] += k;
}
inline double query(int x){
double res = 0.0;
for (re int i = x;i;i -= lowbit(i)) res += tr[i];
return res;
}
#undef lowbit
}T;
inline double f(int x){
if (x > n) return 0.0;
double res = 1.0 - g[n];
if (x) res += g[x - 1];
return res;
}
int main(){
g[0] = 1.0;
n = read(),l = read(),d = read();
for (re int i = 0;i <= 4e5;i++){
if (i) g[i] = T.query(i);
if (i < l){
T.modify(i + 1,g[i] / d),T.modify(i + d + 1,-g[i] / d);
g[i] = 0.0;
}
}
for (re int i = 1;i <= 4e5;i++) g[i] += g[i - 1];
double sum = 0.0;
for (re int i = 4e5;~i;i--){
if (i > n) dp[i] = 0.0;
else dp[i] = max(sum / d,f(i));
sum += dp[i];
if (i + d <= 4e5) sum -= dp[i + d];
}
printf("%.15Lf",dp[0]);
return 0;
}