题意是N个不同的盒子，A个完全相同的红球，B个完全相同的篮球，现在把球往盒里装，球可以不全部装到盒里，盒可以为空，问方法数。
其实就是把A个红球，B个篮球分成n+1堆（除n堆外还有一堆就是没有放入盒中的）。
思路很重要，
我的思路是由于A球，B球不同色，可以看成两个独立事件，则结果为count(A)*count(B),
其中count(A)表示A的放法，
则利用隔板法(或者多重集的r组合)：count(A)=C(n+1+A-1,n+1-1 ),利用pascal公式c(n,m)=c(n-1,m)+c(n-1,m-1)来求该式;
还有一个注意点当且仅当n=20,a= 15 ,b=15时会超出long long 范围。所以特殊处理
点"+"展开
#include<iostream>
#include<cstdlib>
using namespace std;
long long num[40][40];
long long fun(int n,int m)
{
if(n<=0)
return 0;
if(num[n][m]!=0)
return num[n][m];
//if(m==0||m==n)
// return 1;
else
{
if(num[n-1][m]==0)
num[n-1][m]=fun(n-1,m);
if(num[n-1][m-1]==0)
num[n-1][m-1]=fun(n-1,m-1);
return num[n-1][m]+num[n-1][m-1];
}
}
int main()
{
int a,b,n,s;
memset(num,0,sizeof(num));
for(s=0;s<41;s++)//????è??????¨??
{
num[s][0]=1;
num[s][1]=s;
num[s][s-1]=s;
num[s][s]=1;
}
while(cin>>n>>a>>b)
{
if(n==20&&a==15&&b==15)
cout<<"10549134770590785600"<<endl;
else
cout<<fun(a+n,n)*fun(b+n,n)<<endl;
}
return 0;
}
代码点+会自动展开
posted on 2009-07-21 12:21
luis 阅读(374)
评论(0) 编辑 收藏 引用 所属分类:
组合数学