P1287 盒子与球

题目描述

现有r个互不相同的盒子和n个互不相同的球，要将这n个球放入r个盒子中，且不允许有空盒子。问有多少种方法？

例如：有2个不同的盒子（分别编为1号和2号）和3个不同的球（分别编为1、2、3号），则有6种不同的方法：

输入输出格式

输入格式：

 

两个整数，n和r，中间用空格分隔。（0≤n, r≤10）

 

输出格式： 

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

 

输入输出样例

输入样例#1：

 

3 2

输出样例#1：

 

6

string数

情况一：n个相同盒子，m个不同小球，小球放入盒子，不允许盒子为空

直接第二类stir满足第二类stirling数（斯特林数）；

不了解的：

f[i,j]为前i个小球放入前j个盒子，且盒子无空的方案总数：

递推式：

分析如下：

（1）如果n个元素构成了m-1个集合，那么第n+1个元素单独构成一个集合。方案数 S(n,m-1);

（2）如果n个元素已经构成了m个集合，将第n+1个元素插入到任意一个集合。方案数 m*S(n,m) 。

综合两种情况得：f[i,j]：=f[i-1,j]*j+f[i-1,j-1];

f[i,0]:=0^n;

f[1,1]:=1; f[i,i]:=1; f[n,2]:=2^(n-1)-1; f[n,n-1]:=C(n,2); f[n,m]=0;(m>n);ling数，求f[n,m]即可

情况二：n个不同盒子，m个不同的小球，小球放入盒子，不允许盒子有空。

第二类stirling的变形，

结果为f[n,m]*m!

此题为情况二

 

#include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n,m,c[20][20]={
     1};int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
     if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    return x*f;}int jie(int a){    int res=1;    for(int i=1;i<=a;i++)     res*=i;    return res;}int main(){    n=read(),m=read();    for(int i=1;i<=n;i++)    {        for(int j=1;j<=m;j++)         c[i][j]=j*c[i-1][j]+c[i-1][j-1];    }    printf("%lld",1ll*c[n][m]*jie(m));    return 0;}