poj 3088 组合计数，第二类斯特林数

题意：给出n个数字[1,n]，问你可以组成多少种不同的序列，其中每一个序列由几个部分组成，每个部分包含几个数字，每部分内数字无序，部分之间数字有序。每个数字最多使用一次，可以不用。

思路：枚举从n个数字中选出i个数字（组合数），再枚举将这i个数字分成j个部分（第二类斯特林数），然后乘上j的全排列。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int N = 12;
long long c[N][N];
long long s[N][N];
long long q[N];

void init()
{
    //第二类斯特林数
    memset( s, 0, sizeof(s) );
    s[0][0] = 1;
    for ( int i = 1; i < N; i++ )
    {
        for ( int j = 1; j <= i; j++ )
        {
            s[i][j] = s[i - 1][j] * j + s[i - 1][j - 1];
        }
    }
    //组合数
    memset( c, 0, sizeof(c) );
    c[0][0] = 1;
    for ( int i = 1; i < N; i++ )
    {
        c[i][0] = 1;
        for ( int j = 1; j <= i; j++ )
        {
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    }
    //全排列数
    q[0] = 1;
    for ( int i = 1; i < N; i++ )
    {
        q[i] = q[i - 1] * i;
    }
}

long long calc( int n )
{
    long long ans = 0;
    for ( int i = 1; i <= n; i++ )
    {
        for ( int j = 1; j <= i; j++ )
        {
            ans += c[n][i] * s[i][j] * q[j];
        }
    }
    return ans;
}

int main ()
{
    init();
    int t;
    scanf("%d", &t);
    for ( int _case = 1; _case <= t; _case++ )
    {
        int n;
        scanf("%d", &n);
        printf("%d %d %lld
", _case, n, calc(n));
    }
    return 0;
}