給定從1 到 N的 N 個數，問有多少種不同方案劃分這些數。比如N = 3，則有5種方案：
{{1},{2},{3}}
{{1,2},{3}}
{{1,3},{2}}
{{2,3},{1}}
{{1,2,3}}
最后的結果只保留后四位，即mod10000；
上網查了下，集合的劃分的個數叫做bell數，bell數可以遞歸求解：
bell[0] = 1;
bell [n + 1] = sigma(C(n,k))*(bell[k]); (0<=k<=n)
然而這個題卻不可以這樣做，因為N得范圍是2000，這樣做必定超時，于是想到了DP，如果用dp[i][j]表示i個數
劃分成j個集合，那么便有dp[i][j] = j * dp[i-1][j] + dp[i-1][j-1];( i > j )直觀理解就是，將i個數劃分成j個集合的個數，即為i-1個數劃分到j個集合的數，再將多的那個依次放到j個集合中，所以乘以j，或者是i-1個數放在j-1個集合中，第j個集合為空，則正好將多的這個數放到這個集合中，于是便有上邊的狀態轉移方程。
Code:
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int map[2002][2002];
void DP()
{
memset(map,0,sizeof(map));
int i,j,k;
for(i = 0;i <= 2000; i++){
map[i][i] = 1;
map[i][1] = 1;
}
for(i = 0;i <= 2000 ;i++)
for(j = 0; j < i; j++)
map[i][j] = (j * map[i-1][j] + map[i-1][j-1])%10000;
}
int main()
{
int i,j,k,n;
DP();
while(scanf("%d",&n),n){
int ans = 0;
for(i = 0;i <= n; i++)
ans = (ans + map[n][i])%10000;
string str = "0000";
str[3] = ans%10+'0'; ans/=10;
str[2] = ans%10+'0'; ans/=10;
str[1] = ans%10+'0'; ans/=10;
str[0] = ans%10+'0'; ans/=10;
cout<<str<<endl;
}
}