题意：
有一个01串，每一步都会将所有的0变为10，将所有的1变为01，串最开始为1.
求第n步之后，00的个数
分析：
刚开始想的时候还是比较乱的，我还纠结了一下000中算是有1个00还是2个00
最终想明白后，并不会出现这样的子串。
总结了几个要点：
- 第n步之后，串的长度为2n，且0和1的个数相等，分别为2n-1
- 1经过两步变化为1001，所以每个1经过两步变化就会得到一个00，而且这个00分别被左右两边一个1包围着，不会与其他数字凑出额外的00
- 0经过两步变化为0110，所以00就会变成01100110，这样00变化两次仍然还有00
最终得到结论:
令F(n)为n次变化之后串中00的个数，则有递推关系F(n+2) = F(n)(两次变化前00的个数) + 2n-1(两次变化前1的个数)
因为n可能有1000那么大，所以要用高精度。
#include <iostream>
#include <cstdio>
using namespace std; int A[][], B[][]; int main()
{
A[][] = A[][] = ;
for(int i = ; i <= ; i++)
for(int j = ; j < ; j++)
{
A[i][j] += A[i-][j] + A[i-][j];
B[i][j] += B[i-][j] + A[i-][j];
A[i][j+] += A[i][j] / ; A[i][j] %= ;
B[i][j+] += B[i][j] / ; B[i][j] %= ;
} int n;
while(scanf("%d", &n) == )
{
int i;
for(i = ; i > && B[n][i] == ; i--);
printf("%d", B[n][i]);
for(i--; i >= ; i--) printf("%04d", B[n][i]);
printf("\n");
} return ;
}
代码君