[ACM] FZU 1570 集合划分有关问题（不同小球放入相同盒子，第二类Stirling数）

[ACM] FZU 1570 集合划分问题（不同小球放入相同盒子，第二类Stirling数）

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

24

Sample Output

215

Source

FOJ月赛-2008年3月

解题思路：

第二类Stirling数 S（p,k）是将p个元素的集合划分成k个不可辨别的非空盒的划分的个数。

(p个不同的小球，放入k个相同的盒子里面，不允许有空盒)

递推关系为：

S[p][0]=0 （p>=1）,s[p][1]=1 （p>=0）

S[p][k]=s[p-1][k-1]+k*s[p-1][k].

注意int很容易超范围，当p等于20的时候就超出int范围类型。

代码：

#include <iostream>
#include <string.h>
using namespace std;
const int maxn=21;
typedef long long ll;
ll s[maxn][maxn];
ll ans[maxn]; //将i种不同的元素划分为0,1,2,3，...i-1种非空集合一共的总数
int n;

void init()
{
    memset(s,0,sizeof(s));
    memset(ans,0,sizeof(ans));
    s[1][1]=1;
    for(int i=2;i<=20;i++)
        for(int j=1;j<=i;j++)
            s[i][j]=s[i-1][j-1]+j*s[i-1][j];
    for(int i=1;i<=20;i++)
        for(int j=1;j<=i;j++)
            ans[i]+=s[i][j];
}

int main()
{
    init();
    while(cin>>n)
    {
        cout<<ans[n]<<endl;
    }
    return 0;
}

[ACM] FZU 1570 集合划分有关问题（ 不同小球放入相同盒子，第二类Stirling数）