Problem 1570 集合划分问题
http://acm.fzu.edu.cn/problem.php?pid=1570
Accept: 250 Submit: 671Time Limit: 1000 mSec Memory Limit : 32768 KB
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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
//第二类斯特林数
void Stirling_2(__int64 a[][25],int n)
{
//注意:不能在这里写memset(a..);这样不能对main函数中的a数组初始化
//memset(a,0,sizeof(a));
a[1][1]=1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
a[i][j]=j*a[i-1][j]+a[i-1][j-1];
}
}
}
int main()
{
__int64 a[25][25];
memset(a,0,sizeof(a));
Stirling_2(a,20);
__int64 tmp[25]={0};
for(int i=1;i<=20;i++) for(int j=1;j<=i;j++) tmp[i]+=a[i][j];
int n;
while(scanf("%d",&n)==1)
{
printf("%I64d/n",tmp[n]);
}
return 0;
}
