ACM-FZOJ2009-1715解题报告

新浪博客 发表时间 -- 2009-07-27 22:14:24

<wbr><strong><span style="font-size:24px; word-wrap:normal; word-break:normal; line-height:36px">Ball and Box</span></strong></wbr>

<wbr>算法：</wbr>

<wbr><wbr><wbr><wbr>题目很简单，要求n个不同小球放入r个不同盒子里，求不同方法。。初看时以为高中知识就行（实际上也可以），这里介绍一个公式stirling公式：</wbr></wbr></wbr></wbr>

<wbr><wbr><wbr></wbr></wbr></wbr>递推公式：

　　S(n,k) = 0 (k > n）

　　S(n,1) = 1 (k = 1)

　　s(n,k)=1 (n=k)

　　S(n,k) = S(n-1,k-1)+k*S(n-1,k) (n >= k >= 2)

<wbr>只要我们用数组来表示来存储就能求出。。。</wbr>