首页 > 其他 > 详细

题解 [BZOJ2159] Crash的文明世界

时间:2019-07-13 00:48:27      阅读:49      评论:0      收藏:0      [点我收藏+]

标签:ostream   ons   https   ref   main   ==   str   name   out   

题面

解析

这题一眼换根DP啊

首先,我们考虑一下如何转换\(n^m\)这个式子,

先把式子摆出来吧:\(n^m=\sum_{j=0}^mS(m,j)C_n^jj!\)

其中\(S(m,j)\)表示第二类斯特林数,

(其实就是把\(m\)个不同的小球放到\(j\)个相同的盒子里,且盒子不为空的方案数)

我们感性理解一下(懒得不会推式子),

\(n^m\)其实就表示将\(m\)个不同的球放入\(n\)个不同的盒子里,

而我们