学步园

题解：组合数学的知识，推理一下即可。

#include <stdio.h>
#include <string.h>
#define N 2001

int total[N][N];

void compute_total(){
    int i,j;
    for(i = 0; i < N; i ++){
        total[i][0] = 0;
        total[i][1] = 1;
        total[i][i] = 1;
    }
    for( i = 2; i < N; i ++){
        for(j = 2; j < i; j++ ){
            total[i][j] = (total[i-1][j] * j + total[i-1][j-1])%1000;
        }
    }
}

int main(){
    int i,n,t,num,all;
    compute_total();
    scanf("%d",&t);
    while(t--){
        all=0;
        scanf("%d",&num);
        for(i = 1; i <= num; i ++){
            all=(all+total[num][i])%1000;
        }
        printf("%d\n",all);
    }
    return 0;
}