题目描述
题目背景
话说某天小岛从超市里买了许许多多的..雪糕....本来他打算存在冰箱里慢慢享用的...
结果这件事情被寝室里的adx发现了...于是不幸的事情发生了...
题目叙述
小岛回忆起了当时de场景...
那时...寝室里包括自己一共聚集了 n 个人...我从超市里共买了 m 袋不同种类的雪糕.....
醒来之后身边一支雪糕也没有了.....我还可以隐约知道...每个人都不会一支雪糕也不拿...
小岛想知道自己的雪糕现在会在哪...那么当时的情况下...一共有多少种不同的可能呢..?
数据规模
对于30% 的数据，n <= 10，m <= 20。
对于100%的数据， n <= 100，m<= 100。
样例解释
雪糕以 1-3 编号。共六种情况，其中三种为：
1. {1} {2, 3}
2. {2} {1, 3}
3. {3} {1, 2}
另三种与之对称。
输入格式
一行两个数 n，m...
输出格式
一个数表示当时可能的情况数目...
第二类斯特林数。
s(n,k)表示将n个不同物体放在k个一样的盘子上（每份>0个）的方法数。
s(n,k)=k*s(n-1,k)+s(n-1,k-1);
s(m,n-1)*(n-1)!就是本题答案。
1 #include<iostream> 2 using namespace std; 3 4 int n,m,s[105][105][205],d[205],ans[205]; 5 bool flag[105][105]; 6 7 void S(int x,int y){ 8 if(flag[x][y]||x<y||y==0) return ; 9 if(y==1||x==y) {s[x][y][0]=1;flag[x][y]=1;return ;} 10 11 S(x-1,y); 12 S(x-1,y-1); 13 for(int i=0;i<200;++i) 14 s[x][y][i]=y*s[x-1][y][i]; 15 for(int i=0;i<200;++i) 16 s[x][y][i]+=s[x-1][y-1][i]; 17 for(int i=0;i<200;++i) 18 if(s[x][y][i]>9) 19 s[x][y][i+1]+=s[x][y][i]/10,s[x][y][i]%=10; 20 flag[x][y]=1; 21 return ; 22 } 23 24 int main() 25 { 26 cin>>n>>m; 27 n--; 28 29 S(m,n); 30 31 d[0]=1; 32 for(int i=1;i<=n;++i) 33 { 34 for(int k=0;k<200;++k) 35 d[k]*=i; 36 for(int k=0;k<200;++k) 37 if(d[k]>9) d[k+1]+=d[k]/10,d[k]%=10; 38 } 39 40 for(int i=0;i<200;++i) 41 for(int j=0;j<200-i;++j) 42 { 43 ans[i+j]+=d[i]*s[m][n][j]; 44 if(ans[i+j]>9) 45 {ans[i+j+1]+=ans[i+j]/10;ans[i+j]%=10;} 46 } 47 48 49 int i=199; 50 while(ans[i]==0&&i>0) i--; 51 while(i>=0) cout<<ans[i--]; 52 cout<<endl; 53 // system("pause"); 54 return 0; 55 56 }