集合的划分

【寻物启示】继续找我的脑子，麻烦各位了

【题目背景】

　　公元2020年，一群科学家通过佩奇的遗传基因克隆出了许多佩奇，想让她们去往不同的时空带给小朋友们快乐

【题目描述】

　　设s是n只佩奇最开始所在的时空，s = {peppa1，peppa2，……，peppan}，现将s划分成K个满足下列条件的子时空是s1，s2，……sk，且满足：

1、任何一个时空中都必须有一只佩奇

2、佩奇不可以分身，所以任意两个时空中的佩奇是不能重复的

3、所有时空的佩奇加在一起等于n只佩奇

则称s1，s2,，……，sk是时空s的一个划分。它相当于把s时空中的n只佩奇peppa1，peppa2，……peppan放入k个（0<k<=n<30)相同的子时空中，使得没有一个子时空没有佩奇的存在。请你确定n只佩奇peppa1，peppa2，……peppan放入k个相同的子时空中的划分数s（n，k）。

【输入】一行两个整数n、k

【输出】一行，一个整数s(n,k)

【样例输入】10 6

【样例输出】22827

【代码】

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<cstring>
 6 using namespace std;
 7 int s(int n,int k)//递归 
 8 {
 9     if(k == 1) return 1;//如果只有一个时空，那么一定只有一种划分数 
10     else if(k > n) return 0;//如果佩奇的数量小于时空的数量，则不能保证每个时空都至少有一个佩奇，划分数为0 
11     else
12     return s(n - 1,k - 1) + k * s(n - 1,k);//当一个时空只有一只peppa1时，则剩下k-1个时空n-1只peppa的划分数为s(n-1,k-1) 
13 0}//当peppa1存在的时空还有其他peppa存在，则k个时空n-1只peppa的划分数要用 k * s(n - 1,k)来表示 
14 int main()
15 {
16     int n,k;
17     scanf("%d%d",&n,&k);
18     printf("%d",s(n,k));
19     return 0;
20 }

【end】