UVa 1647 (递推) Computer Transformation

题意：

有一个01串，每一步都会将所有的0变为10，将所有的1变为01，串最开始为1.

求第n步之后，00的个数

分析：

刚开始想的时候还是比较乱的，我还纠结了一下000中算是有1个00还是2个00

最终想明白后，并不会出现这样的子串。

总结了几个要点：

• 第n步之后，串的长度为2ⁿ，且0和1的个数相等，分别为2^n-1
• 1经过两步变化为1001，所以每个1经过两步变化就会得到一个00，而且这个00分别被左右两边一个1包围着，不会与其他数字凑出额外的00
• 0经过两步变化为0110，所以00就会变成01100110，这样00变化两次仍然还有00

最终得到结论:

　　令F(n)为n次变化之后串中00的个数，则有递推关系F(n+2) = F(n)(两次变化前00的个数) + 2^n-1(两次变化前1的个数)

因为n可能有1000那么大，所以要用高精度。

#include <iostream>
#include <cstdio>
using namespace std;

int A[1005][150], B[1005][150];

int main()
{
    A[0][0] = A[1][0] = 1;
    for(int i = 2; i <= 1000; i++)
        for(int j = 0; j < 135; j++)
        {
            A[i][j] += A[i-1][j] + A[i-1][j];
            B[i][j] += B[i-2][j] + A[i-2][j];
            A[i][j+1] += A[i][j] / 10000; A[i][j] %= 10000;
            B[i][j+1] += B[i][j] / 10000; B[i][j] %= 10000;
        }

    int n;
    while(scanf("%d", &n) == 1)
    {
        int i;
        for(i = 135; i > 0 && B[n][i] == 0; i--);
        printf("%d", B[n][i]);
        for(i--; i >= 0; i--) printf("%04d", B[n][i]);
        printf("
");
    }

    return 0;
}