学步园

 简单大数，不过公式可能有些难推，先给出我的公式 dp[i] = dp[i-1] + dp[i-2]*2

①：01

②：1001

③：0110 1001

④：1001 0110 0110 1001

⑤：0110 1001 1001 0110 1001 0110 0110 1001

可以发现把每一步分成两分，后一半肯定和上面的一样，所以+dp[i-1]，前一半的一半和上两个一样，而后一半只不过是翻转了一下而已，贡献的0没变，所以+dp[i-2]*2..

#include<stdio.h>
int ds[1001][501];
int main()
{
    int n,i,j,jw,f;

    ds[0][0] = ds[1][0] = 0; ds[2][0] = ds[3][0] = 1;
    for(i=4;i<=1000;i++)
        for(jw=j=0;j<=500;j++)
        {
            ds[i][j] = ds[i-1][j] + ds[i-2][j]*2 + jw;
            jw = ds[i][j] / 10;
            ds[i][j] %= 10;
        }

    while(scanf("%d",&n)!=EOF)
    {
        if(n==1) printf("0");
        else
            for(f=j=500;j>=0;j--)
                if(ds[n][j] || !f)
                {
                    printf("%d",ds[n][j]);
                    f = 0;
                }
        puts("");
    }
}