題意是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 閱讀(408)
評論(0) 編輯 收藏 引用 所屬分類:
組合數學