CUC-SUMMER-5-C

C - Computer Transformation

HDU - 1041

---

A sequence consisting of one digit, the number 1 is initially written into a computer. At each successive time step, the computer simultaneously tranforms each digit 0 into the sequence 1 0 and each digit 1 into the sequence 0 1. So, after the first time step, the sequence 0 1 is obtained; after the second, the sequence 1 0 0 1, after the third, the sequence 0 1 1 0 1 0 0 1 and so on.

How many pairs of consequitive zeroes will appear in the sequence after n steps?

Input
Every input line contains one natural number n (0 < n ≤1000).

Output
For each input n print the number of consecutive zeroes pairs that will appear in the sequence after n steps.

Sample Input
2
3
Sample Output
1
1

---

题意：0变成10，1变成01，初始字符为01，经过n次变化，有几个连续的0

解法：dp，递推。最多只可能有两个0相连，看字符串先找规律：

                    0 1
                  1 0 0 1
              0 1 1 0 1 0 0 1
      1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

上面是前四次变化，可以发现n次变化的后一半为n-1次变化的序列，前一半在分两段，前一段是n-2次变化的序列，后一段再分两段，前一段为n-3，依次类推，我们还发现，如果i为偶数，第一个拼接处还会出现一个多0序列，而在其他的拼接出不会发生，因为任何次变化后都会以1结尾。

所以得到递推公式：
f(n) = f(n-1)+f(n-2)+······+f(2)+f(1)+(n+1)%2
f(n-1) = f(n-2)+······+f(2)+f(1)+n%2
化简得：
f(n) = 2f(n-1)+(n+1)%2-n%2

另外输出结果很大远超longlong，所以要用到高精度计算

代码：

#include<iostream>
using namespace std;
int a[1005][100]={0};
int main()
{
    for(int i=2;i<=1000;i++){
        int carry=0;
        for(int j=0;j<100;j++){
            a[i][j]=a[i-1][j]*2+carry;
            if(j==0)
                a[i][j]+=(i+1)%2-i%2;
            carry=a[i][j]/100000;
            a[i][j]%=100000;
        }
    }
    int n;
    while(cin>>n){
        int flag=0;
        if(n==1){
            cout<<0<<endl;
            continue;
        }
        for(int i=99;i>=0;i--){
            if(flag>0){
                printf("%05d",a[n][i]);
            }
            else
                if(a[n][i]>0){
                    cout<<a[n][i];
                    flag=1;
                }
        }
        cout<<endl;
    }
    return 0;
}