940. Quan hệ

Xét một tập N đối tượng có thể so sánh được (2<=n<=10). Giữa 2 đối tượng a và b có thể tồn tại 1 trong 3 quan hệ phân loại:

a = b; a < b; a > b;

Như vậy, với 3 đối tượng (a, b, c) có thể tồn tại 13 quan hệ phân loại như sau:

a = b = c; a = b < c; c < a = b; a < b = c
b = c < a; a = c < b; b < a = c; a < b < c
a < c < b; b < a < c; b < c < a; c < a < b
c < b < a;

Cho số n, hãy xác định số lượng quan hệ phân loại khác nhau.

Input

Gồm nhiều số n. Mỗi số trên 1 dòng. Kết thúc file là -1.

Output

Với mỗi n, đưa ra số lượng quan hệ phân loại tìm được, mỗi số trên 1 dòng (không có dòng trống).

Example

Input:
2
3
-1
Output:
3
13

Link nộp bài ở đây nhé. : http://vn.spoj.com/problems/COND/

Đây là code của mình, xem và tham khảo nhé 

1. #include<algorithm>
2. #include<cstdio>
3. #include<cmath>
4. using namespace std;
5. typedef long long LL;
6. const int MAXN = 10;
7. const int INF = 1000000001;
8. int n;
9. LL f[MAXN+10][MAXN+10];
10. LL g[MAXN+10];
11. int main(){
12. f[0][0] = 1;
13. for (int i=1;i<=MAXN;i++) 
14. for (int j=1;j<=i;j++)
15. f[i][j] = f[i-1][j-1]+j*f[i-1][j];
16. g[0] = 1;
17. for (int i=1;i<=MAXN;i++) 
18. g[i] = g[i-1]*i;
19. scanf("%d", &n);
20. while(n>=0){
21.       LL res = 0;
22.       for (int k=1;k<=n;k++) 
23. res += f[n][k]*g[k];
24.       printf("%lld\n", res);
25.       scanf("%d", &n);
26. }
27. return 0;
28. }