概要
大筋は公式解説と同じだと思います．使った計算のテクニックは少し違いました．
2024年に知られた手法を見たことのない感じの使い方をしました．
解法
長さ $M$ の区間を置いていく問題です．
$i$ 番目のマスが被覆されていないという包除ルールを表す0, 1 文字列を考えます．すると，
- $1$ が $1$ 個以上含まれているような $0,1$ 文字列 $S$ を考える．$a_S$ を，$S$ において $0$ からなる長さ $M$ の部分文字列の個数（ただし円環で数える）とする．$b_S$ を $S$ が含む $1$ の個数とする．
- $k$ 回操作しても全体が被覆できていない確率は $\sum_S (-1)^{b_S-1}(a_S/N)^k$ です．
- 求める期待値は，これを $\sum_{k=0}^{\infty}$ したもの $\sum_S (-1)^{b_S-1}\times \dfrac{N}{N-a_S}$ です．なお $S$ が $1$ を含むとき $a_S<N$ より $N-a_S\neq 0$ となります．
そこで，次で定まる $A[0], \ldots, A[N-1]$ に興味があるということになります：
- $a_S=i$ となるような $S$ に対する $(-1)^{b_S-1}$ の総和．
$A(x) = \sum A[i]x^i$ という多項式を求める問題だと見なすことができます．
$A(x)$ への， $b_S=k$ であるようなものの寄与を考えます．このような文字列 $S$ は $1$ をちょうど $k$ 個含みますが，そのうち特別な $1$ を選んだ場合の数え上げを $k$ で割ればよいです．特別な $1$ の場所によって数え上げが変わらないことを考えると，結局，単に先頭が $1$ であるような文字列の個数の $N/k$ 倍を求めればよいことが分かります．
先頭が $1$ のとき，文字列を $10000/100/1/1/100$ のように $1\cdot 0^n$ の形に区切って考えると，次のような計算手順になります．$x$ の指数が $0$ が $M$ 個続く部分の個数，$y$ の指数が文字列長を表しています．
- $F(x,y) = y+y^2+y^3+\cdots+y^{M-1}+y^M+xy^{M+1}+x^2y^{M+2}+\cdots$ とする．
- $A(x) = [y^N] \sum_{k=1}^{\infty} (-1)^{k-1}\dfrac{N}{k}F(x,y)^k = [y^N] N \log(1+F(x,y))$ である．
$1+F(x,y) = \dfrac{1-y^M}{1-y}+\dfrac{y^M}{1-xy}$ です．これは $x$ について見ると $(a+bx)/(c+dx)$ の形になっているので，次の問題が解ければよいことが分かります：
$[x^0y^0]P=[x^0y^0]Q=1$ であるような多項式 $P(x,y), Q(x,y)$ があり，これらは $x$ について $1$ 次以下であるとき，$[y^N]\log (P(x,y)/Q(x,y))$ を求めよ．
$x$ についての偏導関数と，定数項が求まればよいです．$x$ に関する定数項は単に $[y^N]\log (P(0,y)/Q(0,y))$ で簡単です．偏導関数は次の形の問題になります：
$[x^0y^0]Q=1$ であるような多項式 $P(x,y), Q(x,y)$ があり，これらは $x$ について $2$ 次以下であるとき，$[y^N]P(x,y)/Q(x,y)$ を求めよ．
これは noshi91 さんによる power projection of FPS と同じアルゴリズムで $\Theta(N\log^2N)$ 時間で計算できます．
