这道题我已经推出00和1过两步变成00了，可我没有继续做下去……
后来看了博客发现自己已经做了90%了……
可惜了，以后不要轻易放弃。
1的个数有个规律，就是每次都乘以2，因为0和1下一步都会变出1
然后因为0和1个个数是一样的，所以1的变出1，0的也变出1
最后1的个数就乘以2了
第i次1的个数为2的（i-1）次方。
最后要用高精度，高精度可以不去弄那些类什么的，直接重数组模拟就好了
可以一位存一万来提高效率。
相加，进位，去零
#include<cstdio>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 1123;
const int MAXM = 212;
const int base = 10000;
int a[MAXN][MAXN], b[MAXN][MAXN];void init()
{a[0][0] = a[1][0] = 1;REP(i, 2, MAXN)REP(j, 0, MAXM){a[i][j] += a[i-1][j] * 2;b[i][j] += b[i-2][j] + a[i-2][j];a[i][j+1] += a[i][j] / base;a[i][j] %= base;b[i][j+1] += b[i][j] / base;b[i][j] %= base; }
}int main()
{init();int n;while(~scanf("%d", &n)){int i = MAXM;while(i > 0 && !b[n][i]) i--;printf("%d", b[n][i--]);for(; i>= 0; i--)printf("%04d", b[n][i]);puts("");}return 0;
}