漸化式を立てると，一見循環してしまう． これを式変形して循環しない形にして計算する．
振り出しに戻るものが厄介． そのときの答えを \(x\) とおいて， \(x\) に関する 1次式とみなす．
\(dp_{i} := i\) に居るときの答え(期待値) とする． \(x = dp_{0}\) とおく． \( dp_{i} \) たちを \(x\) の 1次式の状態で dp を計算する．
まず，振り出しに戻るマスが存在しない場合を考える． \(dp_{i} = \sum_{j \in [1,M]} dp_{i+j}/M + 1\). これは累積和で求まる． \(s := \sum_{j \in [1,M]} dp_{i+j}\) を保持しながら遷移すれば良い．
次に，振り出しに戻るマスを考える． \(dp_{0} = ax + b\) の形で表せるから， \(x = ax + b\) を得る． すなわち，\(x = b/(1-a)\) を得る． ただし，\(1-a = 0\) の場合に注意． \(b < 0\) の場合は起きない？
実装
\(x\) の \(1\)次式に対する \(+, -, /\) を定義する． これは struct を用いる． \(ax + b\) を object とみなしたいので， 代わりに係数 \(a,b\) を保持する．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
struct L{
double a,b;
// L(){}
L(double a = 0, double b = 0) : a(a), b(b) {}
L operator + (L x){ return L(a + x.a, b + x.b); }
L operator - (L x){ return L(a - x.a, b - x.b); }
L operator / (double x){ return L(a/x, b/x); }
};
int main() {
ll n,m,k;
cin >> n >> m >> k;
vll va(n); rep(i,k) { ll p; cin >> p; va[p] = 1; }
L s(0,0);
drep(i,n){
if(va[i]){
dp[i] = L(1,0);
}else{
dp[i] = s/m + L(0,1);
}
s = s + dp[i];
if(i+m < n+1) s = s - dp[i+m];
}
double a = dp[0].a, b = dp[0].b;
if(a + 1e-6 > 1) {
cout << -1 << endl;
return 0;
}
L ans = b/(1-a);
printf("%.10lf", ans.a) ;
return 0;
}
