集合的划分（setsub）

题目描述

设(s)是一个具有(n) 个元素的集合，(s＝{a_1，a_2，dots，a_n})，现将
(s)划分成 (k) 个满足下列条件的子集合 (s_1,s_2,dots,s_k) ，且满足：
1．(si≠emptyset)
2．(siigcap sj＝emptyset (1le i，jle k,i≠j))
3．(s_1igcup s_2igcup s_3igcupdotsigcup s_k＝s)
则称(s_1，s_2，dots，s_k)是集合(s)的一个划分。它相当于把(s)集合中的
(n) 个元素(a_1,a_2,dots,a_n) 放入(k)个((0<k≤n<30))无标号的盒子中，使
得没有一个盒子为空。请你确定(n) 个元素(a_1,a_2,dots,a_n) 放入(k) 个
无标号盒子中去的划分数(s(n,k))。

输入

一行两个整数(n、k)

输出

一行，一个整数(s(n,k))

样例输入

10 6

样例输出

22827

思路：

对于(a_n)个，考虑：

① 若单元素集合({a_n})是(k)个集合中的一个，则剩下的(n-1)个元素组成剩下(k-1)个集合，集合总数为(dp[n-1][k-1])；

② 若单元素集合({a_n})不是(k)个集合中的一个，则可以暂时不考虑(a_n)这一项，共有(dp[n-1][k])个集合。此事考虑将(a_n)置于其中一个集合中，有(k)种可能，集合总数为(k imes dp[n-1][k])。

总递推式：

​ (dp[i][j] = dp[i-1][j-1]+j imes dp[i-1][j])

特判为(forall iin operatorname{N}^+ ,quad dp[i][1]=1)

代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f,N = 3e1+5;
int dp[N][N];
int n,k;
int main(){
	scanf("%d %d",&n,&k);
	for(int i = 1 ; i <= n ; i ++)
		dp[i][1] = 1;
	for(int i = 2 ; i <= n ; i ++)
		for(int j = 2 ; j <= i ; j ++)
			dp[i][j] = dp[i-1][j-1] + j * dp[i-1][j];
	printf("%d",dp[n][k]);
	
	return 0;
}