计算机变换(Computer Transformations,ACM,ICPC SEERC 2005,UVa1647)

找规律的题目，首先要列举几个，以发现规律

第一次展开：01

有1个0，1个1，1个01

第二次展开：1001

有2个0，2个1，1个00，1个01，1个10

第三次展开：01101001

有4个0，4个1，1个00，3个01，2个10，1个11

这时可以发现这道题好像存在递推规律，且第i次展开可能只与第i-1次字符串的状态有关

那么该如何思考？

我们发现如下规律：

对于某个序列

1，序列中00这个串只能由上一次01经过展开后得到

01 -> 1(00)1

2，01这个串，要么由上一次的1直接展开得到，要么由上一次的00展开得到

00 -> 1(01)0

3，10这个串，要么由上一次的0直接展开得到，要么由上一次的11展开得到

11 -> 0(10)1

4，11这个串，只能由上一次10展开得到

10 -> 0(11)0

那么，现在，

我们设第i个串中出现0的次数为f[i][0]，出现1的次数为f[i][1]，出现00的次数为f[i][2]，出现01的次数为f[i][3]，出现10的次数为f[i][4]，出现11的次数为f[i][5]

求得递推式如下：

由于本题要高精度，所以我写了个python的代码懒的写高精度

f=[[0 for i in range(0,7)] for j in range(0,1010)]

if __name__=="__main__":
    f[1][3]=1;f[1][0]=1;f[1][1]=1
    for i in range(2,1005):
        f[i][0]=f[i-1][0]+f[i-1][1]
        f[i][1]=f[i-1][1]+f[i-1][0]
        f[i][2]=f[i-1][3]
        f[i][3]=f[i-1][1]+f[i-1][2]
        f[i][4]=f[i-1][0]+f[i-1][5]
        f[i][5]=f[i-1][4]
    try:
        while True:
            n=eval(input())
            print(f[n][2])
    except EOFError:
        pass