公式

又那么难么？是不是直接用组合就可以了？“P”……

怎么没有说n的上限，万一测试数据中n=2^31-1，r=10怎么办……肯定超出范围。

莫非要用高精度？？！！

通过的人，告诉各位一下，又没有很大的数据？

组合数学的算发与程序设计

吴文虎 王建德的黄书..

越想越觉得可以const

直接数学公式

无语~~~~~

stirling数是啥??????

因为盒子不一样 所以顺序可以改变，所以要乘以r!

日,第4个点总是格式错误...........

两种方法

1，用第二类STRIRLING 数递推公式 S[N，R]：=S[N-1，R-1]+S[N-1，R]*R

ANS：=S[N，R]*R！

2 回溯，先把盒子全部当作一样的处理，求出方案数再*R！

详情请参看黄书(组合数学)-吴文虎 P98~~

先假设R个盒子无区别,再将N个球编号为B1,B2...Bi...Bn,用F表示将前i个球放入前j个盒子的方案总数,对于求Bi有:

Bi单独放一个盒子(假设放入的是盒子j),则其他球(B1~Bn)放入前j-1个盒子,用公式表示为F;

Bi与其他球共放,等价于将Bi放入j个已经有球的盒子中的一个,用公式表示为j*F;

综上所述,F=F+j*F;

最后要把那R个盒子还原成有区别的盒子,只须将F[N,R]*R!即可~~

设M个球N个盒的方法数为S[M，N]

你若要求M个球N个盒 则可分成两种情况

1。第M个球自己独立装在一个盒子里，这就和M-1个球N-1盒联系在一起，分析可得

这种情况的方法数为N*S[M-1，N-1]

2。第M个球和其他的球装在一起，这样就和M-1个球N个盒联系在一起，易得这种情况的方法数为N*S[M-1，N]

所以总共S[M，N]=N*（S[M-1，N]+S[M-1，N-1]）

s[n,r]=r*sum(s[n-i,r-1])(1

St(n,r) =( st(n-1,r) + st(n-1,r-1))*r;

第２类stirling 还要乘上一个r!

hint 有错，害得我直接不看题目

数学不行...

听位大牛说是第2类stirling...

就是把Ｎ个不同的球放到Ｍ个不同的箱子，箱子不为空的数量，

递推关系式是：

S[n,r] =r * (s[n-1,r] + s[n-1,r-1])

听那位大牛说是组合数学的内容....我不知道得出的过程,有谁能赐教?