出勤奖励

某学校决定给所有出勤和守时表现良好的孩子们发放现金奖励。存在连续三天缺席，或多于一次迟到的孩子无法获得奖励，其它无上述情况者都可以得到奖金。

连续n天的实际出勤情况可以用一个长度为n，且由L（表示迟到）、O（表示准时）、A（表示缺席）三个字母组成的字符串表示。

例如，

n = 4

天时共有81种，其中恰有43种可以获得奖励：

OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA
OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO
AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL
AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA
LAOO LAOA LAAO

n = 30

时共有多少种可以获得奖励的情况？

本题难度:

解答

用

f (n, k, w)

表示长度为n，有过k次迟到，且以w结尾的满足要求的字符串总数。

其中

2 \leq n \leq 30

，

k = 0, 1

，w是AA、AO、OA、OO、AL、LA、LO、OL这八种字符串之一。

考虑在长度为n-1的字符串后添加一个字母的情形并按此定义递推，很容易就得到结果

1918080160

。

s=["AA","AO","OA","OO","AL","LA","LO","OL"]
f=[[dict.fromkeys(s,1 if n==2 else 0) for k in [0,1]] for n in range(31)]
f[2][0]["AL"]=f[2][0]["LA"]=f[2][0]["LO"]=f[2][0]["OL"]=f[2][1]["AA"]=f[2][1]["AO"]=f[2][1]["OA"]=f[2][1]["OO"]=0
for n in range(3,31):
    f[n][0]["AA"]=f[n-1][0]["OA"]
    f[n][0]["AO"]=f[n-1][0]["AA"]+f[n-1][0]["OA"]
    f[n][0]["OA"]=f[n-1][0]["AO"]+f[n-1][0]["OO"]
    f[n][0]["OO"]=f[n-1][0]["AO"]+f[n-1][0]["OO"]
    f[n][1]["AA"]=f[n-1][1]["OA"]+f[n-1][1]["LA"]
    f[n][1]["AO"]=f[n-1][1]["AA"]+f[n-1][1]["OA"]+f[n-1][1]["LA"]
    f[n][1]["OA"]=f[n-1][1]["AO"]+f[n-1][1]["OO"]+f[n-1][1]["LO"]
    f[n][1]["OO"]=f[n-1][1]["AO"]+f[n-1][1]["OO"]+f[n-1][1]["LO"]
    f[n][1]["AL"]=f[n-1][0]["OA"]+f[n-1][0]["AA"]
    f[n][1]["LA"]=f[n-1][1]["AL"]+f[n-1][1]["OL"]
    f[n][1]["LO"]=f[n-1][1]["AL"]+f[n-1][1]["OL"]
    f[n][1]["OL"]=f[n-1][0]["AO"]+f[n-1][0]["OO"]

print sum(v for v in f[30][0].values())+sum(v for v in f[30][1].values())