FOJ 1570 集合划分问题[第二类斯特林数]_综合

题目链接
Problem Description

n个元素的集合{1,2,…,n}可以划分若干个非空子集。例如，当n=4时，集合{1,2,3,4}可以划分为15个不同的非空子集如下:

{
    {1},{
    2},{
    3},{
    4}},
{
    {1,2},{
    3},{
    4}},
{
    {1,3},{
    2},{
    4}},
{
    {1,4},{
    2},{
    3}},
{
    {2,3},{
    1},{
    4}},
{
    {2,4},{
    1},{
    3}},
{
    {3,4},{
    1},{
    2}},
{
    {1,2},{
    3,4}},
{
    {1,3},{
    2,4}},
{
    {1,4},{
    2,3}},
{
    {1,2,3},{
    4}},
{
    {1,2,4},{
    3}},
{
    {1,3,4},{
    2}},
{
    {2,3,4},{
    1}},
{
    {1,2,3,4}}

给定正整数n(1<=n<=20),计算出n个元素的集合{1,2,…,n} 可以化为多少个不同的非空子集。
Input
多组输入数据，每组数据1行，表示元素个数n.
Output
对于每组数据，输出一行一个数，表示不同的非空子集的个数。
Sample Input

2
4

Sample Output

2
15

Source

FOJ月赛-2008年3月

#include<iostream>
#include<cstdio>
using namespace std;
long long int n,sum,sfirst[25][25];
void init(){sfirst[1][1] = 1;for(int i = 2;i <= 20;i++)for(int j = 1;j <= i;j++)sfirst[i][j] = sfirst[i - 1][j - 1] + j * sfirst[i - 1][j];return;
}
int main(){init();while(~scanf("%lld",&n)){
   //使用long long类型sum = 0;for(int i = 1;i <= n;i++)sum += sfirst[n][i];printf("%lld\n",sum);}return 0;
}