书接上文

我终于想明白算法的正确性了

二项式定理做法

$ E[L_i^j]=p_i+p_i\sum_{k=1}^{j}{\tbinom{j}{k}E[L_{i-1}^k]} $

$ \begin{aligned} Ans&=\sum_{i=1}^{n}{p_i\sum_{j=0}^{m-1}{\tbinom{m}{j}E[L_{i-1}^j]}}\\ &=\sum_{i=1}^{n}{p_i}+\sum_{i=1}^{n}{\sum_{j=1}^{m-1}{p_i\tbinom{m}{j}E[L_{i-1}^j]}}\\ &=\sum_{i=1}^{n}{p_i}+\sum_{i=1}^{n}{\sum_{k=1}^{i-1}{\sum_{j_0=m>j_1 \ge j_2 ... \ge j_{i-k} \ge 1}{p_i\tbinom{j_0}{j_1}p_{i-1}\tbinom{j_1}{j_2}p_{i-2}...\tbinom{j_{i-k-1}}{j_{i-k}}p_k}}}\\ &=\sum_{i=1}^{n}{p_i}+\sum_{i=1}^{n}{\sum_{k=1}^{i-1}p_{k...i}\sum_{j_0=m>j_1 \ge j_2 ... \ge j_{i-k} \ge 1}{\tbinom{j_0}{j_1}\tbinom{j_1}{j_2}...\tbinom{j_{i-k-1}}{j_{i-k}}}} \end{aligned} $

正解做法

$ \begin{cases} a_{i,0}=p_i\\ a_{i,j}=\sum_{k=1}^{i-j}\tbinom{i-1-k}{j-1}\prod_{l=k}^{i}{p_l} & 1 \le j \le m-1 \end{cases} $

$ b_j=\sum_{i=1}^{n}{a_{i,j}} $

$ \begin{aligned} Ans&=\sum_{j=0}^{m-1}b_jS_2(m,j+1)(j+1)!\\ &=\sum_{i=1}^{n}{p_i}+\sum_{j=1}^{m-1}\sum_{i=1}^{n}{\sum_{k=1}^{i-j}\tbinom{i-1-k}{j-1}}S_2(m,j+1)(j+1)!\prod_{l=k}^{i}{p_l}\\ &=\sum_{i=1}^{n}{p_i}+\sum_{i=1}^{n}{\sum_{k=1}^{i-1}{\sum_{j=1}^{i-k}{\tbinom{i-1-k}{j-1}S_2(m,j+1)(j+1)!\prod_{l=k}^{i}{p_l}}}}\\ &=\sum_{i=1}^{n}{p_i}+\sum_{i=1}^{n}{\sum_{k=1}^{i-1}{p_{k...i}\sum_{j=0}^{i-k-1}{\tbinom{i-k-1}{j}S_2(m,j+2)(j+2)!}}} \end{aligned} $

对比 $ \sum_{j_0=m>j_1 \ge j_2 ... \ge j_{i-k} \ge 1}{\tbinom{j_0}{j_1}\tbinom{j_1}{j_2}...\tbinom{j_{i-k-1}}{j_{i-k}}} $ 和 $ \sum_{j=0}^{i-k-1}{\tbinom{i-k-1}{j}S_2(m,j+2)(j+2)!} $

它们的组合意义相同：把 $ m $ 个不同球放进 $ i-k+1 $ 个不同的盒子中，第一个盒子和最后一个盒子非空，中间的盒子可以是空盒的时候的方案数，由此可以看出正解的正确性。

不过它是怎么推导出来的我还没有想通