Time Limit: 1 second

Memory Limit: 128 MB

小虎刚刚上了幼儿园，老师让他做一个家庭作业：首先画3行格子，第一行有三个格子，第二行有2个格子，第三行有1个格子。

每行的格子从左到右可以放棋子，但要求除第一行外，每行放的棋子数不能超过上一行的棋子。玩了一会儿，小虎的哥哥大虎

：这个作业有很多种摆放法，我想找到，但我不知道有多少种方案，你能帮助我吗？

大虎是学校信息学集训队的，立刻想到用计算机来解决这个问题，并很快有了解答：13。

第二天他把问题拿到学校，并说如果第一行有N个格子，第二行有N-1个格子，…，第N行有1个格子，怎么办？现在请你一块来帮助

他解决这个难题。

数据范围：

30%数据：1<=n<=12

50%数据：1<=n<=30

100%数据：1<=n<=100

【输入格式】

仅一行，一个正整数N。

【输出格式】

一行，方案总数。

【数据规模】

Sample Input1

2

Sample Output1

4

Sample Input2

3

Sample Output2

13

【样例说明】

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=u240

【题意】

【题解】



除非是最上面那一层;

否则每一行不能是空的;

设f[i][j]表示第i行第j列以下的合法方案数;

有递推公式

f[i+1][j..i+1]+=f[i][j];

写个高精度.

最后累加f[n][1..n]就好



【完整代码】

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <cstring>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 110;

struct bignum

{

    int a[N],len;

    bignum()

    {

        memset(a,0,sizeof a);

        len = 1;

    }

};

int n;

bignum f[N][N];

bignum jia(bignum a,bignum b)

{

    bignum c;

    int &len = c.len;

    int lena = a.len,lenb = b.len;

    len = max(lena,lenb);

    int x = 0;

    rep1(i,1,len)

    {

        c.a[i] = c.a[i]+a.a[i]+b.a[i]+x;

        x = c.a[i]/10;

        c.a[i]%=10;

    }

    while (x>0)

    {

        c.a[++len] = x;

        x = c.a[len]/10;

        c.a[len]%=10;

    }

    return c;

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    rei(n);

    f[1][1].a[1] = 1;

    if (n>1)

        f[1][0].a[1] = 1;

    rep1(i,1,n-1)

    {

        if (i==n-1)

            rep1(j,1,n)

                f[i+1][j] = jia(f[i+1][j],f[i][0]);

        else

            rep1(j,0,i+1)

                f[i+1][j] = jia(f[i+1][j],f[i][0]);

        rep1(j,1,i)

            rep1(k,j,i+1)

                f[i+1][k] = jia(f[i+1][k],f[i][j]);

    }

    bignum ans;

    rep1(i,1,n)

        ans = jia(ans,f[n][i]);

    int len = ans.len;

    rep2(i,len,1)

        printf("%d",ans.a[i]);

    return 0;

}