一卡通大冒險

Time Limit: 2000/1000 MS (Java/Others)??? Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1134??? Accepted Submission(s): 732

Problem Description 因為長期鉆研算法， 無暇顧及個人問題，BUAA ACM/ICPC 訓練小組的帥哥們大部分都是單身。某天，他們在機房商量一個絕妙的計劃"一卡通大冒險"。這個計劃是由wf最先提出來的，計劃的內容是，把自己的聯系方式寫在校園一卡通的背面，然后故意將自己的卡"遺失"在某處（如水房，TD，食堂，主M。。。。）他們希望能有MM看到他們遺失卡，能主動跟他們聯系，這樣就有機會請MM吃飯了。他們決定將自己的一卡通夾在基本相同的書里，然后再將書遺失到校園的各個角落。正當大家為這個絕妙的計劃叫好時，大家想到一個問題。很明顯，如果只有一張一卡通，那么只有一種方法，即，將其夾入一本書中。當有兩張一卡通時，就有了兩種選擇，即，將兩張一卡通夾在一本書里，或者分開夾在不同的書里。當有三張一卡通時，他們就有了5種選擇，即： {{A},{B},{C}} , {{A,B},{C}}, {{B,C},{A}}, {{A,C},{B}} ,{{A,B,C}} 于是， 這個邪惡計劃的組織者wf希望了解，如果ACM訓練對里有n位帥哥（即有N張一卡通），那么要把這些一卡通夾到書里有多少種不同的方法。 Input 包含多組數據，第一行為n，表示接下來有n組數據。以下每行一個數x，表示共有x張一卡通。（1≤x≤2000）. Output 對每組數據，輸出一行：不同的方法數，因為這個數可能非常大，我們只需要它除以1000的余數。 Sample Input 4 1 2 3 100 Sample Output 1 2 5 751 又是排列組合的題目，，，，，，，我要思考一下。。。 來完善代碼了，，，哈哈!! /*這是一個組合數學的問題。
其實它等價于：n個有區別的球放到m個相同的盒子中,要求無一空盒,其不同的方案數用S(n,m) 表示,稱為第二類Stirling數。
公式S(n,m)=S(n-1,m-1)+mS(n-1,m),S(n,1)=S(n,n)=1。*/ 還要繼續努力啊，，，哈哈！！ #include<stdio.h> #include<iostream> using namespace std;int a[2002][2002];int main() {for(int i=1;i<=2000;i++){for(int j=1;j<=i;j++){if(i==j||j==1)a[i][j]=1;else{a[i][j]=(a[i-1][j-1]%1000+j*a[i-1][j]%1000)%1000;} // printf("%-4d",a[i][j]); } // printf("\n"); }int n;int m;cin>>n;while(n--){cin>>m;int s=0;for(int i=1;i<=m;i++){s+=a[m][i]%1000;}cout<<s%1000<<endl;} }

?

轉載于:https://www.cnblogs.com/yuyixingkong/p/3370993.html

總結

以上是生活随笔為你收集整理的一卡通大冒险（hdu2512）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。