忘記同步更進(jìn)了

前置知識(shí)

什么是數(shù)學(xué)期望？

類(lèi)似于加權(quán)平均，離散型隨機(jī)變量的一切可能的取值??與對(duì)應(yīng)的概率 ?乘積之和稱(chēng)為該離散型隨機(jī)變量的數(shù)學(xué)期望 。

因此，?可表示為：

分析

本題最大的特點(diǎn)是每個(gè)盤(pán)子中至多有??個(gè)壽司。

如果有兩個(gè)盤(pán)子都有 ?個(gè)壽司，那么它們就沒(méi)有區(qū)別。

也就是說(shuō)，無(wú)論這兩個(gè)盤(pán)子排在哪里，最終輸出的答案是一致的。無(wú)端聯(lián)想排列組合。

因此，我們只需要關(guān)心不同壽司個(gè)數(shù)的盤(pán)子的數(shù)量，這些盤(pán)子的順序?qū)ψ罱K答案沒(méi)有任何影響。

實(shí)現(xiàn)

?表示當(dāng)當(dāng)前壽司數(shù)為??的盤(pán)子有 ?個(gè)，壽司數(shù)為 ?的盤(pán)子有 ?個(gè)，壽司數(shù)為??的步數(shù)為??個(gè)時(shí)，吃完全部所需的期望。

dp 方程如下：

顯然，維度 ?具有單調(diào)性，因此 ?需要放在循環(huán)外層。

Code