【组合数学】盒子与球

盒子与球

Time Limit:1000MS  Memory Limit:65536k

Description

现有r个互不相同的盒子和n个互不相同的球,要将这n个球放入r个盒子中,且不允许有空盒子。问有多少种方法?
例如:有2个不同的盒子(分别编为1号和2号)和3个不同的球(分别编为1、2、3号),则有6种不同的方法:

Input

两个整数,n和r,中间用空格分隔。(0≤n, r≤10)

Output

仅一行,一个整数(保证在长整型范围内)。表示n个球放入r个盒子的方法。

Sample Input

3 2

Sample Output

6


分析:
可以设f(i,j)表示i个球放入j个箱子,
那么可以推导出f(i,j)=f(i-1,j)*j+f(i-1,j-1);
因为有i个球,j个盒子可以由有i-1个球,j个盒子推倒出来
i-(i-1)=1,那么要将这多出来或者说加上去的球任意放到一个盒子里
那么有多少这样的盒子呢,目前是有j个,所以第一项是f(i-1,j)*j
但这还不够,我们没法考虑少一个箱子的复杂情况,所以只能是箱子和球各少一个
那么最后我们可以在箱子之间任意调换,由于是互不相同,所以乘上一个箱子个数的阶乘就可以了

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int M,N;
int f[11][11];
int num=1;
int main(){
	cin>>N>>M;
	for(int i=1;i<=M;i++) num*=i;
	for(int i=1;i<=N;i++) f[i][1]=1;
	for(int i=2;i<=N;i++)
	    for(int j=2;j<=M;j++)
	        f[i][j]=f[i-1][j]*j+f[i-1][j-1];
	cout<<f[N][M]*num;
}
 
原文地址:https://www.cnblogs.com/wxjor/p/6195205.html