Friday, August 22, 2014

几题排列组合看能不能把你绕晕

(来自买买提论坛。)







n个一样的球,放到m个一样的盒子里,有几种方法
n个一样的球,放到m个都不一样的盒子里,有几种方法
n个一样的球,放到m个除了颜色可能不一样其他都一样的盒子里,有几种方法
n个都不一样的球,放到m个一样的盒子里,有几种方法
n个都不一样的球,放到m个都不一样的盒子里,有几种方法
n个都不一样的球,放到m个除了颜色可能不一样其他都一样的盒子里,有几种方法
n个除了颜色可能不一样其他都一样的球,放到m个一样的盒子里,有几种方法
n个除了颜色可能不一样其他都一样的球,放到m个都不一样的盒子里,有几种方法
n个除了颜色可能不一样其他都一样的球,放到m个除了颜色可能不一样其他都一样的盒
子里,有几种方法






----------------------------------------Tiger's solution---------------------------请大家指正-------


n个一样的球,放到m个一样的盒子里,有几种方法

--------1------第一反应是DP方法。就是n分成最多m个子集,这样需要 m*n的时间和空间。
--------2------先把所有的求排成一串。把所有的盒子排成一串。然后每个球看放到哪个里面就是。就转换成了10块糖,每天至少吃一块儿的问题。 但是,这里的糖是球。最多要吃m天


n个一样的球,放到m个都不一样的盒子里,有几种方法






-----------------------先把所有的求排成一串。只有1种方法。


n个一样的球,放到m个除了颜色可能不一样其他都一样的盒子里,有几种方法


n个都不一样的球,放到m个一样的盒子里,有几种方法


n个都不一样的球,放到m个都不一样的盒子里,有几种方法


n个都不一样的球,放到m个除了颜色可能不一样其他都一样的盒子里,有几种方法



n个除了颜色可能不一样其他都一样的球,放到m个一样的盒子里,有几种方法




n个除了颜色可能不一样其他都一样的球,放到m个都不一样的盒子里,有几种方法





n个除了颜色可能不一样其他都一样的球,放到m个除了颜色可能不一样其他都一样的盒子里,有几种方法









这里有个wiki的链接 。貌似就是讲这样的问题。