題目

直接算是非常困難的，因為每填滿一個倉庫之后分母就變了。

但是不難發現"等概率隨機選一個沒有滿的燃料艙"其實是沒什么用的，直接轉化為等概率選取一個位置\(+1\)，求\(\geq a\)位置個數的期望。這樣的話概率就一直是\(\frac{1}{n}\)。

考慮對于\(1\)號位置計算在全部位置\(\geq b\)之前\(1\)號位置\(\geq a\)的概率是多少，由于每個位置是等價的，所以乘\(n\)就是答案了。

將每次填的位置拿出來形成一個序列，考慮在這個序列有\(a\)個\(1\)的時候就停下來。這樣概率就和序列長度相關了。同時我們還需要保證至少有一個位置在序列的出現次數少于\(b\)次，否則在出現\(a\)個\(1\)之前就停下來了。

設\(F(x)=\sum_{i=0}^{b-1}\frac{x^i}{i!}\)，可以用生成函數將序列寫成如下形式：

即選出\(i\)個位置來出現次數少于\(b\)，剩下的\(n-1-i\)個位置出現次數大于等于\(b\)。\(1\)出現了\(a\)次且必定出現在最后，于是只剩下\(a-1\)個位置可以隨便排列。

后面用一下二項式定理，就能得到：

再用一下二項式定理將\((e^x-F(x))^{n-1}\)展開得：

之后我們會得到一些形如\(c\times x_i\times e^{jx}\)的東西，直接展開得\(c\sum_{k=0}^{\infty}\frac{j^k(k+i)!}{k!n^{k+i+1}}=\frac{c}{n^{i+1}}\sum_{k=0}^{\infty}(\frac{j}{n})^k(k+i)^{\underline i}\)。這里的\(\frac{1}{n^{i+k+1}}\)是這個長度為\(i+k+1\)的序列出現的概率，\(+1\)是因為還有被欽定在最后一個位置的\(1\)。

之后推一波式子：

生成函數中有一個經典結論，\(\sum_{k=0}^{\infty}x^k\binom{k+i-1}{i-1}=\frac{1}{(1-x)^{i}}\)，于是我們可以將\(\frac{j}{n}\)看成\(x\)，就能得到

于是\(c\times x_i\times e^{jx}=\frac{i!c}{n^{i+1}(1-\frac{j}{n})^{i+1}}=\frac{i!c}{(n-j)^{i+1}}\)，\((-F(x))\)的各次冪可以直接暴力NTT來算，于是復雜度為\(O(n^3\log n)\)。

代碼。