UVa1647 Computer Transformation

? ? ? ? 题意：初始串为1，每一步会将所有0变为10，所有1变为01。如1-01-1001-01101001。统计n步之后的串中，00这样连续两个0出现了多少次。

? ? ? ? 思路：找规律。首先，不会出现连续3个0。然后观察数的变化，只有01的下一步会出现00，而1和00的下一步都会出现01。得到f(n)=2*f(n-2)+f(n-1)。然后结果很大爆long long，需要写一个高精度。

? ? ? ? 是时候准备一个大数模版了！

#include <iostream>    
#include <stdio.h>    
#include <cmath>    
#include <algorithm>    
#include <iomanip>    
#include <cstdlib>    
#include <string>    
#include <memory.h>    
#include <vector>    
#include <queue>    
#include <stack>    
#include <map>  
#include <set>  
#include <ctype.h>    
#define INF 1000000  
#define ll long long

  
using namespace std;  

int F[1010][400];  

int main(){
	F[1][0]=1;F[1][1]=0;
    F[2][0]=F[3][0]=1;F[2][1]=F[3][1]=1;
    for(int i=4;i<=1000;i++){
		//F[i]=2*F[i-2]+F[i-1];
		int carry=0;  
        for(int j=1;j<=F[i-1][0];j++){  
            F[i][j]=F[i-1][j]+2*F[i-2][j]+carry;  
            carry=F[i][j]/10;  
            F[i][j]%=10;  
        }  
        F[i][0]=F[i-1][0];  
        if(carry){  
            F[i][F[i-1][0]+1]++;  
            F[i][0]++;  
        }  
	}
    
    int n;
    while(cin>>n){  
		for(int i=F[n][0];i>=1;i--){  
            printf("%d",F[n][i]);  
        }  
        printf("n");  
    }  
    return 0;  
}