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

 
{{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}}

解题思路：

第二类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数）,布布扣,bubuko.com

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

原文：http://blog.csdn.net/sr_19930829/article/details/38293053