題意是N個(gè)不同的盒子，A個(gè)完全相同的紅球，B個(gè)完全相同的籃球，現(xiàn)在把球往盒里裝，球可以不全部裝到盒里，盒可以為空，問(wèn)方法數(shù)。
其實(shí)就是把A個(gè)紅球，B個(gè)籃球分成n+1堆（除n堆外還有一堆就是沒(méi)有放入盒中的）。
思路很重要，
我的思路是由于A球，B球不同色，可以看成兩個(gè)獨(dú)立事件，則結(jié)果為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)來(lái)求該式;
還有一個(gè)注意點(diǎn)當(dāng)且僅當(dāng)n=20,a= 15 ,b=15時(shí)會(huì)超出long long 范圍。所以特殊處理
點(diǎn)"+"展開(kāi)
#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;
}
代碼點(diǎn)+會(huì)自動(dòng)展開(kāi)
posted on 2009-07-21 12:21
luis 閱讀(408)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
組合數(shù)學(xué)